If they are all co-planar checking is relativels straightforward. I'm assuming they lie on the xy plane...
This is crude and inefficient but should work (I think)
1) Break all quads into tris
2) Round all points to a fine grid (eg. 0.25LDU)
3) Cycle through all tris:
3a) Each tri has three points (x1,y1) (x2,y2) and (x3,y3)
Calculate u1=x2-x1, v1=y2-y1, u2=x3-x1, v2=y3-y1
Calculate det=v2*u1-v1*u2
3b) Cycle through all other points (x,y)
3ci) Set a=[v2*(x-x1) - v1*(y-y1)]/det, b=[u1*(y-y1) - u2*(x-x1)]/det
3cii) if (a>0) && (a<1) && (b>0) && (b<1) && (abs(a)+abs(b)<1)
then the two tris overlap
I'm fairly sure that should work although I may have made a slight error.
Tim
This is crude and inefficient but should work (I think)
1) Break all quads into tris
2) Round all points to a fine grid (eg. 0.25LDU)
3) Cycle through all tris:
3a) Each tri has three points (x1,y1) (x2,y2) and (x3,y3)
Calculate u1=x2-x1, v1=y2-y1, u2=x3-x1, v2=y3-y1
Calculate det=v2*u1-v1*u2
3b) Cycle through all other points (x,y)
3ci) Set a=[v2*(x-x1) - v1*(y-y1)]/det, b=[u1*(y-y1) - u2*(x-x1)]/det
3cii) if (a>0) && (a<1) && (b>0) && (b<1) && (abs(a)+abs(b)<1)
then the two tris overlap
I'm fairly sure that should work although I may have made a slight error.
Tim