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?
5
$\begingroup$
$\endgroup$
-
6$\begingroup$ 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... $\endgroup$ – Anton Petrunin Feb 25 '11 at 18:08
-
1$\begingroup$ 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. $\endgroup$ – Gerry Myerson Feb 26 '11 at 5:08
2
$\begingroup$
$\endgroup$
See question 3.6 in the Comp.Graphics.Algorithms FAQ: http://apodeline.free.fr/FAQ/CGAFAQ/CGAFAQ-3.html
8
$\begingroup$
$\endgroup$
- 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
answered Feb 25 '11 at 18:21
-
2$\begingroup$ 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. $\endgroup$ – Michael Nov 12 '14 at 22:53
-
$\begingroup$ This is an easy and efficient approach. Note that the x-xoordinate of P must also lie within the polygon's bounding box. $\endgroup$ – Diomidis Spinellis Oct 26 '17 at 12:44
0
$\begingroup$
$\endgroup$
Check this link for program + description
