Find point in polygon

Question

I have a simple, 2 dimensional polygon with vertices 3..n. I need to find an arbitrary point in the interior (not on the boundary) of this polygon. How can I find one? This problem is trivial for convex polygons: Just take three adjacent points that are not lying on the same line (so they are forming a triangle). The midpoint of this triangle is guaranteed to lie inside the polygon. But this approach does not work for non-convex polygons.

   class Point
   {
      public double X, Y;
   }

   Point GetPointInPolygon(Point[] polygon)
   {
      .....
   }

Have you even tried anything? SO is not a code-service. So what´s your idea? What steps should be done to get what you want, maybe some psuedo-code? — HimBromBeere
if you want any point in a polygon given by its vertexes then just return the first vertex. If you want any interior point, excluding vertexes then use the equation of the line by two points (x0,y0), (x1,y1) en.wikipedia.org/wiki/Linear_equation#Two-point_form and get points from x0 to x1. To know if any point is interior read this article stackoverflow.com/questions/4243042/c-sharp-point-in-polygon but this is more than you need. — derloopkat
Have you read wiki article? en.wikipedia.org/wiki/Point_in_polygon — jdweng
@derloopkat Getting a line equation by two arbitrary points does not work for non-convex polygons because not every point on this line is inside the polygon — NMO
determining inside-outside from a given point has well-known solutions. but picking an arbitrary point that's inside, may be non-trivial, and is more a maths/algorithm problem than a programming question. I would start with the idea of probing close, random points on normals on each of the the polygon's sides' midpoints, until I find one to be inside, but there ought to be better deterministic solutions. — Cee McSharpface

Yves Daoust Yves Daoust · Accepted Answer · 2016-07-07T12:42:25

Draw an horizontal line at some ordinate between the extreme values (to be sure to cross the polygon). Compute all intersections of this line with the polygon outline. This is done in a simple loop on the polygon edges, where you detect the changes of side.

You will find an even number of intersections. Sort them by increasing abscissa and pick any point between an even and an odd intersection.

This takes time O(N), which is optimal.

As you can check, the point-in-polygon test by ray casting reports true.

Erratum:

In the worst case, there can be O(N) intersections, and the sorting will take O(N Log(N)) operations. In practice, this is rarely met.

Side note:

If you have the extra requirement that the interior point should be at a sufficient distance from the edges, you can perform the offsetting of the polygon (inner side), and pick a point inside the offset using the same procedure. Offset computation is by no means trivial, though.

The possible offset distances are bounded, but I have no idea how this bound can be found. It will correspond to "deepest" point(s).

Find point in polygon

1 Answers