Polygon Triangulation (Ear Cutting)
Author |
Message |
Silinter
|
Posted: Wed Apr 29, 2009 4:35 pm Post subject: Polygon Triangulation (Ear Cutting) |
|
|
I'm trying to triangulate an arbitrary simple polygon with no holes.
The problem is that the five or six explanations out there are very vague when they come to defining an ear.
The most concrete answer I got was that if the cross product of a->b, b->c and c->a (where a, b, c are points) is in the same direction as the normal of the polygon than it's an ear.
The only problem with that is the poster actually worded it as direction. How do you get a direction of the polygon? He later explained that the normal of the polygon
is acquired by taking the cross products of subsequent points along the polygon, which is good, but he didn't explain "direction". I assumed he meant sign.
Here's another tutorial explaining finding an ear, but vague on how to determine if a vertex is convex.
I've made my own ear clipper, but it reports a vertex as an ear even when, if it were to be cut the edge formed by the former and latter vertex crosses other edges or goes outside the polygon.
Turing: |
fcn crossProduct (x1, y1, x2, y2 : real) : real
result (x1 * y2) - (y1 * x2)
end crossProduct
fcn normal (x1, y1, x2, y2, x3, y3 : real) : real
result crossProduct (x1, y1, x2, y2) + crossProduct (x2, y2, x3, y3) + crossProduct (x3, y3, x1, y1)
end normal
|
These are the two functions that are used to determine the normal of the polygon and the vertex in question.
The normal is calculated by going around the polygon and getting the cross product of the current vertex and it's adjacent vertex.
The normal of a vertex is calculated by entering (p(i-1).x, p(i-1).y, p(i).x, p(i).y, p(i+1).x, p(i+1).y) into the normal function. (where p is the array holding the points for the polygon and i is the vertex in question).
OP edit: solved. it was a logical problem due to poor wording. i hang on words too much T_T. |
|
|
|
|
|
Sponsor Sponsor
|
|
|
|
|