目标
我想确定一个测试点是否在一个定义好的四边形内。我的实现可能会用Matlab，所以我只需要伪代码。
输入
四边形的四个角落坐标：(x1,y1) (x2,y2) (x3,y3) (x4,y4)
测试点坐标: (xt, yt)
输出
1 - 如果在四边形内
0 - 否则
更新
有人指出，仅仅识别四边形的顶点是不足以唯一确定四边形的。你可以假设这些点的顺序决定了四边形的边（第1个点连接着第2个点，第2个点连接着第3个点，第3个点连接着第4个点，第4个点连接着第1个点）。
如何确定一个点是否在四边形内部
21
- slykat
3
6除非有额外的限制条件，如四边形是凸的或者点按照给定顺序定义，否则仅通过点无法唯一确定一个四边形。那么这两个限制条件中的其中一个存在吗？如果存在，是哪一个？ - Damien_The_Unbeliever
1以等边三角形为例，三角形中心有一个额外的点。仅仅知道这些点并不能让你知道哪条边被弯曲以满足中心点。 - Damien_The_Unbeliever
谢谢，已更新问题以解决此问题。这应该能唯一地识别四边形。 - slykat
7个回答
54
你可以使用此条件测试 Point。同时，你可以将四边形看作两个三角形来计算其面积。
- mili
4
9这真的可行吗？这让我大开眼界！我在试图想象一种这种方法不适用的情况。这种方法不仅适用于四边形，对于任何形状都适用，是吗？太棒了！ - Kaliber64
16这是一个很好的解决方案，但很容易看出它只适用于凸四边形。 - Ken Y-N
1可能在Matlab中可以工作，但是使用其他编程语言比较浮点数会存在四舍五入问题。最好使用测试来确定该点是否位于所有边的同侧。 - JamesP
1喜欢这个！它简单、优雅，而且非常优雅。 - VirxEC
2
由于这是一个简单的四边形，您可以对每个端点进行三角形点测试，并对中间点进行矩形点测试。
编辑 这里是一些点在三角形内的伪代码：
function SameSide(p1,p2, a,b)
cp1 = CrossProduct(b-a, p1-a)
cp2 = CrossProduct(b-a, p2-a)
if DotProduct(cp1, cp2) >= 0 then return true
else return false
function PointInTriangle(p, a,b,c)
if SameSide(p,a, b,c) and SameSide(p,b, a,c)
and SameSide(p,c, a,b) then return true
else return false
或者使用重心法技术：
A、B和C是三角形的顶点，P是测试点。
// Compute vectors
v0 = C - A
v1 = B - A
v2 = P - A
// Compute dot products
dot00 = dot(v0, v0)
dot01 = dot(v0, v1)
dot02 = dot(v0, v2)
dot11 = dot(v1, v1)
dot12 = dot(v1, v2)
// Compute barycentric coordinates
invDenom = 1 / (dot00 * dot11 - dot01 * dot01)
u = (dot11 * dot02 - dot01 * dot12) * invDenom
v = (dot00 * dot12 - dot01 * dot02) * invDenom
// Check if point is in triangle
return (u > 0) && (v > 0) && (u + v < 1)
- SRM
1
假定给定的坐标已按以下方式排列：
(x1，y1) = 最右侧坐标
(x2，y2) = 最上方坐标
(x3，y3) = 最左侧坐标
(x4，y4) = 最底部坐标
你可以执行以下操作：
1. calculate the 4 lines of the quadrilateral (we'll call these quad lines)
2. calculate 4 lines, from the (xt, yt) to every other coordinate (we'll call these new lines)
3. if any new line intersects any of the quad lines, then the coordinate is outside of the quadrilateral, otherwise it is inside.
- Gal
1
1这个解决方案只适用于凸四边形。 - Lee.J.Baxter
1
假设四边形的顶点为 A、B、C、D，点 P 为任意一点。
若点 P 在四边形内，则所有点积 dot(BP,BA)、dot(BP,BC)、dot(AP,AB)、dot(AP,AD)、dot(DP,DC)、dot(DP,DA)、dot(CP,CB) 和 dot(CP,CD) 都是正数。
若点 P 在四边形外，则至少有一个点积是负数。
- John Prospathopoulos
1
我认为这对于矩形是正确的，但并不适用于所有四边形。如果点在斜线上方/旁边，并且四边形具有非直角，则其中一个将返回负值。 - Opieus
0
我用来解决这个问题的方法是获取P的角度（在OP发布的图表中）与四边形的每条边组成的四个三角形。将这些角度相加。如果它们等于360（或接近360，取决于代码的误差容限），则该点位于四边形内部。如果总和小于360，则该点位于外部。然而，这种方法可能只适用于凸四边形。
- Darren Eriksen
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接