Determine if the two-dimensional point is inside the four-sided

Question

I am working on a JS program that I need to determine if the points are at the four corners in the coordinate system.

Can someone point me in response to an answer?

I look at what I call a convex quadrangle. That is, four symbolically randomly selected angular positions with all angles less than 180 °.

Thanks.

Answer 1

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

The second approach is to go around the polygon in order and for each pair of vertices v _i and v _{i + 1} (wrapping the first vertex if necessary), calculate the value (x - x _i ) * (y _{i + 1} - y _i ) - (x _{i + 1} - x _i ) * (y - y _i ). If these values ​​have the same sign, the point is inside the polygon. (These quantities are the Z-component of the transverse product of the vectors (v _{i + 1} - v _i ) and (p - v _i ). The condition that they all have the same sign coincides with the condition that p is on the same side ( left or right) of each rib.)

Both approaches must deal with the fact that the point is exactly on the edge or on the top. First you need to decide whether you want to count points such as those inside the polygon or not. Then you need to configure the tests accordingly. Keep in mind that small round-off errors can give a false answer anyway. This is just what you have to live with.

Since you have a convex quadrangle, there is another approach. Select any three vertices and calculate the barycentric coordinates of the point and the fourth vertex relative to the triangle formed by the three selected vertices. If the barycentric coordinates of the point are all positive and less and less than the barycentric coordinates of the fourth vertex, then the point is inside the quadrangle.

PS I just found a nice page here that lists quite a few strategies. Some of them are very interesting.

Answer 2

You need to use a winding or ray tracing method.

With winding, you can determine if any point is inside any shape constructed using line segments.

Basically, you take the cross-product of each line segment with a dot, and then add up all the results. How I did this to decide if the star was in the constellation, given the set of constellation lines. I see that there are other ways.

http://en.wikipedia.org/wiki/Point_in_polygon

There should be some code in several places.

Answer 3

It is much easier to see if a point is in a triangle.

Any quadrangle can be divided into two triangles.

If the point is in either of the two triangles that make up the quadrangle, then the point is inside the quadrangle.