
Comments and Discussions





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.





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







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.

Triangulate a polygon by cutting ears in C#
Type  Article 
Licence  
First Posted  9 Sep 2004 
Views  197,636 
Bookmarked  106 times 

