How to determine if a point is within a quadrilateral

Question

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)

Keim

The points alone don't uniquely identify a quadrilateral, unless there's an additional constraint that it's convex, or that the points are defined in a given order. Does one or other of those constraints exist (if so, which)? – Anaphora

As an example, consider an equilateral triangle, with an additional point in the centre of the triangle. Just knowing the points doesn't allow you to know which edge of the triangle has been kinked in to meet the centre point. – Anaphora

Thanks, updated the problem to fix this. This should uniquely identify the quadrilateral. – Keim

Answer 1

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

Zampino

Answer 2

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

Tubercle

This actually works? Its blowing my mind! I'm trying to think of a scenario this wouldn't work. This would work for more than just quads too right?! Any shape. This is too awesome. – Janey

This is a wonderful solution, but it can be easily seen that this works only for convex quadrilaterals. – Seacock

May work in Matlab but other language comparing floating point numbers is fraught with rounding issues. Better to use to test if the point is on the same side of all the egdes. – Expend

Love this! It's simple, elegant, and simply elegant. – Hufford

Answer 3

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

Keister

Answer 4

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)

Philippa

Answer 5

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.

Ventage

This solution would only work for convex quadrilaterals. – Millenarianism

Answer 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.

Mckeever

I think this is correct for rectangles, but not all quadrilaterals. One of them will return negative in a quadrilateral with non-right angles, if the point is above/beside the diagonal. – Tarpon

Answer 7

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.

Disarray