Jump to content
  • Advertisement
Sign in to follow this  
rootbender

Earcutting algorithm

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

If you intended to correct an error in the post then please contact us.

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 Free Image Hosting at www.ImageShack.us<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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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[]);


int
main(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;
}


void
RunTest(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 this post


Link to post
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).

With their bad point-in-polygon checking, looks like your result:


Without:


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


My implementation, for reference:


import csv

import Image
import ImageDraw

def 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 es

def convexPt(t):
return area(t) < 0

def 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 True


def 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])
) / 2

ps = [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 this post


Link to post
Share on other sites
Quote:
Original post by mattd
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.


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:

bool
EarCutter::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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!