Yow! The algorithm I gave for insidedness testing only works if:
1. The quadrilateral is non-self-intersecting
2. The quadrilateral is convex (i.e. non-concave)
I think 1 is reasonable but 2 makes it a lot weaker.
You could always split the quad into two triangles,
which are GUARANTEED to be convex, then use the same
algorithm. Be careful where you split it though.
For a quad there can be only one trio of vertices
where it is concave, you want the middle vertex to
be one of the endpoints of the splitting line segment.
WLOG you can walk around the polygon in either direction
starting from any point, looking for monotonicity in
the deflection angle. If it is monotonic the figure is
convex, if it changes sign there is an adjacent concavity
but I cannot see any better way than walking the entire
polygon and summing the deflection angles to find out
which sense the polygon is -- if the total is a multiple
of +360 degrees it is one sense, -360 degrees the other.
If the sense turns out to be backwards you can walk the
other way or invert all your tests.
To find a point to characterize inside/outside for
each segment you should be able to use an average
point, that is, a point whose x coordinate is the
average of the x coordinates of the vertices and
whose y coordinate is the average of the y coordinates
of the vertices.
Testing for self intersection is probably a n^2
problem which means you'd have to make 4*3 = 12
My old computer graphics teacher (to whom I spoke about this)
suggests a heirarchical triangulation using the same kind of
sidedness tests that could test in log(n) time for large
numbers of vertices. He also mentions an algorithm based
on the total angle swept by a line from the test point to
each of the vertices in turn. This algorithm is attributed
to Randloph Franklin.
Charles B. (Ben) Cranston