6

确定一个点是否在平行四边形/菱形内最快的方法是什么？

4

9 回答 9

16

再次嗨，感谢您的所有回答。与此同时，我自己想出了一些我认为会相当快的东西：

想象一下，我们有一个由 PQ 和 PR 跨越的平行四边形，其中 PQ 和 PR 是向量（P、Q 和 R 是角）。此外，我们还有要检查的点，称为 A。

我们知道向量 PA 可以拆分为平行于 PQ 和 PR 的两个向量：

PA=n*PQ+m*PR

现在我们知道 n 和 m 必须在区间 [0; 1]，我们求解n和m：

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

其中 det(PA, PQ) 是向量 PA 和 PQ 的行列式：

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

如果点 A 在平行四边形内，则 0<=n<=1 和 0<=m<=1，这给了我们伪代码：

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}
于 2009-08-02T09:42:49.467 回答
5

想象一下从你的点向一个方向发出的光线。如果该光线多次穿过形状的线条，则它在形状内部。如果它穿过偶数次，它就在形状之外。

因此，在您的程序中，您只需创建一条不可见的线并查看它交叉的频率。我想，Actionscript 可能有一个内置函数来执行此操作。

现在，如果您有大量对象并且点只能在一个中，您可以通过使用二进制空间分区来存储对象的位置来加快速度。这样，您不必将您的点与每个对象进行比较，只需将其与附近的对象进行比较。

于 2009-08-01T22:03:54.417 回答
2

请参阅我对这个问题的回答，这非常相似。在那里，我给出了我认为在平行四边形有一个角的情况下非常简单的测试，(0,0)因为它使解释更容易理解，但修改它以使其一般工作并不难。

编辑：由于问题所有者熟悉向量，我基本上会用那种语言重写我的答案。假设平行四边形由向量PQ和组成PR，其中P、Q和R是角。该符号*将表示点积。选择一个垂直于(ie ) 和(q例如，您可以通过旋转90 度得到) 的点。也选择一个点，这样和。那么一个点在内部当且仅当。PQPqPq*PQ=0PR*Pq>0qQPrPR*Pr=0PQ*Pr>0A(0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR)

于 2009-08-01T22:31:46.327 回答
1

本文介绍了一种确定光线和四边形相交位置的方法。如果四边形是平行四边形，则可以进一步简化。

如果您有一个由向量​​ AB和AC描述的相邻边的平行四边形。平行四边形平面上的任何一点都可以用下面的向量来描述

T(a, b) = A + a * AB + b * AC

任何射线都可以描述为原点O和方向D

R(t) = O + t * D

2的交点是什么时候T(a, b) == R(t)

O + t * D = A + a * AB + b * AC

解决这个问题a并b检查它们是否都在 0 和 1 之间。请参阅本文末尾的伪代码以了解如何实现它。

于 2009-08-03T11:55:26.530 回答
0

我对这个问题的第一个观察是矩形（与轴对齐）是一个简单的退化案例。如果该矩形的两个角是：(x1,y1) 和 (x2,y2)，那么您只需测试，给定一个点 (x3,y3)，min(x1,x2) < x3 < max(x1,x2) 和最小（y1，y2）< y3 < 最大（y1，y3）。

这也可能是一个有用的优化。如果我们找到平行四边形的轴对齐边界矩形，那么我们可以开始快速测试任何给定点。

如果我们的平行线具有非零斜率，那么我们计算边界线的轴交点以及在这些斜率处通过相关点的线的交点。如果我们的两个点的交点（由两个斜率定义）都位于边界线的交点之间，那么我们就在其中。如果其中任何一个不在这些范围内，那么我们不在。

我没有时间编写示例，但计算这些斜率和交叉点是第一年的代数。

[附加物]

我现在看到第一篇文章（关于从要测试的点发出的光线并沿任意斜率延伸）是对任何封闭平面多边形的该问题的一般解决方案的参考......或者实际上，对于任何封闭平面曲线。它也可以扩展到封闭曲面的三个维度。

然而，有一个警告适用于平行四边形或菱形。在凹多边形（或其他一些曲线）的情况下，如果光线击中任何顶点（角），那么测试可能会返回偶数个“线”交叉点。换句话说，同时包含在多边形的多个“边”中的“曲线”的任何部分都可能返回误报。

两种解决方案是：显式测试线段限制（角/顶点）处的交叉点，或将每个线段视为一端以（点 + epsilon）为界（这样我们的计算将找不到任何共同点）任意两侧）。

我找到一个边界矩形的想法仍然是一个有用的快速测试，并且通常扩展到所有多边形。我们找到 min() 和 max() x 来找到左右边界，而 min() 和 max() y 来找到上下边界。这也可以扩展到三个维度……一位朋友告诉我，标准图形库在大多数虚拟现实和 MMORPG 等中广泛使用它进行碰撞检测。当在边界框中找到碰撞时，它们会进行更细粒度的计算在其中包含的多边形上。

于 2009-08-01T22:51:31.090 回答
0

一条线的标准方程为 ax+bx+c=0 .. 但有趣的是，如果您采用该表达式 ax+bx+c，并在给定特定线的 a,b,c 的情况下计算点 x,y，你会发现表达式将平面分成两半，一半在表达式大于零的位置，另一半在小于零的位置。

现在，如果您取平行四边形的四个点，并计算构成平行四边形一侧的每条线的 a、b、c 系数，您可以计算所讨论 x、y 的每个表达式并找出哪一侧该点所在的每一行。平行四边形的内部将是特定边的逻辑与。

即，一旦您拥有四行中的每一行的 a、b、c，您就可以进行类似 的测试 

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

.. 唯一剩下的技巧是您必须确定每个符号测试的“极性”，即大于或小于零。执行此操作的简单方法是评估 0,0，并查看它是否在您想要的一侧，这相当于说“c”的符号告诉您测试哪种方式。

诚然，这是一种蛮力的方法，但它可以扩展为适用于任何凸多边形......或者，删除一个点，它也适用于三角形。

于 2009-08-02T01:12:27.670 回答
0

如果平行四边形是凸的（并且给定平行四边形的定义，它必须是 xD），那么任何测试它是否在其边界内的算法都应该这样做，您可以提高展开循环的效率，因为您知道只有 4 个顶点，例如.

这是一个简单的算法，它基于矢量乘积的右手规则来测试所有线段的同一侧的点（您也可以通过用简单的符号测试替换除法以对矢量进行归一化来优化它）：

如何测试一个点是否在二维整数坐标中的凸多边形内？

另一种选择，如果您要对同一个平行四边形进行大量比较，则将其归一化为正方形，获取进行转换的矩阵，每次获得要测试的点时，将其乘以矩阵，然后检查如果转换点在归一化正方形内（这应该更容易）。

于 2009-08-03T12:07:51.927 回答
0
  1. 获取多边形的轮廓
  2. 检查点是否在计数中

dist1 = cv2.pointPolygonTest(contours[0], (50, 70), True)

dist 返回以下三个之一：

  • 如果点在轮廓内，则为正值
  • 如果点在轮廓之外，则为负值
  • 如果点在轮廓上，则为零

如何检查点是否位于轮廓内？

于 2019-03-15T11:38:47.477 回答
-1

y 坐标是最简单的，所以从它开始。如果该点的 y 坐标在形状的顶部和底部之间，则继续到 x 坐标。在该点的y坐标处计算形状左右两侧的x坐标，并检查该点的x坐标是否在它们之间。

编辑：

给定左上角、右上角、右下角和左下角的四个坐标：

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}
于 2009-08-01T22:10:13.063 回答