2

有没有办法在多边形中找到一个点？我不想找到一个点是否在多边形中，但想找到内部点本身。我尝试使用 x 坐标的平均值和 y 坐标的平均值来获得多边形的质心，但这不适用于某些多边形的情况，例如以下质心在外面的多边形。

在此处输入图像描述

4

7 回答 7

0

假设您有一个具有 n 个顶点的多边形 where V_n = (x_n,y_n)，您可以这样做：

  1. 计算点A = (max(x_n),max(y_n))和B = (min(x_n),min(y_n))。检查两个点是否实际上是顶点，如果不是继续下一步，但如果两个点都是顶点，则取点C = (max(x_n),min(y_n))代替D = (min(x_n),max(y_n))。
  2. 将线AB（或CD）与多边形相交（即与每条边相交并测试每个顶点是否位于该线上）。
  3. 对于您在上一步中获得的所有点，计算它们到A（或C分别）的距离，通过增加到的距离对它们进行排序A。
  4. 从最接近 A 的点开始（如果 A 是顶点，则为 A 本身），在该点和下一个最近点之间选择一个点。测试该点是否在多边形内。如果是你完成了，如果不是，重复这个步骤到下一个点（这是你最后一次迭代的第二个点）。

解释

矩形ACBD是多边形的轴对齐边界框，因此多边形内的每个点也将在该矩形内。AB并且CD是该矩形的对角线。

在第 1 步中，我们检查两个点是否都是顶点，这很重要A。B如果其中一个不是，我们可以确定多边形的至少一个顶点在对角线“上方”，并且至少有一个顶点在“下方”，因此对角线将与多边形相交。

如果两个点都是顶点，我们可以处理一个三角形，其中对角线实际上是一条边或一个完全位于对角线一侧的凹多边形，因此我们只需切换对角线并保证另一条对角线将与多边形。

因为我们知道我们的对角线与多边形相交，所以我们可以遍历所有线段并从每个线段中选择一个点来查看它是否在内部，其中一个必须是。通常它将是您测试的第一条线段，但有一些特殊情况可能导致该线段位于多边形之外（同样：凹多边形并且您的第一个交点是顶点而不是边），但至少有一个段必须在里面。

我认为这可以更有效地完成，但如果 n 足够小并且您不需要为大量多边形这样做，那么应该没有问题。

于 2016-03-27T21:58:11.723 回答
0

很晚才到达这个问题，但这里记录了一种方法

  1. 识别一个凸顶点v；令其相邻顶点为 a 和 b。
  2. 对于彼此的顶点 q 做：2a。如果 q 在 avb 内，则计算到 v 的距离（与 ab 正交）。2b。如果距离是一个新的最小值，则保存点 q。
  3. 如果内部没有点，则返回 ab 的中点或 avb 的质心。
  4. 否则，如果某个点在内部，则 qv 是内部的：返回它的中点。

我在这里编写了一个 javascript 版本

希望能帮助到你！

于 2020-06-12T13:30:34.777 回答
0

如果没有完整的算法，您可以执行以下操作：

假设我有一个按顺时针顺序添加到点的多边形：

    p.addPoint(100, 200);
    p.addPoint(200, 100);
    p.addPoint(160, 200);
    p.addPoint(200, 300);
    for(i=0; i<p.npoints; i++) {
      int[] p0={p.xpoints[i], h-1-p.ypoints[i]}, p1={p.xpoints[(i+1)%p.npoints], h-1-p.ypoints[(i+1)%p.npoints]}, p2={p.xpoints[(i+2)%p.npoints], h-1-p.ypoints[(i+2)%p.npoints]};
      System.out.println(" angle "+angle(p0, p1, p2));
    }

即取三个连续的点并确定角度 p0, p1, p2（按此顺序 p1 是角的角）当边 p2-p1 转身与边 p0-p2 以顺时针顺序相交时）：如果小于大于 180 度，它是一个凸角，您可以在其中得到一些点（例如，取两侧的中点并找到它们连接线的中点等）

如果超过180继续。

angle() 是一种求角度的方法。

如果要将坐标转换为通常的几何系统，则需要 h-1-p[]（h 是窗口的高度）；否则不要使用它。

总之：找到一个凸角，无论是使用角度方法还是其他方法。

于 2016-03-28T19:18:53.450 回答
0

找到多边形内的任何非特定点非常容易。您需要知道多边形的缠绕顺序（顺时针或逆时针） - 这决定了哪个是内部，哪个是多边形的外部。就是这样：

  1. 使用剪耳法找到一个三角形（“耳朵”）。
  2. 找到那个三角形的中点。

我可以在这里准确地重现它是如何工作的，但它已经有很好的记录了，只需使用维基百科链接并搜索有关多边形三角剖分的耳朵剪裁的更多信息。

于 2016-03-27T22:27:06.550 回答
0

我相信这可以仅使用基本几何（没有三角测量、剪耳等）并在 $O(n)$ 时间内完成，至少在多边形很简单的情况下是这样。

选择多边形的任意三个连续顶点 $A$、$B$、$C$，然后查看 $B$ 处的角。这个角（假设 $B$ 是一个简单的顶点）将多边形的内部与外部分隔开来，如果您知道多边形的方向（如果不知道，则很容易计算），您就知道哪一边是哪个。

这个角的平分线由垂直于$(CA)$的向量支撑；如果你的多边形是逆时针的，那么向量 $i(CA)$ 指向多边形内部，否则 $-i(CA)$ 指向内部（为了简单起见，这里使用复数）。这意味着，对于任何足够小的 ε，$P = B+ε i(CA)$ 位于多边形内。

这里，“足够小”只是意味着线段$BP$不穿过多边形的任何其他边，因此只需选择小于$B$与多边形任何其他边之间的最小距离的ε（即，除了$AB$ 和 $BC$)，除以 $AC$ 的范数。（这是算法的 $O(n)$ 部分）。

于 2021-10-18T08:30:52.307 回答
0

可能有更有效的方法。但解决问题的一种方法是将其分解为多个部分：

  1. 将多边形三角化为一组三角形。这总是可能的。例如，参见 de Burg 的“计算几何”一书（第 2 版，第 3 章）。

在您的示例中，多边形显然可以分解为两个三角形。

  1. 选择任何组件三角形的中心。三角形的中心在三角形内部，因此在原始多边形内部。

中心

于 2016-03-27T21:37:16.440 回答
-1

这更像是一个数学问题而不是编码，但你应该尝试这样的事情

从该点开始一条射线，您检查该射线与多边形相交的次数。如果它甚至点在多边形之外

于 2016-03-27T21:32:53.997 回答