Welcome to MathOverflow

Question

0

I have a 2D polygon of arbitrary geometry. I need to find any point that is inside of that polygon. The center won't work because the polygon might be convex. Is there a way to quickly find a point inside an arbitrary geometry?

flag	asked Feb 25 2011 at 17:49 unknown (google) 3●2

4

I assume that "polygon" is a set bounded by simple closed broken line (?). Do you need a kind of algorithm? Say what if you take a point $p$ on a side of polygon; take a line $\ell$ in general position; count number of intersections of $\ell$ with other sides before $p$ and go bit left from $p$ if the number is even and bit to the right if it is odd... – Anton Petrunin Feb 25 2011 at 18:08

Sure - you just look at the polygon, and pick a point inside it. But maybe when you say you "have a 2D polygon," you don't mean you have a piece of paper with the polygon on it. So, what do you mean? Unless we know in what way you "have" this polygon, we can't give a sensible procedure for saying anything about it, much less finding a point inside it. – Gerry Myerson Feb 26 2011 at 5:08

lhf · Accepted Answer · 2011-02-25 18:14:09Z UTC

2

See question 2.06 in the Comp.Graphics.Algorithms FAQ: http://www.exaflop.org/docs/cgafaq/cga2.html#Subject%202.06:%20How%20do%20I%20find%20a%20single%20point%20inside%20a%20simple%20polygon?

answered Feb 25 2011 at 18:14

lhf
1,875●1●8●19

Cristi Stoica · Answer 2 · 2011-02-25 18:21:56Z UTC

find the AABB (axis aligned bounding box) of the polygon
choose a point P outside the bounding box, for example at the left and below the AABB
choose a point M on the middle of an edge of the polygon
intersect the line PM with the polygon and collect the intersection points in a list
check if the intersection points are passing too close to the vertices of the polygon. If so, go back to 2 and choose another point P outside the polygon, because otherwise you may run into problems
sort the intersection points you find by the increasing distance from P
your result is the middle of the segment determined by the first two intersection points

Get a point inside a polygon

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.