Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Determining if an angle causes polygon to be concave.

Credits go to hazul and Indeterminatus for helping out!
This thread is locked; no one can reply to it. rss feed Print
Determining if an angle causes polygon to be concave.
Elverion
Member #6,239
September 2005
avatar

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?

--
SolarStrike Software - MicroMacro home - Automation software.

Indeterminatus
Member #737
November 2000
avatar

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.

_______________________________
Indeterminatus. [Atomic Butcher]
si tacuisses, philosophus mansisses

Elverion
Member #6,239
September 2005
avatar

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.

--
SolarStrike Software - MicroMacro home - Automation software.

hazul
Member #4,338
February 2004
avatar

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));

* * * * *
"Multiplayer is actually the best way of not programming a good AI" -ReyBrujo

Elverion
Member #6,239
September 2005
avatar

Quote:

Hmm.. why use this:
...
instead of this ?

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.

--
SolarStrike Software - MicroMacro home - Automation software.

Kitty Cat
Member #2,815
October 2002
avatar

Quote:

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

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

--
"Do not meddle in the affairs of cats, for they are subtle and will pee on your computer." -- Bruce Graham

Go to: