# Earcutting algorithm

This topic is 3337 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I'm trying to use the earcutting algorithm found here: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html But, it fails on a particular shape I'm testing, and I don't know why. This shape is a simple polygon. It has no holes, no intersecting edges, and no collinear points. And the points are perfectly ordered the way the algorithm wants them. I don't know of any other requirements. If anyone here is using it, I was wondering if you could try out my point data and see if you get the same results. direct link to image Problem <br /><br />
# 67 points
0.896228, -9.559765
-4.806242, -9.559765
-4.806242, -9.342011
-4.661872, -9.299168
-4.453118, -9.210262
-4.277850, -9.100100
-4.140493, -8.969691
-4.061854, -8.855359
-3.986295, -8.692520
-3.934360, -8.503078
-3.912570, -8.327597
-3.909851, -8.237110
-3.909851, 6.406619
-9.985071, 6.406619
-10.199396, 6.390604
-10.395503, 6.344637
-10.565790, 6.273743
-10.707406, 6.182111
-10.817174, 6.073102
-10.932118, 5.906509
-11.025241, 5.706016
-11.089889, 5.510261
-11.304804, 5.510261
-11.304804, 10.176340
-11.087529, 10.176340
-11.044605, 10.029084
-10.956005, 9.814075
-10.852725, 9.645889
-10.762815, 9.548217
-10.706326, 9.504527
-10.613694, 9.429585
-10.479352, 9.360190
-10.293304, 9.306666
-10.088482, 9.282678
-9.981827, 9.279983
6.045895, 9.279983
6.258058, 9.291615
6.456950, 9.330135
6.638083, 9.400080
6.788710, 9.497355
6.891400, 9.599189
6.998284, 9.763045
7.092585, 9.963773
7.172896, 10.176340
7.394856, 10.176340
7.394856, 5.510261
7.170963, 5.510261
7.116407, 5.659758
7.024268, 5.863114
6.922921, 6.033561
6.800833, 6.181260
6.635101, 6.275786
6.459604, 6.345014
6.261662, 6.390629
6.047173, 6.406619
-0.000097, 6.406619
-0.000097, -8.238758
0.011567, -8.450741
0.050265, -8.647085
0.113406, -8.806944
0.183034, -8.914887
0.227596, -8.965126
0.291393, -9.042631
0.413447, -9.141696
0.604803, -9.243913
0.830597, -9.325880
0.896228, -9.343996
# end

[Edited by - rootbender on October 24, 2009 10:30:26 PM]

##### Share on other sites
Can you post the source for your implementation of the algorithm?

##### Share on other sites

