如何确定一个点是否在四边形内

Question

goal 我想确定测试点是否在定义的四边形内。我可能会在MATLAB中实现该解决方案，因此我只需要伪代码。

输入

四边形的角：（x1，y1）（x2，y2）（x3，y3）（x4，y4）

测试点：（XT，YT）

输出

1-如果在四边形内

0-否则

update

指出，识别四边形的顶点不足以唯一识别它。您可以假设点的顺序确定四边形的侧面（点1连接2、2连接到3、3连接到4、4连接到1）

仅用于凸四边形：

Answer 1

使用。用法将是

inpolygon

Answer 2

中的classic

Classicpoint以实现。否则做雅各布的建议。

由于这是一个简单的四边形，您可以在三角形中测试一个三角形的点，而中间的矩形矩形点。 Edit

这是三角形中点的一些伪代码：

Answer 3

inpolygon(xt,yt,[x1 x2 x3 x4],[y1 y2 y3 y4])

或使用Barycentric技术： a，b和c是三角形终点，p是正在测试的点

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

Answer 4

用来安排给定的坐标。 （x1，y1）=最右边的坐标 （x2，y2）=上坐标 （x3，y3）=最左边的坐标 （x4，y4）=最多的坐标

您可以做以下操作：

// 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)

Assume

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.

是四边形的顶点，是重点。 如果

A,B,C,D

在四边形内部，则所有点产物the和

P

将是正的。 如果

P

在四边形以外，则至少其中一种将为负。

Answer 5

我用来解决此问题的解决方案是为其在四边形的每一侧制作的四个三角形中的每个三角形中的每一个。将角度添加在一起。如果它们相等（或几乎相等，具体取决于代码的误差）360，则点在四边形内。如果总和小于360，则点在外面。但是，这可能仅适用于凸四边形。