Polygon AlgorithmsDate: 05/10/2001 at 08:59:26 From: Andriy Tylychko Subject: Polygon algorithms Dear Sir, Given a polygon as a set of points (X, Y) and a database table with "X" and "Y" columns, select all records/points from the table that are inside the polygon or belong to its border. Please let me know any useful information (Internet links, algorithms, programming sources etc.). Thank you very much, Andriy Tylychko, Date: 05/10/2001 at 12:30:34 From: Doctor Rob Subject: Re: Polygon algorithms Thanks for writing to Ask Dr. Math, Andriy. If the polygon is convex, there are several methods. For two, see: Formula for Point in Rectangle http://www.mathforum.org/dr.math/problems/scott5.31.96.html If the polygon is concave, cut it into convex pieces using internal diagonals, and apply the algorithm for convex polygons to each piece. If the point is inside any piece, it is inside the polygon. To test for convexity, pick each edge in turn, and see if all the other vertices are on the same side of that edge. If that is so for all the edges, the polygon is convex. If not, it is concave (and one of the vertices on any such edge is at an angle larger than 180 degrees). A diagonal is internal if its endpoints split the polygon's vertices into two sets of contiguous vertices, each of which lies on a single side of the diagonal, and the two sets lie on opposite sides of the diagonal. Another method that works for triangles appears at Analytic Geometry Formulas http://mathforum.org/dr.math/faq/formulas/faq.analygeom_2.html Select Two Dimensions: Triangles, and then scroll down to find the formulas you need, involving r, s, and t (the barycentric coordinates of the point with respect to the three vertices of the triangle). You can apply this to a general polygon by cutting it into triangles using internal diagonals, and testing to see if the point is inside any of the triangles. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/