Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Polygon Triangulation (Ear Cutting)
Index -> Programming, Turing -> Turing Help
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
Silinter




PostPosted: 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
Sponsor
sponsor
Display posts from previous:   
   Index -> Programming, Turing -> Turing Help
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 1 Posts ]
Jump to:   


Style:  
Search: