Return true if a point is within a quadrilateral.

[someonerules]

I need to write an if statement (or more) to return either true if a point is inside of a quadrilateral else return false. My quadrilateral can can be in ANY shape or size, not just square, and that's where my problem occurs. However the lines cannot cross, if that helps. I have attempted to come up with a formula, but I have had no luck. I'm not too great with geometry and such, soo... I would be grateful for any help!

[691175002]

Without seriously delving into possible solutions, my first suggestion would be to use a convex hull algorithm and make sure the target point is not one of the bounds.
http://en.wikipedia.org/wiki/Convex_hull
http://en.wikipedia.org/wiki/Convex_hull_algorithms

I know there are also better ways to do this, such as linear inequalities, however the convex hull algorithms are well documented.

[someonerules]

Hmm...I read through those documents, and I must say...what? I somewhat understand what they are saying...but I don't really know how to use what I read to help me...

[realMakc]

another simple solution is to cast a ray out and count intersections with bounding line (if you do have this line). count % 2 will give 0 if outside, and 1 if inside.

[TechNoiZ]

Not done the code for it but something like;

for quad abcd and point X within;

angle(Xdc) < angle(adc) AND angle(Xba) < angle(cda)

OR

The point X must be within the 'lightcones' of two opposite points of the quadrilateral formed by the two adjacent sides to the point; either b and d (as above) or a and c.

[691175002]

Id have to say that TechNoiZ solution is the best one so far.

[realMakc]

mine requires less computations and in fact works for any concave polygon with holes.

[realMakc]

ok, it turned out not so simple it is all just +/- and >/==, no atan-s etc, but code gets very hairy... I will soon release it (after I catch all bugs) along with tesselation (which I needed it for (sort of)), so keep an eye on my rss.

[someonerules]

Wow! Thats really cool! How did you do that?

[JerryScript]

I'm not sure if it would be faster, but you could check parametric coordinates to insure the point is within one of the two triangles making up the quadrilateral. I use this method for ray/triangle (3d mesh) intersection checks, and it's 100% accurate, and pretty fast.

[realMakc]

actually js is right, you could use any triangle hittest, if you split quadrilateral along inner diagonal... but there a problem remains, how would you test that diagonal is inside?

[JerryScript]

hmm, isn't the shortest diagonal always inside? I'm thinking so in my minds eye, but I don't know if it's true.

[realMakc]

* * * * * *

[JerryScript]

ahh, thanks for the correction

[rachil0]

If you know your quadrilateral (or any N-gon) is convex, if you can use four (or N) cross products to determine if the test point is in the positive or negative halfspace of each edge.

If you can't guarantee the quadrilateral is convex, split it into the union of two triangles, and then do insideness tests for each triangles (which are 3-gons and guaranteed convex).

Like makc's picture, there can be a right and wrong way to split a nonconvex quadrilateral. If you do it wrongly, one of the triangles will wind/circulate with the wrong handedness. So after you split, test that both triangles have the same circulation as the original quad (this is just more cross products).