平行四边形包含Point

问题描述 投票：3回答：9

决定一个点是否在平行四边形/菱形内部的最快速度是什么？

actionscript-3 performance math mathematical-optimization
9个回答
12
投票

嗨再次感谢您的所有答案。与此同时，我自己想出了一些我觉得会很快的东西：

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

我们知道Vector 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
}
5
投票

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

因此，在您的程序中，您只需创建一条不可见的线，并查看它经常穿过的频率。我想，Actionscript可能有一个内置函数来做到这一点。

现在，如果你有大量的物体并且这个点只能在一个物体中，你可以通过使用Binary Space Partition存储物体的位置来加快速度。这样，您不必将您的点与每个对象进行比较，只需将它们与附近的对象进行比较即可。

2
投票

请参阅我对this question的回答，这非常相似。在那里，我给出了我认为非常简单的测试，因为平行四边形在(0,0)上有一个角落，因为它使解释更容易看，但是修改它一般都不是很难。

编辑：由于问题所有者熟悉向量，我基本上会用该语言重写我的答案。假设平行四边形由矢量PQ和PR跨越，其中P，Q和R是角。符号*将表示点积。选择一个点q使得PQ垂直于Pq（即Pq*PQ=0）和PR*Pq>0（例如，你可以通过将q围绕Q旋转90度来获得P）。也选择一点r，使PR*Pr=0和PQ*Pr>0。然后一个点A在内部，当且仅当(0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR)。

1
投票

这个paper描述了一种确定射线和四边形相交的方法。如果四边形是平行四边形，则可以进一步简化。

如果您有一个平行四边形，其中相邻边由矢量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之间。请参阅本文末尾的伪代码以了解如何实现它。

0
投票

一条线的标准方程式给出为ax + bx + c = 0 ..但有趣的是，如果你取这个表达式ax + bx + c，并评估点x，y给出你的特定线的a，b，c，你会发现表达式将平面分成两半，一半表达式大于零，另一半表示较小。

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

即，一旦你有四条线中的每条线的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'的符号告诉您要测试哪种方式。

不可否认，这是一种蛮力的方式，但它可以扩展到任何凸多边形..或者，删除一个点，它也适用于三角形。

0
投票

我对这个问题的第一个观察是一个矩形（与轴对齐）是一个简单的退化情况。如果该矩形的两个角是：（x1，y1）和（x2，y2）那么你只需测试一个点（x3，y3），即min（x1，x2）<x3 <max（x1，x2）和min（y1，y2）<y3 <max（y1，y3）。

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

如果我们的平行线具有非零斜率，那么我们计算我们的边界线的轴线交点以及将在这些斜坡处穿过所讨论的点的线的交点。如果我们的两个点的交叉点（由两个斜率定义）位于我们的边界线的交点之间，那么我们就进入。如果其中任何一个超出这些范围，那么我们就不是。

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

[附加物]

我现在看到第一个帖子（关于来自待测点和沿任意斜率延伸的光线）是对任何闭合平面多边形的这个问题的一般解决方案的参考...或者，事实上，对于任何封闭的平面曲线。对于封闭表面，它也可以扩展到三维。

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

这样做的两个解决方案是：明确测试线段限制（角点/顶点）处的交叉点，或者将每个线段视为一端由（点+ epsilon）限制（这样我们的计算将找不到任何点之间的共同点）任何双方）。

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

0
投票

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

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

How to test if a point is inside of a convex polygon in 2D integer coordinates?

另一种选择，如果你要对相同的平行四边形进行大量的比较，就是将它标准化为一个正方形，获得进行变换的矩阵，每次得到一个测试点，将其乘以矩阵，然后检查如果变换点在标准化方块内（这应该更容易）。

0
投票
  1. 获取多边形的轮廓
  2. 检查点是否位于轮廓中

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

dist返回以下三个中的一个：

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

How to check if point is placed inside contour?

-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
     }
   }
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.