Triangulating Simple (Convex) polygons is peanuts, but triangulating nonconvex ones appears to be quite an involved process. I came up with an algorhythm on my own (which I later found was the “line sweep algorythm”), but I am too lazy to implement it on my own. Are there any libraries to do this? In case you’re wondering, I’m writing a program/library/whatever that will give you names of oceans and polygons associated with them. To go the reverse way, I need to do hit test, which is best with triangles.
to check, if a point lies within an arbitrary poly, you could use the following algorithm, if you are in 2d space:
int /* 1=inside, 0=outside /
inpoly( / is target point inside a 2D polygon? /
unsigned int poly[][2], / polygon points, [0]=x, [1]=y /
int npoints, / number of points in polygon /
unsigned int xt, / x (horizontal) of target point /
unsigned int yt) / y (vertical) of target point */
{
unsigned int xnew,ynew;
unsigned int xold,yold;
unsigned int x1,y1;
unsigned int x2,y2;
int i;
int inside=0;
if (npoints < 3) {
return(0);
}
xold=poly[npoints-1][0];
yold=poly[npoints-1][1];
for (i=0 ; i < npoints ; i++) {
xnew=poly[i][0];
ynew=poly[i][1];
if (xnew > xold) {
x1=xold;
x2=xnew;
y1=yold;
y2=ynew;
}
else {
x1=xnew;
x2=xold;
y1=ynew;
y2=yold;
}
if ((xnew < xt) == (xt <= xold) /* edge "open" at one end */
&& ((long)yt-(long)y1)*(long)(x2-x1)
< ((long)y2-(long)y1)*(long)(xt-x1)) {
inside=!inside;
}
xold=xnew;
yold=ynew;
}
return(inside);
if want to triangulate polys with holes, check out the “seidel algorithm” and the “earclip algorithm”. an implementation is available at http://www.terragear.org . download the project and look for the poly library inside. it has some problems, that have to be fixed. i did it a while ago. contact me, if you want the patched files.
If all you want to do is hit test a complex polygon, it seems easier to just use the regular raycast polygon inclusion testing algorithm. Shoot a ray in the plane of the polygon from the point towards positive infinity. Count the number of times it passes through an edge of the poly, where each “uppermost” vert counts as “in” the line, and “lowermost” counts as “not in”. If it’s odd, you’re inside the poly.
Note that hit testing the area described by an n-gon in 3-space is an ambiguous problem (because “the area described” is ambiguous).
Look at http://www.codeproject.com/useritems/polygon_tesselation.asp. This is a sub-case of monoconnected (not self intersecting) polygons. The sample is for 2D but iy works fine in 3D. The basic idea is to reduce a non convex polygon to convex removing vertex. This tecnique il more speed (in my esperience) than glu (that is more geneal) and as the advantage that don’t insert points (big advantage when you use texture mapping).