
Comments and Discussions



are you want to see my triangulator:
http://www.youtube.com/watch?v=uglSdkHTXnY[^]
this application and source code available coming soon... (vb.net)
extensions: polygon triangulator, collision detection, path finder, edge smooter for polygons, bitmap polygonizer, similarity finder (OCR etc...) and more
?





Modifying the original default data it can be seen that the triangulation fails. The below code draws a simple "I" shape.
m_aPolygon=new Point[12];
m_aPolygon[0]=new Point(0,0);
m_aPolygon[1]=new Point(0,50);
m_aPolygon[2]=new Point(50,50);
m_aPolygon[3]=new Point(50,100);
m_aPolygon[4]=new Point(0,100);
m_aPolygon[5]=new Point(0,150);
m_aPolygon[6]=new Point(150,150);
m_aPolygon[7]=new Point(150,100);
m_aPolygon[8]=new Point(100,100);
m_aPolygon[9]=new Point(100,50);
m_aPolygon[10]=new Point(150,50);
m_aPolygon[11]=new Point(150,0);
I just realized that this is a similar bug that was happening to mario a few years ago. Nevertheless I decided to post my data for testing purposes. I am guessing not to hold my breath on a fix.
modified on Wednesday, July 2, 2008 2:13 PM





How difficult would it be to modify this algorithm to handle holes? Would it be worth trying to change the existing code or would it be better to start over conceptually from scratch?





Holes are theoretically easy: Let the "hole" be a polygon with reverse winding inside of the containing polygon, and merge them into a single polygon by joining a vertex (actually a start and an end vertex with the same positions) from each polygon with two edges. Essentially you have one polygon with an infitesimal small gap, you can visualize it like:
_________
/ ___ \
 ___>
\_________/
(You'll have to copy and paste this ASCII *art* into some text editor with fixedwidth font support, doesn't work with kerned fonts)
Where the dashes represent the connecting seam, picture the outer polygon to be winded clockwise and the inner one counter clockwise.





Fiorentino, appreciate the response. I am trying to think of ways this could be implemented. I believe the original source code reversed the poly point hull if the points were deemed clockwise. So, I am not sure how this will play into having an outer poly point hull as clockwise. Would the point list be composed of one continuous point list (outer hull clockwiseinner hull anticlock)? I can try to play with some small samples to see the effect. Thanks





To be honest, I haven't read the original source code, but was eager to try to help you. Now, based on what you said about the source code ensuring the winding direction of the polygons, I assume this is because it makes the earclipping approach so much easier.
If you encapsulate the polygon in a structure with a flag that says whether it is additive or subtractive (or hole or not hole or whatever lingo you prefer), you can then ensure the opposing winding directions of polygons that are supposed to be additive or subtractive (holes) in the method that ensures the proper winding directions.
Then before the triangulation step, you map out what subtractive polygons are completely contained in what additive polygons (scrap overlapping polygons to make it easier, you can deal with edge intersections and clipping later on). You can do this by starting with a test on whether a vertex of the subtractive polygon is inside the additive polygon, if it is, then check that none of its edges intersect with the edges of the additive one. Of course, selfintersection would be tested for before this step to rule out all malshaped polygons.
After this make the program find the closest vertices of the outer polygon and the hole polygon, and merge them there (this takes a bit of index magic, but is easy to do with a bit of thinking).
Now, this should theoretically work for polygons with single holes. If there are multiple holes, and they do not overlap, inside of a polygon, you must take steps to ensure that the gluing edges do not cross any existing edges, so it's a bit more tricky.
If done right, the newly constructed polygons from the holes should be consistent with the winding direction of the outer polygon, so the actual triangulation algorithm should need to be touched.
Hope it works out for you.
I've found that it isn't really possible to model a polygon with hole, without separating the two or joining them with a glue edge.





Can someone tell me how I triangular holes? Does anyone have a code example?





what are the rules for reuse?





Can I triangulate complex polygons? (those who are composed by many rings)
LeonniK®





I found two bugs in the PointInsidePolygon method of CPoint2D.
1. This for loop: for (int i= 1; i<nPoints; i++)
needs to loop until i<=nPoints, that is: for (int i= 1; i<=nPoints; i++)
2. Points that are on the border will return inconsistent results. Since you are using the method of checking a line from the point and counting the number of intersections of polygon sides (even = outside, odd = inside). If the point is already on the a border of the polygon the code counts that as one intersection. depending on which side of the polygon the point is on and which way your testing line is drawn you may head into the poylgon, out the other side and cross another line resulting in 2 intersections (not in polygon). Or the testing line would be drawn away from the inner polygon resulting in just the one intersection (in the polygon). To fix this you can simply check if the point is on a border line and if it is return true, else continue with the test you now have.





