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

tests.

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

http://www.wam.umd.edu/~zben