Determine if a 2D point is within a quadrilateral

Question

I'm working on a JS program which I need to have determine if points are within four corners in a coordinate system.

Could somebody point me in the direction of an answer?

I'm looking at what I think is called a convex quadrilateral. That is, four pretty randomly chosen corner positions with all angles smaller than 180°.

Thanks.

Answer 1

There are two relatively simple approaches. The first approach is to draw a ray from the point to "infinity" (actually, to any point outside the polygon) and count how many sides of the polygon the ray intersects. The point is inside the polygon if and only if the count is odd.

The second approach is to go around the polygon in order and for every pair of vertices v_i and v_i+1 (wrapping around to the first vertex if necessary), compute the quantity (x - x_i) * (y_i+1 - y_i) - (x_i+1 - x_i) * (y - y_i). If these quantities all have the same sign, the point is inside the polygon. (These quantities are the Z component of the cross product of the vectors (v_i+1 - v_i) and (p - v_i). The condition that they all have the same sign is the same as the condition that p is on the same side (left or right) of every edge.)

Both approaches need to deal with the case that the point is exactly on an edge or on a vertex. You first need to decide whether you want to count such points as being inside the polygon or not. Then you need to adjust the tests accordingly. Be aware that slight numerical rounding errors can give a false answer either way. It's just something you'll have to live with.

Since you have a convex quadrilateral, there's another approach. Pick any three vertices and compute the barycentric coordinates of the point and of the fourth vertex with respect to the triangle formed by the three chosen vertices. If the barycentric coordinates of the point are all positive and all less than the barycentric coordinates of the fourth vertex, then the point is inside the quadrilateral.

P.S. Just found a nice page here that lists quite a number of strategies. Some of them are very interesting.