Add your own alternative version
Stats
241.7K views 10.1K downloads 109 bookmarked
Posted
9 Sep 2004

Comments and Discussions



Triangulate function is not working when the polygon contains more than 4000 points.
What is the solution?
Thanking you Subrata,Kolkata





This algorithm fails in most of the cases, Please provide a better solution for that. I am providing you a list of points where first coloumn is X, second is Y and last is Z. Use in 1 to +1 screen cordinate system.
here is the list of points : 378936.00 9249177.00 0.000 379061.00 9249652.00 0.000 379061.00 9250152.00 0.000 379236.00 9250639.00 0.000 379136.00 9251152.00 0.000 379136.00 9251664.00 0.000 378986.00 9252152.00 0.000 379022.69 9252659.00 0.000 379188.56 9253203.00 0.000 378721.75 9253676.00 0.000 378453.88 9254172.00 0.000 377969.44 9254551.00 0.000 377736.53 9254636.00 0.000 377553.06 9255172.00 0.000 377207.22 9255652.00 0.000 376896.69 9256139.00 0.000 376454.53 9256614.00 0.000 376341.63 9256671.00 0.000 376038.16 9257129.00 0.000 375960.53 9257320.00 0.000 375946.41 9257673.00 0.000 375748.78 9258146.00 0.000 375936.00 9258627.00 0.000 376453.50 9259151.00 0.000 376375.88 9259645.00 0.000 376298.25 9260195.00 0.000 376509.97 9260661.00 0.000 376178.28 9261169.00 0.000 376164.16 9261325.00 0.000 376150.03 9261670.00 0.000 375867.75 9262129.00 0.000 375712.47 9262623.00 0.000 375473.13 9263125.00 0.000 375289.63 9263640.00 0.000 375155.53 9264134.00 0.000 374607.56 9264449.00 0.000 374320.22 9264702.00 0.000 374113.31 9264690.00 0.000 374412.16 9264368.00 0.000 374873.22 9264085.00 0.000 374986.13 9263633.00 0.000 375075.41 9263177.00 0.000 375393.00 9262676.00 0.000 375627.78 9262122.00 0.000 375924.19 9261663.00 0.000 375987.72 9261141.00 0.000 376312.38 9260647.00 0.000 376142.97 9260167.00 0.000 376157.09 9259659.00 0.000 376192.38 9259137.00 0.000 375761.00 9258627.00 0.000 375522.94 9258160.00 0.000 375663.16 9257658.00 0.000 375861.00 9257139.00 0.000 375961.00 9256977.00 0.000 376086.81 9256614.00 0.000 376461.00 9256427.00 0.000 376649.69 9256146.00 0.000 376960.22 9255610.00 0.000 377221.34 9255179.00 0.000 377386.00 9254914.00 0.000 377553.06 9254579.00 0.000 377950.00 9254433.00 0.000 378294.09 9254142.00 0.000 378458.13 9254003.00 0.000 378649.50 9253623.00 0.000 378912.13 9253152.00 0.000 378818.56 9252655.00 0.000 378711.00 9252152.00 0.000 378861.00 9251652.00 0.000 378911.00 9251152.00 0.000 379011.00 9250639.00 0.000 378911.00 9250139.00 0.000 378886.00 9249639.00 0.000 378711.00 9249164.00 0.000 378936.00 9249164.00 0.000 378936.00 9249177.00 0.000  In this case traingulation is done outside the polygon i.e. wrong.







I would like an algorithm to merge adjacent or overlapping polygons any ideas?





Hi,
I have used the triangulation library as part of a Extruded Shape > OBJ converter to avoid uncontroled rendering efects. My polygons have holes and are potentially complex (no self intersection though). First I had to expand the library to include hole support (first merging the outer and inner hole with a fake double connection).
In general it worked fine, but some polygons were not correctly converted. Investigating I found out some methods where not giving the right response.
 VerticesDirection (in CPolygon) not always gives the right answer. PointInsidePolygon from CPoint2D failed in some polygons.
