Sign in to follow this  

delaunay triangulation code

This topic is 2310 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've been experimenting with the Delaunay triangulation code on page 187 of the book Computational Geometry in C (1998 edition), and it doesn't seem to work properly. In particular, it doesn't seem to find all the triangles of the Delaunay triangulation. Here's my code, which is slightly modififed from the book: double rand01(void) { double num = double(rand())/double(RAND_MAX); return num; } void drawdelaun(void) { float x[NMAX], y[NMAX], z[NMAX]; int n; int i, j, k, m; float xn, yn, zn; int flag; glBegin(GL_LINES); n = 30; for (int ctr = 0; ctr < n; ctr++) { x[ctr] = rand01()*2-1; y[ctr] = rand01()*2-1; z[ctr] = x[ctr] * x[ctr] + y[ctr] * y[ctr]; } for (i = 0; i < n - 2; i++) for (j = i + 1; j < n; j++) for (k = i + 1; k < n; k++) if ( j != k) { xn = (y[j]-y[i])*(z[k]-z[i]) - (y[k]-y[i])*(z[j]-z[i]); yn = (x[k]-x[i])*(z[j]-z[i]) - (x[j]-x[i])*(z[k]-z[i]); zn = (x[j]-x[i])*(y[k]-y[i]) - (x[k]-x[i])*(y[j]-y[i]); if (flag = (zn < 0)) for (m = 0; m < n; m++) flag = flag && ((x[m] - x[i])*xn + (y[m] - y[i])*yn + (z[m] - z[i])*zn <= 0); if (flag) { glColor3f(1, 1, 1); glVertex2f(x[i], y[i]); glVertex2f(x[j], y[j]); glVertex2f(x[j], y[j]); glVertex2f(x[k], y[k]); glVertex2f(x[k], y[k]); glVertex2f(x[i], y[i]); } } glEnd(); } Anyone have any ideas? Thanks. mike http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
Hmm dunno, but here's my code that works:


for (unsigned int i=0; i<mNodeCount-2; i++)
{
for (unsigned int j=i+1; j<mNodeCount-1; j++)
{
for (unsigned int k=j+1; k<mNodeCount; k++)
{
if (!c.CircumCircle(pts[i], pts[j], pts[k]))
{
// Slight Hax0r: move (last) point a bit so not collinear.
LOG("Warning: had to shift collinear network point.");
pts[k] += pts[k]*0.0001f;

if (!c.CircumCircle(pts[i], pts[j], pts[k]))
{
LOG("Error: can't create triangulation!");
return false;
}
}

pointValid = true;
for (unsigned int l=0; l<mNodeCount; l++)
{
if (l != i && l != j && l != k)
{
if (c.IsPointInside(pts[l]))
{
pointValid = false;
break;
}
}
}

if (pointValid)
{
// Add triangle as graph links
Node(i).AddLink(Node(j));
Node(j).AddLink(Node(k));
Node(k).AddLink(Node(i));
}
}
}
}

Share this post


Link to post
Share on other sites
Interesting. How did you come up with that?

Can you tell me what the object c represents and what the IsPointInside function does?

Thanks.

mike
http://www.coolgroups.com/

Share this post


Link to post
Share on other sites
Whoops sorry, been away for a while...

Code was sort of from here (the java code, not the Guibas-Stolfi stuff).

c is my circle class.
CircumCircle() creates the circle with the 3 given points on its circumference.
IsPointInside returns whether the given point is inside the circle.

If you're working with any sort of geometry, a good circle class can simplify/reduce/encapsulate a lot of work for you!

Share this post


Link to post
Share on other sites

This topic is 2310 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this