hellow
I enlarged the MainForm of the demo to 1600X1200 to fit the following input:
m_aPolygon=new Point[26];
m_aPolygon[0] = new Point(487,450);
m_aPolygon[1] = new Point(498 ,482);
m_aPolygon[2] = new Point(708, 767);
m_aPolygon[3] = new Point(704, 927);
m_aPolygon[4] = new Point(638,1054);
m_aPolygon[5] = new Point(528,1130);
m_aPolygon[6] = new Point(400 ,1157);
m_aPolygon[7] = new Point(272 ,1130);
m_aPolygon[8] = new Point(162 ,1054);
m_aPolygon[9] = new Point(96 ,927);
m_aPolygon[10] = new Point(92,767);
m_aPolygon[11] = new Point(302, 482);
m_aPolygon[12] = new Point(313, 450);
m_aPolygon[13] = new Point(374, 415);
m_aPolygon[14] = new Point(370, 425);
m_aPolygon[15] = new Point(367, 440);
m_aPolygon[16] = new Point(368 ,456);
m_aPolygon[17] = new Point(376, 467);
m_aPolygon[18] = new Point(387, 479);
m_aPolygon[19] = new Point(400, 489);
m_aPolygon[20] = new Point(413, 479);
m_aPolygon[21] = new Point(424, 467);
m_aPolygon[22] = new Point(432, 456);
m_aPolygon[23] = new Point(433, 440);
m_aPolygon[24] = new Point(430, 425);
m_aPolygon[25] = new Point(426 ,415);
and the triangulation is not working!!!
please help me ...
shoham





Hello,
I use other test data:
m_aPolygon=new Point[12];
m_aPolygon[0]=new Point(50,50);
m_aPolygon[1]=new Point(190,50);
m_aPolygon[2]=new Point(190,55);
m_aPolygon[3]=new Point(75,55);
m_aPolygon[4]=new Point(75,195);
m_aPolygon[5]=new Point(190,195);
m_aPolygon[6]=new Point(190,200);
m_aPolygon[7]=new Point(50,200);
m_aPolygon[8]=new Point(50,195);
m_aPolygon[9]=new Point(70,195);
m_aPolygon[10]=new Point(70,55);
m_aPolygon[11]=new Point(50,55);
This is a polygon like a big I, all only 90° angles. Triangulation for this case not works. Can anybody say what’s wrong?
Mario





Another problem:
m_aPolygon=new Point[8];
m_aPolygon[0]=new Point(50,70);
m_aPolygon[1]=new Point(150,70);
m_aPolygon[2]=new Point(150,170);
m_aPolygon[3]=new Point(100,170);
m_aPolygon[4]=new Point(120,120);
m_aPolygon[5]=new Point(80,120);
m_aPolygon[6]=new Point(100,170);
m_aPolygon[7]=new Point(50,170);
Cutting ears never return





I found that the problem is with point(100,170), propably you should not allow 2 same points ... try this:
m_aPolygon=new Point[8];
m_aPolygon[0]=new Point(50,70);
m_aPolygon[1]=new Point(150,70);
m_aPolygon[2]=new Point(150,170);
m_aPolygon[3]=new Point(100,170);
m_aPolygon[4]=new Point(120,120);
m_aPolygon[5]=new Point(80,120);
m_aPolygon[6]=new Point(100,171);
m_aPolygon[7]=new Point(50,170);
it works well.
Wizard_01





Below code is used to draw conditional shape used in the flow chart in rubber band effect.
Point[] ptArray = new Point[4];
ptArray[0] = new Point(m_ptStart.X + (m_ptOld.X  m_ptStart.X) / 2, m_ptStart.Y);
ptArray[1] = new Point(m_ptStart.X + (m_ptOld.X  m_ptStart.X), m_ptStart.Y + ((m_ptOld.Y  m_ptStart.Y) / 2));
ptArray[2] = new Point(m_ptStart.X + ((m_ptOld.X  m_ptStart.X) / 2), m_ptStart.Y + ((m_ptOld.Y  m_ptStart.Y)));
ptArray[3] = new Point(m_ptStart.X, m_ptStart.Y + ((m_ptOld.Y  m_ptStart.Y) / 2));
g.DrawPolygon(p, ptArray);
Regards,
anil Kale





The InLine method does not work properly.
After my change the InLine method seems to work better.
Before my change:
else if ((Cx < lineSegment.GetXmax())
&& (Cx > lineSegment.GetXmin())
&& (Cy < lineSegment.GetYmax())
&& (Cy > lineSegment.GetYmin()))
After my change:
else if ((Cx <= lineSegment.GetXmax())
&& (Cx >= lineSegment.GetXmin())
&& (Cy <= lineSegment.GetYmax())
&& (Cy >= lineSegment.GetYmin()))