I was looking ear cutting up on the web (I'd not heard of it before...)
and found reference back to this:

http://www.gamedev.net/community/forums/topic.asp?topic_id=471865

##### Share on other sites
Quote:
 Can you post the source for your implementation of the algorithm?

You can find a C++ version here (not mine):
https://svn.cs.rpi.edu/svn/DVC/trunk/simulator/include/triangle.h
https://svn.cs.rpi.edu/svn/DVC/trunk/simulator/src/triangle.cpp

It produces the exact same results. Bad triangulation.
I don't have the OpenGL portion available, but you can create a simple test program out of it:

#include "triangle.h"using namespace DVC;void RunTest(FILE *File);int  main(int argc, char *argv[], char *env[]);intmain(int argc, char *argv[], char *env[]) { if(argc < 2) return 0; FILE *File = fopen(argv[1], "rt"); if(File) {    RunTest(File);    fclose(File);    File = NULL; } return 0;}voidRunTest(FILE *File) { if(NULL == File) return; EarCutter E; /////////////////////////////// // Read in pointdata char line_buffer[512]; double x,y; double first_x,first_y; int count=0; while(fgets(line_buffer, 512, File)) {     if(sscanf( line_buffer, "%lf, %lf", &x, &y) == 2) {       E.AddPoint(x,y);       // save first point       if(!count) {          first_x = x;          first_y = y;        }       count++;    } } // repeat first point E.AddPoint(first_x, first_y); /////////////////////////////// E.Start(); E.CutAll(); E.PrintPoints(); E.PrintTris();}

Quote:
 I was looking ear cutting up on the web (I'd not heard of it before...)and found reference back to this:

Thanks, I looked at the geometrictools site, but it appears much the code is heavily dependent on their libraries.

##### Share on other sites
Looks like it doesn't properly handle points that are on the very edges of a triangle in EarCutter::triangleContainsPoint, leading it to not see that left point in the T-joint intersects the dodgy triangle it's adding.

I tried your data in a python implemention of mine (below).

Without:

So, try changing the > and < comparisons in EarCutter::triangleContainsPoint to >= and <=.

My implementation, for reference:

import csvimport Imageimport ImageDrawdef ear(p):    for i in range(len(p)):        t = [p[(i - 1) % len(p)], p, p[(i + 1) % len(p)]]        if convexPt(t) and noConcavePtInTri(p, i, t):            return (i, t)def ears(p):    p = list(p)    es = []    while len(p) >= 3:        e = ear(p)        if not e:            break        es.append(e[1])        p.pop(e[0])    return esdef convexPt(t):    return area(t) < 0def noConcavePtInTri(p, ii, t):    for i in range(len(p)):        if min((i - ii) % len(p), (ii - i) % len(p)) <= 1:            continue        tt = [p[(i - 1) % len(p)], p, p[(i + 1) % len(p)]]        if convexPt(tt):            continue        as = [            area([t[0], t[1], p]),            area([t[1], t[2], p]),            area([t[2], t[0], p])        ]        if all(map(lambda x: x <= 0, as)) or all(map(lambda x: x >= 0, as)):            return False    return Truedef area(t):    return (        t[0][0] * (t[2][1] - t[1][1]) +        t[1][0] * (t[0][1] - t[2][1]) +        t[2][0] * (t[1][1] - t[0][1])    ) / 2ps = [tuple(map(float, r)) for r in csv.reader(open(r"c:\rootbender.csv", "rb"))][::-1]es = ears(ps)im = Image.new("RGB", (640, 480))imd = ImageDraw.Draw(im)conv = lambda (x, y): (x * 20 + im.size[0] / 2, -y * 20 + im.size[1] / 2)for e in es:    imd.polygon(map(conv, e), outline=(255, 0, 0), fill=(127, 0, 0))for p in ps:    imd.rectangle(map(conv, [(p[0] - .1, p[1] - .1), (p[0] + .1, p[1] + .1)]))im.show()

##### Share on other sites
Quote:
 Original post by mattdLooks like it doesn't properly handle points that are on the very edges of a triangle in EarCutter::triangleContainsPoint, leading it to not see that left point in the T-joint intersects the dodgy triangle it's adding.

Thanks for looking at it!

I tried adding the signs, but it didn't work. Half the triangles disappeared. :( I also tried adding some epilson, but again, nothing.
I also replaced the whole function with another one found elsewhere, but I got the same bad result.

Sorry, I'm not familiar with Python, so I'm not sure how you got it to work?
That's awesome if you did.

This didn't work:
       if (area1 >= 0) {          if ((area2 >= 0) && (area3 >= 0)) {             noPointInTriangle = false;          }       }       if (area1 <= 0) {          if ((area2 <= 0) && (area3 <= 0)) {             noPointInTriangle = false;          }       }

This didn't work either:
boolEarCutter::triangleContainsPoint(double x1, double y1, double x2, double y2, double x3, double y3) { int i=0; bool noPointInTriangle = true; vec2 p0 = vec2( x1, y1 ); vec2 p1 = vec2( x2, y2 ); vec2 p2 = vec2( x3, y3 ); while ((i < (npoints-1)) && (noPointInTriangle)) {    if ((ptType == -1)  &&       (((xpoints != x1) && (ypoints != y1)) ||        ((xpoints != x2) && (ypoints != y2)) ||        ((xpoints != x3) && (ypoints != y3)))) {        vec2 pp = vec2( xpoints, ypoints );	vec2 v0 = p1 - p0;	vec2 v1 = p2 - p0;	vec2 v2 = pp - p0;	double dot00 = DotProduct(v0, v0);	double dot01 = DotProduct(v0, v1);	double dot02 = DotProduct(v0, v2);	double dot11 = DotProduct(v1, v1);	double dot12 = DotProduct(v1, v2);        double d = (dot00 * dot11 - dot01 * dot01);	double invDenom = 1.0 / d;	double s = (dot11 * dot02 - dot01 * dot12) * invDenom;	double t = (dot00 * dot12 - dot01 * dot02) * invDenom;        noPointInTriangle = !((s > 0) && (t > 0) && ((s + t) < 1.0));    }    i++; } return !noPointInTriangle;}

##### Share on other sites
Looks like you also have to change this bit:
       (((xpoints != x1) && (ypoints != y1)) ||        ((xpoints != x2) && (ypoints != y2)) ||        ((xpoints != x3) && (ypoints != y3)))) {

to:
      !(((xpoints == x1) && (ypoints == y1)) ||        ((xpoints == x2) && (ypoints == y2)) ||        ((xpoints == x3) && (ypoints == y3)))) {

..otherwise the edge-inclusive point-in-triangle test catches the points of the triangle itself, which obviously isn't helpful.

Also, with your barycentric coords test, I'm pretty sure you'll need to be using !((s >= 0) && (t >= 0) && ((s + t) <= 1.0)); for the signs there too.

##### Share on other sites
Thanks mattd, that was it! Got it working with the barycentric test.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 26
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
633711
• Total Posts
3013488
×