CODEWITHSUNDEEP
c#computational-geometry
NMO
NMO

Reputation: 786

Find point in polygon

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)
   {
      .....
   }

Upvotes: 1

Views: 760

Answers (1)

user1196549
user1196549

Reputation:

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.

enter image description here

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).

Upvotes: 4

Related Questions