如何确定一个点是否位于矩形内？

Question

可能重复:
查找点是否位于矩形内

有一个采访问题,"如何确定一个点是否位于矩形内"

请注意,矩形也可以旋转.因此,检查矩形内部点的简单解决方案在这里不起作用......

请分享您对这个问题的看法..

我在互联网上找到了一个链接,并试图理解它,但失败了....请问这里的任何一个机构可以提供完整的计算机图形逻辑解决方案,因为我已经忘记了所有的基础知识.... 如何确定一个点是否在矩形内.

Answer 1

选择一个绝对在矩形之外的点.然后创建从该点到相关点的段.求解该段与构成矩形的段之间的交点的线性方程.如果您只得到一个交点,则该点位于矩形内.否则(0或2个交叉点),它在外面.

这对于基本上任何多边形来说都是微不足道的 - 奇数个交叉点意味着该点在多边形内部,偶数表示它在外面.

编辑:可能不是很明显,所以我要强调我们在矩形(多边形)之外选取的点完全是任意的.我们可以选择我们想要的任何点,只要我们确定它在多边形之外.为了使我们的计算变得容易,我们通常做的是选择(P _x,无穷大)(其中P _x是我们正在测试的点P的x坐标) - 也就是说,我们正在创建的基本上是垂直射线.这简化了测试,因为我们只需要针对一个端点进行测试以找到交叉点.它还简化了线性方程的求解,使其几乎无法识别为求解线性方程.我们真的只需要计算P _x处线的Y坐标,看它是否大于P _y.因此,求解线性方程分解为:

1. 检查该X值是否在该段的X值范围内
2. 如果是,则将X值插入线的等式中
3. 测试得到的Y值是否大于P _y

如果那些通过,我们有一个交叉点.另请注意,测试可以并行执行(如果我们在像GPU这样的并行硬件上执行此操作,则会很方便).

Answer 2

对于凸多面体,在N维中工作的简单解决方案,其中二维矩形是​​一种特殊情况:

1. 将多面体表示为半空间的交集,每个半空间由单位法向量和表面超平面与法线沿原点的距离定义.
2. 对于这些半空间中的每一个,将所讨论的点的点积与定义的法向量相乘.当且仅当点积小于[或等于]定义距离时,该点在半空间中.
3. 该点位于多面体内部,当且仅当它位于每个半空间中时.

对于定义为逆时针序列边缘的矩形,步骤1相当于顺时针旋转边缘90度以获得法线,然后将法线与包含边缘的线相交以找到到原点的距离.

假设步骤1完成,测试一个点最多需要8次乘法,4次加法和4次比较.

如果你愿意,你可以稍微优化一下这个过程,因为你有矩形(因此相对的边有相反的法线).现在你只看到2个法线而不是4个,以及一系列点积值,它们表示位于相对边之间的点.所以现在你需要4次乘法,2次加法和4次比较.

如果您做的第一个测试显示该点在矩形之外,您也可以获得幸运,在这种情况下,它只需要2次乘法,1次加法和1-2次比较.

Answer 3

这远非最佳解决方案...但是，如果您有连续顺序的点，请将它们称为a, b, , c，并且带有 x 和 ay 字段，您可以使用您的点与每个连续点d之间的向量的叉积p对。

如果你总是得到相同的结果符号（即全部为正或全部为负），那么你就在矩形内；否则，你就在外面了。