The "IntersectedWith" method does not function properly.
First of all ... I believe that:
if (Math.Abs(de  0) < ConstantValue.SmallValue)
Should be:
if (Math.Abs(de  0) > ConstantValue.SmallValue)
Additionally,
if ((ub > 0) && (ub < 1))
return true;
Seems to return true, even if the lines don't actually intersect. I think this should rather be:
if ((ub > 0) && (ub < 1))
if ((ua > 0) && (ua < 1))
return true;
else
return false;
This seems to make it function properly.
Anyone else come across this?
 modified at 12:00 Friday 10th March, 2006





I found no usage of this function.





Hi,
One aspect that you may not be aware of is that this algorithm does not always choose triangles with shorter sides when there is a choice. A simple example is where you have a 5 point star and the center is a pentagon. If the star is not symmetric the pentagon will have 2 unequal length diagonals. The diagonals must share a common vertex. You can choose this common vertex to be any one of the 5 in the pentagon.
Does it matter? The question depends on what you are using the triangles for. For many modeling uses it is best that the triangles chosen are as close to equilateral, or have the largest internal angles as possible. Triangles with long sides and very small angles do not model surfaces very well and the trig functions usually suffer with small angles.
Your second example with the S shape polygon shows how long and pointy some of the triangles were made. There is another set of triangles that keep them all about the same size and shape.
I once wrote a program that followed Donald Knuth's algorithm that he describes in his paper "Axioms and Hulls". This is slightly different in that you have a field of randomly placed points and you want to triangulate them all to form a mesh of triangles. The outside perimeter is the "hull", but what points will be used for the hull. That's a big computational geometry question and the solution is not trivial. The key point here is that the triangles have to be formed using a set of rules that define what is called a "Delaney Triangle". Simply stated, the triangle is formed from nearest neighbours, but the algorithm is complex. Knuth has a very good solution.





I suspect you can somewhat achieve better control on the shape of the triangles by clipping off convex polygons instead of just ears first. Then you are free to sort out the triangles in any fashion, i.e. triangle fans.





Hi,
One aspect that you may not be aware of is that this algorithm does not always choose triangles with shorter sides when there is a choice. A simple example is where you have a 5 point star and the center is a pentagon. If the star is not symmetric the pentagon will have 2 unequal length diagonals. The diagonals must share a common vertex. You can choose this common vertex to be any one of the 5 in the pentagon.
Does it matter? The question depends on what you are using the triangles for. For many modeling uses it is best that the triangles chosen are as close to equilateral, or have the largest internal angles as possible. Triangles with long sides and very small angles do not model surfaces very well and the trig functions usually suffer with small angles.
Your second example with the S shape polygon shows how long and pointy some of the triangles were made. There is another set of triangles that keep them all about the same size and shape.
I once wrote a program that followed Donald Knuth's algorithm that he describes in his paper "Axioms and Hulls". This is slightly different in that you have a field of randomly placed points and you want to triangulate them all to form a mesh of triangles. The outside perimeter is the "hull", but what points will be used for the hull. That's a big computational geometry question and the solution is not trivial. The key point here is that the triangles have to be formed using a set of rules that define what is called a "Delaney Triangle". Simply stated, the triangle is formed from nearest neighbours, but the algorithm is complex. Knuth has a very good solution.





Hi, what if the inline function is omitted?
would there be an error?
I see the polygon would still be triangulated.
Cause in my case, I actually need all the points, so even if it's inline, it should be triangulated as well.
thanks
 modified at 20:33 Tuesday 11th October, 2005





This is a GREAT example, but I found a small problem at the demo application. When you drawing a poly like in test data but opposite way, there is only one triangle. x \ x \ x \ x / x / / Thanks. Boris.





In the CPolygon.Diagonal method, the parameter vertex2 is never used.
Best regards,
Paul.
Jesus Christ is LOVE! Please tell somebody.





I found this article really useful, but I have a little problem that your program is not able to solve. Really, I am not sure that there is a solution, but here it goes:
How to know if a concave polygon is CCW or CW when there are the same number of concave and convex vertices? Half the cross products are positive and half are negative.
Two thumbs up.





This algorithm will be very useful to me, thanks so much!





It looks great! Wonderful work!
However, there's a crash once you draw a simple triangle and try to find the ears.
I didn't mean to find it! Honest! :P
Programming is life; The rest is mere details.





This bug is fixed and the code is updated. Thanks for pointing out the problem.





I'm speechless.










General News Suggestion Question Bug Answer Joke Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