Alternative methods:
public PolygonDirection VerticesDirection()
{
int nCount = 0, j = 0, k = 0;
decimal area = 0;
int nVertices = m_aVertices.Length;
PolygonType pType = this.GetPolygonType();
if (pType == PolygonType.Convex)
{
double crossProduct = (m_aVertices[1].X  m_aVertices[0].X)
* (m_aVertices[2].Y  m_aVertices[1].Y);
crossProduct = crossProduct  (
(m_aVertices[1].Y  m_aVertices[0].Y)
* (m_aVertices[2].X  m_aVertices[1].X));
if (crossProduct > 0)
return PolygonDirection.Count_Clockwise;
else if (crossProduct < 0)
return PolygonDirection.Clockwise;
else
return PolygonDirection.Unknown;
}
else {
for (int i = 0; i < nVertices1; i++)
{
j = (i + 1);
area = area + Convert.ToDecimal((m_aVertices[i].X * m_aVertices[j].Y)  (m_aVertices[j].X * m_aVertices[i].Y));
}
area = area + Convert.ToDecimal((m_aVertices[nVertices  1].X * m_aVertices[0].Y)  (m_aVertices[0].X * m_aVertices[nVertices  1].Y));
if (area > 0)
return PolygonDirection.Count_Clockwise;
else if (area < 0)
return PolygonDirection.Clockwise;
else
return PolygonDirection.Unknown;
}
}
public bool PointInsidePolygon(CPoint2D[] polygonVertices)
{
if (polygonVertices.Length < 3)
return false;
int nCounter = 0;
int nPoints = polygonVertices.Length;
bool oddNodes = false;
int j = nPoints  1;
for (int i = 0; i < nPoints; i++)
{
if (polygonVertices[i].m_dCoordinate_Y < this.m_dCoordinate_Y && polygonVertices[j].m_dCoordinate_Y >= this.m_dCoordinate_Y
 polygonVertices[j].m_dCoordinate_Y < this.m_dCoordinate_Y && polygonVertices[i].m_dCoordinate_Y >= this.m_dCoordinate_Y)
{
if (polygonVertices[i].m_dCoordinate_X + (this.m_dCoordinate_Y  polygonVertices[i].m_dCoordinate_Y) / (polygonVertices[j].m_dCoordinate_Y  polygonVertices[i].m_dCoordinate_Y) * (polygonVertices[j].m_dCoordinate_X  polygonVertices[i].m_dCoordinate_X) < this.m_dCoordinate_X)
{
oddNodes = !oddNodes;
}
}
j = i;
}
return oddNodes;
}
I hope it helps.
If someone is interested in the implementation for polygons with holes. Just ask.
Oscar





Very good job





hi all, in my code i need to draw a rectangle and to show 0 or 1 in that can anyone halp me out this is very urgent........ thanks in advance





I'm getting help from your codes here. Nice job! I'm wondering if I can get help with this problem. I'm trying to draw a simple concave polygon from a set of points(not sequential). Thanks in advance...
modified on Wednesday, November 19, 2008 11:57 PM





foreach(ShapeRecord record1 in m_ShapeTileArgs.ShapeRecords)//over 10000 { ..... CPoint2D[] vertices = new CPoint2D[record1.Polygon.Points.Length]; for (int i = 0; i <record1.polygon.points.length;>{ vertices[i] = new CPoint2D(record1.Polygon.Points[i].X, record1.Polygon.Points[i].Y); } CPolygonShape cutPolygon = new CPolygonShape(vertices); cutPolygon.CutEar(); ..... }
And my program stopped here,never got out. I just don't know what is happenning. Does it spend much time to caculate? but it just stopped there.





I know this may sound unrelated, but check if the first and last element in m_ShapeTileArgs.ShapeRecords are the same. Because if they are the same, then you get an infinite loop without any errors.
It is worth giving a try.
Aram Azhari





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 Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

