algorithm - 在谷歌地图的多边形内任意放置一个标记

Question

关于如何检测标记是否在谷歌地图的多边形内有很多文档。但是，我的问题是如何在多边形内任意放置标记（最好远离边缘）

我尝试计算多边形点的平均纬度和经度，但这显然在某些非凹多边形中失败。

我还考虑过计算该区域的质心，但显然也是如此。

有任何想法吗？我想避免反复试验的方法，即使它在 99% 的时间内都有效。

Answer 1

有几种不同的方法可以解决这个问题，具体取决于您的总体目标是什么。

一种方法是构建多边形的三角剖分并将标记放置在其中一个三角形内。如果您不太担心最优性，则可以采用简单的启发式方法，例如选择最大三角形的质心，尽管这显然不一定会给您提供离多边形边缘最远的点。多边形三角剖分有多种算法：剪耳或约束 Delaunay三角剖分可能是可行的方法，并且存在许多好的库，即CGAL和Triangle。

如果您有兴趣找到最佳位置，则可以使用基于骨架的方法，使用多边形的中轴或直骨架。中轴是与多边形边缘等距的曲线集，而直骨架是相关结构。具体来说，这些类型的结构可用于查找距离边缘最远的点，请使用基于直线骨架的方法检查用于 GIS 的标签放置应用程序。

希望这可以帮助。