# Get a point inside a polygon

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

• 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 '11 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 '11 at 5:08

See question 3.6 in the Comp.Graphics.Algorithms FAQ: http://apodeline.free.fr/FAQ/CGAFAQ/CGAFAQ-3.html

1. find the AABB (axis aligned bounding box) of the polygon
2. choose a point P outside the bounding box, for example at the left and below the AABB
3. choose a point M on the middle of an edge of the polygon
4. intersect the line PM with the polygon and collect the intersection points in a list
5. 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
6. sort the intersection points you find by the increasing distance from P
7. your result is the middle of the segment determined by the first two intersection points
• For P choose a point with x-coordinate different from x-coordinates of all the vertices; instead of PM use a vertical line; and now you don't need to iterate. – Michael Nov 12 '14 at 22:53
• This is an easy and efficient approach. Note that the x-xoordinate of P must also lie within the polygon's bounding box. – Diomidis Spinellis Oct 26 '17 at 12:44

Check this link for program + description

http://alienryderflex.com/polygon/