Add your own alternative version
Stats
235.1K views 9.8K 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();
//Calculation Explanation:
//http://local.wasp.uwa.edu.au/~pbourke/geometry/clockwise/index.html
//Calculation for CONVEX (simple)
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;
}
}
/*
* Alternative implementation from http://alienryderflex.com/polygon/
*/
public bool PointInsidePolygon(CPoint2D[] polygonVertices)
{
if (polygonVertices.Length < 3) //not a valid polygon
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.

