How to determine if a point is within a quadrilateral

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.

开发者_Go百科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)

---

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

---

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

---

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)

---

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

---

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.

---

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.

---

The solution I used to solve this problem was to get the angle of P (in the diagrams the OP posted) for each of the 4 triangles it makes with each side of the quadrilateral. Add the angles together. If they equal (or nearly equal, depending on the error tolerance of the code) 360, the point is inside the quadrilateral. If the sum is less than 360, the point is outside. However, this might only work with convex quadrilaterals.