[Date Index] [Thread Index] [Author Index]

Problem with Delaunay triangulation in Extend Graphics package

• To: mathgroup at smc.vnet.net
• Subject: [mg39650] Problem with Delaunay triangulation in Extend Graphics package
• From: jrome at mail.com (Jacob Rome)
• Date: Thu, 27 Feb 2003 00:31:25 -0500 (EST)
• Sender: owner-wri-mathgroup at wolfram.com

Hi,

I've been using the excellent Delaunay triangulation routine from
TWJ's ExtendGraphics package. I started having a problem with the
undtion Delaunay[], which would seemingly send the routine into a
loop, and it would stop responding.

I noticed another problem, too, whereas after triangulating a region
"A", a point "B" contained within region "A" was found to not be
within any of the delaunay triangles; I have checks in place for
collinearity and coincidence, so I could not figure out the problem.

While repeatable for a given set of points, these problems would not
occur consistently between <i>similar</i> sets of point. So I wrote a
routine to run some simple cheks on the algorithm. One set of tests
was to see what would happen if I specified repeated points. I wrote
the following:

<< ExtendGraphics`Delaunay`
a = {{1, 1}, {2, 2}, {1, 2}, {0, 3}, {4, 1}, {10, 5}, {9, 6}, {5, 5},
{3,5}, {4, 3}};

hull1 = Delaunay[a][[1]];
hull2 = Delaunay[Join[a, {a[[1]]}]][[1]];
h1Plot = Table[a[[hull1[[i]]]], {i, Length[hull1]}];
h2Plot = Table[a[[hull2[[i]]]], {i, Length[hull2]}];
j1 = ListPlot[h1Plot, PlotJoined -> True];
j2 = ListPlot[h2Plot, PlotJoined -> True];
Show[{j1, j2}];

When execting the program, it generates convex hull plots, which
should be identical. But they are not. Could this issue with repeated
points be at the root of my problem?