Bug in TPPLPartition::IsConvex and IsReflex?

[code-monkey-101]

Based on the calls in UpdateVertex and IsInside, p2 is considered the central vertex.

So the two vectors would be v1 = p1-p2 v2 = p3-p2 (head - tail)

The z coordinate of the cross product would therefore be v1.x v2.y - v2.x v1.y = (p1.x - p2.x) (p3.y - p2.y) - (p3.x - p2.x) (p1.y - p2.y)

Note that the center vertex is always on the right hand side of the minus. Your code looks like this tmp = (p3.y - p1.y) (p2.x - p1.x) - (p3.x - p1.x) (p2.y - p1.y) which would be correct if p1 was the center vertex.

I couldn't even triangulate a square without changing this, no matter what winding I used. The ear-clipping algorithm didn't find a single convex vertex.

See also https://stackoverflow.com/questions/7785601/detecting-if-angle-is-more-than-180-degrees

[ivanfratric]

The two formulae are equivalent, except they result in the opposite sign (yours will give correct result for clockwise input, mine for counter-clockwise).

[code-monkey-101]

Thanks for the response!

Are they really equivalent? You get different signs when you switch v1 and v2 but when you are using a different center vertex, aren't you checking a different angle?

PS: It's absolutely possible that I am missing something.

[code-monkey-101]

Thinking about it, the angle at p1 becomes negative when p2 becomes greater than 180. I'll do some additional test tomorrow. Maybe I did get the winding wrong somehow.

[code-monkey-101]

Ok, I've tried it out and you are right, even though I don't understand it entirely. The method is basically calculating the normal vector of the triangle. There are only two possible normals if you ignore the length, no matter what the middle vertex is. The method doesn't care about the length of the normal, only the direction, so the result is the same except for the sign.

Interestingly enough, even the length of the normal seems to be the same, which is not that clear. The cross product is defined as the length of the two vectors times sin(angle between vectors). Neither the angle nor the length of the vectors are the same. You can also see it as the positive area of the parallelogram having the vectors as sides. The parallelograms are different, so it's not obvious that the area is the same.

Anyways, my main mistake was that I assumed that you can call TPPLPoly::SetOrientation after Init but before adding points. That doesn't work because SetOrientation doesn't set a flag. It actually changes the order of the points which only works after you set them.

However, there is also another problem. Triangulate_OPT doesn't work for the attached polygon. Only Triangulate_EC works. Why is that?

test_triangle.txt