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?
$\begingroup$
$\endgroup$
3
-
7$\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 PetruninCommented Feb 25, 2011 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 MyersonCommented Feb 26, 2011 at 5:08
-
1$\begingroup$ Just to leave an answer in case searches hit this old question. One method is to find a diagonal of the polygon (endpoints at vertices, otherwise strictly interior), and then take the midpoint of the diagonal. How to find a diagonal is discussed in several textbooks, usually when discussing polygon triangulation. $\endgroup$– Joseph O'RourkeCommented Apr 30, 2021 at 15:38
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
See question 3.6 in the Comp.Graphics.Algorithms FAQ: http://apodeline.free.fr/FAQ/CGAFAQ/CGAFAQ-3.html
$\begingroup$
$\endgroup$
3
- 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, 2011 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$– MichaelCommented Nov 12, 2014 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$ Commented Oct 26, 2017 at 12:44
-
$\begingroup$ @DiomidisSpinellis: For a general polygon (not necessarily connected) the chosen x may meet no edge $\endgroup$– 6502Commented Oct 14, 2021 at 20:00
$\begingroup$
$\endgroup$
For the general polygonal area (not connected, not simply connected, possibly overlapping lines, self intersection allowed provided they happen at a vertex) the solution I came up with is:
- sort all y values
- for any pair of consecutive distinct y values $y_i < y_{i+1}$ compute the horizontal spans that the polygon is intercepting on the line
$$y={y_i + y_{i+1} \over 2}$$
The middle point of any non-empty span is inside the polygon and you can stop the search (note that by construction that point cannot be on an horizontal line). Care as usual must be taken for horizontal segments; for example by considering an edge $(x_a, y_a)-(x_b, y_b)$ intersecting the horizontal line if and only if
$${\rm min}(y_a, y_b) \le y \lt {\rm max}(y_a, y_b)$$
How the horizontal spans are constructed depends on the rule chosen for area definition (even-odd, non-zero winding, positive or negative winding). Note that in the general case (non-simple) polygon there may be no solution (consider the "triangle" built from three aligned points, no point in the plane is "inside").
Also, as usual for practical computer implementation, there can be problems when using floating point values where for example $y_{i} < y_{i+1}$ does NOT imply $y_{i} < {y_{i}+y_{i+1}\over 2} < y_{i+1}$ because, in a computer, the average of two distinct floating point values can be equal to one of the values.
$\begingroup$
$\endgroup$
0
Check this link for program + description
$\begingroup$
$\endgroup$
Partition your polygon into convex parts. From any part take two non-adjacent vertex $v_1$ and $v_2$ and calc
$$ P = (v_1+v_2)/2 $$
