6
$\begingroup$

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?

Improve this question
$\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
3
$\begingroup$

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

Improve this answer
$\endgroup$
9
$\begingroup$
  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
Improve this answer
$\endgroup$
  • 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$

Check this link for program + description

http://alienryderflex.com/polygon/

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.