我有一个位于凹多边形内的点，我想找到多边形外面的最近点 . 我在：For a point in an irregular polygon, what is the most efficient way to select the edge closest to the point?中实现了答案，但是它找到了多边形边缘上的最近点，而不是多边形外部 .
我尝试将线从多边形内部的点延伸到边缘上的点，但有些情况下不会起作用 .
有什么建议？
EDIT: 为了使它更清晰，我在凹面或凸面多边形内有一个点，我想在多边形外面找到一个点，尽可能接近内部的点 . 所以在下图中，我想找到红点 . 它不必在距离上完美地最小化，只需要在外面并且离原始点不太远 . 也许按固定金额？
2 回答
对于大多数情况，向外延伸线的方法看起来足够好
如果确定最近的点是拐角，则只需在外角的平分线处获得外部点 .
如果您需要多个查询，您可以计算多边形的Voronoi diagram（有一个CGAL implementation） . 然后，您可以查找查询点所在的Voronoi单元格 . 您获得最近的输入边缘作为此单元格的站点 . 如果您还计算多边形外部的Voronoi图，则可以从单元格外的边缘处获取靠近此站点的点 .