<html>
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p><font face="serif">Thanks to Phuc for remininding me about this
last night. In the ear clipping algorithm your proposed "line
back to the starting vertex" must not intersect any other
lines. It also must be in the interior of the polygon. For
example. If you were to try and tesselate the following simple
figure using only the constraints that the the proposed line
does not intersect any other line segments...</font></p>
<img src="cid:part1.2D819F06.8EB1BBDE@mercer.edu" alt="specialtess0"
width="469" height="602"><br>
<br>
you would have an issue because the red line (which would be the
proposed line back to the first vertex) would not intersect any
other lines, but would also be outside of the polygon.<br>
<br>
<img moz-do-not-send="false"
src="cid:part2.50D3887C.D1297AB3@mercer.edu" alt="t1" width="513"
height="656"><br>
<br>
The fix for this is relatively straightforward. Compute the angles
alpha and beta as shown.<br>
<br>
<img moz-do-not-send="false"
src="cid:part3.588F645A.9B968682@mercer.edu" alt="t2" width="540"
height="692"><br>
<br>
and if alpha is less than beta then the proposed line back to the
first vertex is in the interior of the polygon and you are able to
are able to draw the line and complete the ear clipping. This is
another great place for a boolean function to test if the proposed
line is in the interior of the polygon.<br>
<br>
<br>
<pre class="moz-signature" cols="72">--
Andrew J. Pounds, Ph.D. (<a class="moz-txt-link-abbreviated" href="mailto:pounds_aj@mercer.edu">pounds_aj@mercer.edu</a>)
Professor of Chemistry and Computer Science
Mercer University, Macon, GA 31207 (478) 301-5627
<a class="moz-txt-link-freetext" href="http://faculty.mercer.edu/pounds_aj">http://faculty.mercer.edu/pounds_aj</a>
</pre>
</body>
</html>