平行四边形包含Point

Question

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

Answer 1

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

想象一下,我们有一个由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
}

Answer 2

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

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

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