比质心更好的中心点

Question

我在地图应用中使用多边形的质心来标记位置。这对于凸多边形来说效果非常好，对于许多凹多边形也表现良好。

然而，有些多边形（如香蕉形，甜甜圈形）显然不能产生预期的结果：这些情况下，质心在多边形区域外部。

有人知道寻找一个合适的点在多边形区域内（可能包含空洞！）来标记位置的更好方法吗？

- user2033412

---

一些应用程序在找到重心后会进行点在多边形内的判断。如果它在外面，就会根据射线与多边形相交的中点计算出一个新的x或y。 - NaN

我认为你可以通过三角测量来完成。例如，在第一步中，对多边形进行三角剖分，然后尝试找到一个符合所需标准的中心三角形，并返回其重心。 - vahidreza

我想把一个凹多边形分割成凸部分（也许已经表示了），选择其中最“丰满”的部分（绝对直径大且最大直径/最小直径比值接近1），并将点放在该部分的中心。这可能需要相当多的计算，因此我会考虑缓存结果或将它们与多边形一起存储。 - 9000

你似乎正在寻找距离任何边界最远的点。在一个数学论坛上问这个问题。 - Christophe Roussy

@ChristopheRoussy：没错！ - user2033412

Answer 1

一种方法是生成和优化多边形的骨架, 然后使用骨架的中点来放置标记（如果是文本，则正确定位文本）。这对大多数形状都有效，包括具有孔的形状，以及香蕉形或蝌蚪形新月形。

CGAL库具有2D直线骨架和多边形偏移模块，或者您可以例如使用PostGIS。

- Toby Speight

---

因此，如果在连续收缩过程中每个轮廓都被赋予一个递增的高度，请取最高点。 - Will Ness

@Will - 这是一种方法（并将为您提供距离任何边缘最远的点）。对于哑铃形状的多边形，您可能希望算法选择“杆”的一个点 - 在这种情况下，您应该优先选择沿骨架脊柱的（可能加权）平均位置。 - Toby Speight

Answer 2

重新表达ChristopheRoussy的评论，我们可以寻找多边形内的最大圆。

最大圆是不能再增长的圆，因为它触碰到了三个顶点或边缘（如果只接触到两个，则可以变大或移动到第三个）。

因此，如果您只有一些顶点，可以枚举所有可能的三元组顶点/边缘，为每个找到一个圆，然后选择最大的那个。

但这将需要创建四个函数：

1. Circle（vertex，vertex，vertex） 2. Circle（vertex，vertex，edge） 3. Circle（vertex，edge，edge） 4. Circle（edge，edge，edge）

所有这些函数都是可行的，但可能需要一些努力。

- maxim1000

Answer 3

找到极端的纵坐标并在中间画一条水平线。保证会穿过多边形。

找到与边相交的点，并按照x轴递增的顺序进行排序。在两个交点中间选择一个点。

这是一个O（N + K Log K）的过程，其中K是交点的数量（通常是非常小的偶数）。编写起来相当简单。

为了增加放置的美观性，您可以尝试三条水平线而不是一条，并选择最长的交点线段。

- user1196549

---

如果多边形的内部不连通，并且水平线与多边形的交点位于多边形的自相交处，则此方法可能会失败。例如，多边形可以是一个八字形，而水平线可以横跨八字的腰部。 - Adam Gawne-Cain

@AdamGawne-Cain：不，这个是有效的。你会得到两个重叠的交点，定义了一个退化线段。 - user1196549

我同意你会得到一个点，但它不会严格地在OP要求的多边形内。实际上，我认为你的方法适用于获取标记点，因为标记点可能比一个点大，甚至可能比多边形内所有空间都大。 - Adam Gawne-Cain

Answer 4

我不知道如何解决任何可能形状的问题（而且不进行重计算），但也许对于像你展示的这些简单形状，可以解决：

https://en.wikipedia.org/wiki/Force-directed_graph_drawing

启发式算法：经过一段时间后，这可能会趋向于一个合理的近似值。

- 将图形边界转换为许多点（点越多 = 更精确） - 从多个随机点开始放置在多边形内部 - 推动它们直到它们远离边界点最远，或者仅计算距离...(可以并行执行) - 取最佳点

另一种方法可能是根据形状的性质使用多种算法（例如另一个用于甜甜圈的算法...）。也可以依靠先测量“最胖”的部分吗？

在我看来，应该在数学论坛上询问此问题。

类似： 计算 SpatialPolygon 中心 类似： 如何找到两个最远的点？

- Christophe Roussy

Answer 5

为了获取标记点，我会使用Yves Daoust的方法。

为了获得可靠地“在任何带孔多边形内”的点，我会使用可靠的库（例如OpenGL的GLUtessellator）将多边形分割成三角形，然后获取面积最大的三角形的重心。

如果我有时间进行开发和测试，并且想要良好的性能，那么我会使用混合方法：首先使用Yves Daoust的方法获取一些候选点，然后测试候选点是否在多边形内。如果所有候选点都失败，则退回到更慢但可靠的方法（例如GLUtesselator）。

- Adam Gawne-Cain

Answer 6

for (int i = 0; i < n; /*++i*/) {
    p = RandomPointInsideConvexHull();
    if (IsInsidePolygon(p)) {
        ++i;
        d = DistanceToClosestEdge(p);
        if (d > bestD) {
            bestP = p;
        }
    }
}

运行此循环后，您将通过bestP近似解决方案。 n是要选择的参数。如果您想要更准确的结果，可以重新启动搜索，但现在不要选择多边形凸包内的点，而是可以选择邻近bestP的点，例如不超过bestD / 5（这次您不需要检查随机点是否在多边形内）。

- Yola

---

这个算法对于顶点众多但面积较小的多边形不适用，例如蜿蜒穿过山脉的细小赛道/公路的轮廓。问题在于，在凸包内随机选择的点很可能在多边形外部。在某些情况下，所有点都可能在多边形外部。 - Adam Gawne-Cain

@AdamGawne-Cain 请检查 i 的自增条件。尽管这不是您提到的多边形的最有效算法。 - Yola

你的方法好在可以在很多多边形中找到一个不错的点。但是 OP 需要适用于 "所有多边形" 的方法。如果输入的多边形是退化的（例如，面积为 0 的 L 形状，如 {0 0, 1 0, 1 1, 1 0, 0 0}），你的代码将永远运行下去。 - Adam Gawne-Cain

@AdamGawne-Cain 嗯...没错，但是面积为零的多边形没有点是严格“在”多边形内部的;) - Yola