Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Polygon Algorithms


Date: 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/   
    
Associated Topics:
College Triangles and Other Polygons
High School Triangles and Other Polygons

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/