javascript - 如何判断两个多边形相同？

Question

我有一个多边形，它有五个这样的点:

然后我将另一个点添加到多边形(红色点):

确定两个多边形相同的算法是什么(不仅 Angular/长度相同，坐标也相同)。

Answer 1

因为你的相同意味着相同的形状、大小、方向和位置

• 那就很简单了
• 你有 2 个定义为点集的多边形
• A={ a0,a1...a(n-1) }和 B={ b0,b1,...b(m-1) }

对于初学者，我假设你没有过采样(线总是 2 点不多)

1. 比较 m,n

   • 如果不相等的形状不同那么停止
   • 否则m==n所以我将只使用 n从现在开始

2. 查找 (a(i)==b(j))其中 i,j=<0,n)

   • 如果多边形不是从同一点开始，则需要这样做
   • 否则i=0,j=0
   • 对于复杂(自相交)的形状，您需要找到独特的点
   • (不重复，或下一个点相同的重复次数)
   • 否则只需设置i=0并找到 j单O(n)循环
   • 如果没有找到公共(public)点停止(不相同的多边形)

3. 比较点

       for (k=0;k<n;k++)
        {
        if (a(i)!=b(j)) return false; // not the same
        i++; if (i>=n) i=0;
        j++; if (j>=n) j=0;
        } return true; // are the same
   

   • 可以这样进行点比较if (|a(i)-b(j)|>=max_difference_treshold)
   • 无需比较 sqrt-ed 距离，阈值可以由 2 取而代之
   • 我通常使用像 1e-6 这样的东西或 1e-10值(value)观

对于过采样的多边形，您需要先对摊位 A、B 的点进行重新采样

• 取 3 个相邻点 p(i-1),p(i),p(i+1)
• 计算 2 对之间的 dx,dy
• d1=p(i)-p(i-1); dx1=p1.x; dy1=p1.y;
• d2=p(i+1)-p(i); dx2=p2.x; dy2=p2.y;
• 如果(dx1*dy2==dx1*dy1)然后删除p(i)从集合
• 你应该在此之前分别处理零个案例(任何 dx,dy 为零)