http://solarimpact.servegame.com/poly1.jpg

Ok, for example, I have polygon ABCDEFG. During triangulation, I need to test if the angle in the "test triangle" has a segment that lies outside of the polygon.

In this picture, my current triangulation algorithm first will try ABC. It is correct, so point B is now ignored from further triangulation. Now, it moves on to ACD, which is incorrect (as AD lies outside of the polygon). This is due to the fact that angle C is > 180°. I need to find a quick, easy way to check for this in order to correct the problem that arises.

In IRC, I was discussing a few different methods with several people, but could not decide on a single efficient method. So, I come to you people: the Allegro group! What is the quickest, easiest way of checking if this angle will cause a concave in the rest of the angle? I was thinking of finding the angle at C, and check if it's greater than 180° or not...but, how would you do this? Would the math slow it down too much?

I haven't fully thought this through, so take this with great care: I just had the idea that it should be also possible to check if AD intersects with the polygon (points A and D excluded, of course). If it does, it's concave, if it doesn't, everything's fine.

I doubt that this'd be any faster, though.

The angle approach seems fine. I'd probably use the scalar product for that.

I was thinking...if I can find the two angles using atan2, then subtract that from 360, it should give the angle at B, right? Or maybe my logic here is flawed.

The math I'm using is:

  float angle1 = fixtof( fixatan2(itofix(poly[c].y - poly<b>.y), itofix(poly[c].x - poly<b>.x)) );
  float angle2 = fixtof( fixatan2(itofix(poly[a].y - poly<b>.y), itofix(poly[a].x - poly<b>.x)) );
  float angleb = 360 - abs(angle1) - abs(angle2);
  
  allegro_message("Angle1 is: %f\nAngle2 is: %f\nAngle B must be: %f", angle1, angle2, angleb);

angle1 and angle2 are occasionally negative...is that correct? To compensate for that, I just used their absolute values in finding angleb. My problem here now is that angleb is almost always > 200.0, which can't be correct. What am I doing wrong?

So then I was thinking, instead of subtracting from 360, and checking if it's > 180, to subtract from 180, and check if it's greater than 90. The numbers looked right...but the graph didn't.

Hmm.. why use this:
float angle1 = fixtof( fixatan2(itofix(poly[c].y - poly<b>.y), itofix(poly[c].x - poly<b>.x)) );
instead of this ?
float angle1 = atan2((poly[c].y - poly<b>.y), (poly[c].x - poly<b>.x));

163 C:\poly_test\c_poly.cpp conversion from `int' to non-scalar type `fix' requested

Already tried it.

It has occured to me that fixatan2 uses "Allegro degrees", right? I've modified my code to:

  float angle1 = fixtof( fixatan2(itofix(poly[c].y - poly<b>.y), itofix(poly[c].x - poly<b>.x)) );
  float angle2 = fixtof( fixatan2(itofix(poly[a].y - poly<b>.y), itofix(poly[a].x - poly<b>.x)) );
  float angleb = 256 - abs( ((128-angle1) - (256-angle2)) );
  
  if ( (angleb < 0) || (angleb > 192) )
    return false;

Everything seems to be in order now, so long as points are NOT entered in a clockwise fashion. I'll have to keep testing polygon after polygon to make sure that everything is in order.

Even though you may not have given me the perfect answer, I always look forward to your feedback, and your replies made me think down the right path. So, cookies to you both.

Allegro's damned fix C++ class. The most evil thing to "grace" Allegro that I know of. You can either define this on the command line, or before anywhere you include Allegro:
ALLEGRO_NO_FIX_CLASS