2

There are a lot of algorithms which will tell you whether or not a given point is found inside a polygon.

I'm looking to write an algorithm which, given a non-convex polygon, will return a point which is inside the polygon.

I don't need the point to be in any specific location inside the polygon, but I prefer to receive a point which isn't very close to an edge, but that is not a deal-breaker. It's there merely to mark that polygon's planar straight-line graph (PSLG) as an internal shape for use with Shewchuck's Triangle library for some complicated constrained Delaunay triangulations.

My initial thinking is:

  1. Compute the bounding box
  2. Cast a ray from one corner in the direction of the opposite corner, or from the center of a bounding box edge to the opposite edge center.
  3. Then, a point exactly between the first and second intersection will be inside the polygon.

Is there a better approach?

  • 1
    Well, center points will be as far from the edges of lines as they can be along the ray. But you might also sample 4 or 8 rays, and pick the one point furthest from a line segment. – GrandmasterB Feb 3 '14 at 18:57
  • 1
    When you ask for a "better" approach, how are you weighting computational complexity vs distance from boundary? – Peter Taylor Feb 3 '14 at 19:29
  • 1
    Is a point on an edge considered to be inside or outside the polygon? You might need to handle the case where the diagonal is and edge (i.e. your polygon is a right triangle) or contains an edge. – Jay Elston Feb 3 '14 at 19:30
  • 1
    Non-convex polygons do not always have an inside. For example (0, 0)-(1, 0)-(0, 0)-(0, 1) is an "L" shape with no interior. If this case is possible, give up and pick the position of a convenient vertex or a position on the line between adjacent vertices. Likewise, if self-overlapping polygons are a thing, you're pretty well doomed. – mjfgates Feb 3 '14 at 19:59
  • 1
    @mjfgates, the Non-Convex polys in this case will always have an inside. I can write the algorithm to catch that edge case and fail gracefully, doing nothing. – Rob Perkins Feb 3 '14 at 21:57
1

Your initial approach sounds like it would do what you need, but depending on how much time you could spend on finding a "good" point (not too close to an edge), you could gather several samples in various ways:

  1. Let the intersecting ray hit the other side of the bounding box and look for pairs of intersections (1 & 2, 3 & 4, etc) that are farthest apart from one another.

  2. Cast 2 or 4 rays: from corner to corner, from side to opposite side.

1

If you create a bounding circle instead of a bounding box, you can then select a random point on the circle, and cast rays at every X degrees across the circle (ie, like a chord, creating a fan of rays) to find the points. Then, using whatever preferences you have for point selection, you can select the best point out of the points your 'sweeps' found.

But, I would recommend trying what you have come up with first, because that very well may be sufficient for your needs.

1

Given a polygon (P1, P2, ... Pn), construct triangles from the points adjacent to each vertex (P1 P2 P3), (P2 P3 P4), ... (Pn P1 P2), and check if the center of the triangle is inside the polygon.

0

The following algorithm will do nicely:

p = randpoint();
while(!IsInsidePolygon(p, poly)) {
  p = randpoint();
}

Big problem is choosing randpoint() so that the whole area of the polygon is covered, but the area cannot be too large or the while loop takes too long time.

  • 1
    That doesn't at all sound like it would be efficient... – Rob Perkins Feb 3 '14 at 18:53
  • 1
    While yes, that would work, it'd potentially be much slower than his current algorithm. On the other hand, it'd generate a much more 'balanced' selected point in that it'd be a random point inside. – GrandmasterB Feb 3 '14 at 18:54
  • its pretty bad for small polygons. Best if you have complex polygons that takes large area of the screen. – tp1 Feb 3 '14 at 18:56
  • That's an approach, but, my polygons are not on a screen; they're computed from a cut-point of a 3-d triangle mesh, out of which the segments are taken and ordered. – Rob Perkins Feb 3 '14 at 22:02
0

Finding the point in a triangle which is furthest from its boundary is just finding the incentre. If you triangulate the polygon (not linear time, but not far off), you can then look for a "nice" triangle (e.g. the one with the largest shortest side) and take its incentre.

  • Not quite; my PSLGs are far more complex than triangles, though I could see how an incentre computation could form a part of the full algorithm. – Rob Perkins Feb 3 '14 at 22:01
  • That's why "triangulate" is the first step. – Peter Taylor Feb 3 '14 at 22:16

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.