How to determine if a point is within a quadrilate

问题:

Goal

I want to determine if a test point is within a defined quadrilateral. I'm probably going to implement the solution in Matlab so I only need pseudo-code.

Inputs

Corners of quadrilateral : (x1,y1) (x2,y2) (x3,y3) (x4,y4)

Test point : (xt, yt)

Output

1 - If within quadrilateral

0 - Otherwise

Update

It was pointed out that identifying the vertices of the quadrilateral is not enough to uniquely identify it. You can assume that the order of the points determines the sides of the quadrilateral (point 1 connects 2, 2 connects to 3, 3 connects to 4, 4 connects to 1)

回答1:

Use inpolygon. Usage would be inpolygon(xt,yt,[x1 x2 x3 x4],[y1 y2 y3 y4])

回答2:

You can test the Point with this condition. Also you can treat quadrilateral as 2 triangles to calculate its area.

回答3:

Since it's a simple quadrilateral you can test for a point in triangle for each end and a point in rectangle for the middle.

EDIT Here is some pseudo code for point in triangle:

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

Or using Barycentric technique:

A, B, and C are the triangle end points, P is the point under test

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

回答4:

assuming you the given coordinates are arranged s.t. (x1,y1) = rightmost coordinate (x2,y2) = uppermost coordinate (x3,y3) = leftmost coordinate (x4,y4) = botoom-most coordinate

You can do the following:

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.

回答5:

If the aim is to code your own test, then pick any classic point in polygon test to implement. Otherwise do what Jacob suggests.

回答6:

Assume A,B,C,D are the vertices of the quadrilateral and P is the point. If P is inside the quadrilateral then all dot products dot(BP,BA), dot(BP,BC), dot(AP,AB), dot(AP,AD), dot(DP,DC), dot(DP,DA), dot(CP,CB) and dot(CP,CD) will be positive. If P is outside the quadrilateral at least one of these products will be negative.