**0**

# delaunay triangulation code

Started by Aug 30 2005 09:14 AM

,
4 replies to this topic

###
#1
Members - Reputation: **100**

Posted 30 August 2005 - 09:14 AM

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/

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/

###
#2
Members - Reputation: **287**

Posted 31 August 2005 - 08:37 AM

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));

}

}

}

}

###
#4
Members - Reputation: **287**

Posted 15 September 2005 - 03:23 AM

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!

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!

###
#5
Members - Reputation: **451**

Posted 16 August 2011 - 12:45 PM

Here is a link for a 2D delaunay triangulation example in C# http://vasilydev.blogspot.com/2011/08/delaunay-triangulation-example-in-c.html