0

I have a point located inside a concave polygon and I want to find the closest point that is just outside the polygon. I implemented the answer in: For a point in an irregular polygon, what is the most efficient way to select the edge closest to the point? but that finds the closest point on a polygon edge, not outside the polygon.

I tried just extending the line from the point inside the polygon to the point on the edge, but there are instances where that wont work.

Any suggestions?

EDIT: To make it more clear, I have a point inside a concave or convex polygon, and I want to find a point outside the polygon, as close as possible to the point inside. So in below illustration, I want to find the red point. It doesn't have to be perfectly minimized in distance, just needs to be outside and not too far from the original point. Maybe by a fixed amount?

enter image description here

Community
  • 1
  • 1
TaipanRex
  • 795
  • 5
  • 11
  • 1
    This seems ill-defined: mathematically, there *is* no closest point *strictly* outside the polygon: given any point outside the polygon, you can always move a tiny amount more towards the polygon to get a closer point. To help us understand, can you describe what results you'd want in the case of a square with vertices (0, 0), (0, 1), (1, 1), (1, 0)? (And did you mean convex rather than concave?) – Mark Dickinson Oct 25 '16 at 06:35
  • Updated the question! – TaipanRex Oct 25 '16 at 06:48
  • What's wrong with `just extending the line`? – MBo Oct 25 '16 at 07:10
  • @MBo take my diagram above, if the black point was right underneath the corner to the left of it, the closest point would be said corner and extending the line would just extend it inside the polygon. – TaipanRex Oct 25 '16 at 07:22

2 Answers2

1

Approach with extending the line outwards looks good enough for most cases

If you determine that the closest point is corner, just get external point at bisector of outer angle.

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Hmm, looks like this is workable! Can you explain a bit more re. bisector of outer angle? – TaipanRex Oct 25 '16 at 07:53
  • You know two neigbour edges, take their normalized direction vectors and sum them - this is bisector vector (works for acute external edge) – MBo Oct 25 '16 at 08:02
0

In case you need multiple queries you can compute the Voronoi diagram of the polygon (there is a CGAL implementation). Then you can lookup in which Voronoi cell the query point lies in. You get the closest input edge as site for this cell. If you also compute the Voronoi diagram outside of the polygon you can simply take a point close to this site from the edges outside cell.

gue
  • 1,868
  • 1
  • 16
  • 21
  • Thanks for the idea, but I am hoping for something computationally cheaper. Some of the polygons I am working with have over a thousand edges. – TaipanRex Oct 25 '16 at 07:23
  • The Voronoi diagram of a simple polygon is O(n) in theory, and O(n log n) in practice. – gue Oct 25 '16 at 10:45