Obtaining edge list from Delaunay triangulation

Peter Bone

unread,

Dec 13, 2010, 7:16:05 AM12/13/10

to

I'd like to get a list of unique edges from a Delaunay triangulation on a set of 2D points. The delaunay function returns the vertices of the triangles. If I extract the edges from this then most edges will be counted twice when performed for all triangles. My aim is to find the average distance of edges. I'm hoping for a simple method that doesn't require checking all previously found edges for each edge. Thanks.

Bruno Luong

unread,

Dec 13, 2010, 8:02:05 AM12/13/10

to

"Peter Bone" <pete...@hotmail.com> wrote in message <ie52q5$gtn$1...@fred.mathworks.com>...

> I'd like to get a list of unique edges from a Delaunay triangulation on a set of 2D points. The delaunay function returns the vertices of the triangles. If I extract the edges from this then most edges will be counted twice when performed for all triangles. My aim is to find the average distance of edges. I'm hoping for a simple method that doesn't require checking all previously found edges for each edge. Thanks.

Let T is the list of triangle vertices, the edges are

E = unique(sort([T(:,2) T(:,1); T(:,3) T(:,2); T(:,1) T(:,3)],2),'rows')

Bruno

Peter Bone

unread,

Dec 13, 2010, 8:41:07 AM12/13/10

to

"Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <ie55gd$2fa$1...@fred.mathworks.com>...

Great thanks. It would be much better if the delaunay function returned the edges as an optional output though.

Peter Bone

unread,

Dec 13, 2010, 8:46:08 AM12/13/10

to

"Bruno Luong" <b.l...@fogale.findmycountry> wrote in message <ie55gd$2fa$1...@fred.mathworks.com>...

My general problem is to compute some kind of metric for the density/compactness for a set of 2D points. My first method was to find the average distance from the mean. I'd like something that more considers distance from neighbouring points (maybe average distance between a point and its nearest neighbour). This is what I was attempting with the triangulation, although I now realise this won't work because of the long edges towards the boundary of the set of points. I need something fairly fast. Any ideas?

John D'Errico

unread,

Dec 13, 2010, 9:02:05 AM12/13/10

to

"Peter Bone" <pete...@hotmail.com> wrote in message <ie5830$hgk$1...@fred.mathworks.com>...

What Bruno suggested is the standard trick, and it will be
fast of course, but as you say, a delaunay triangulation
tends to generate long edges around the perimeter.

One option would be to use an alpha shape to delete
those long perimeter edges. Alpha shapes are fairly fast
to compute.

Another idea is to use a k-d tree to find the nearest
neighbor for all points. There are fast tools for this on
the FEX.

John

Steven_Lord

unread,

Dec 13, 2010, 9:38:32 AM12/13/10

to

"Peter Bone" <pete...@hotmail.com> wrote in message

news:ie52q5$gtn$1...@fred.mathworks.com...

Use the edges and/or freeBoundary methods of the DelaunayTri object,
depending on what exactly you mean by "average distance of edges".

http://www.mathworks.com/help/techdoc/ref/delaunaytriclass.html

--
Steve Lord
sl...@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlab.wikia.com/wiki/FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Peter Bone

unread,

Dec 13, 2010, 11:10:09 AM12/13/10

to

"John D'Errico" <wood...@rochester.rr.com> wrote in message <ie590t$4s6$1...@fred.mathworks.com>...

Thanks. I went for the kd-tree idea. I used the kd-tree code by pramod vemulapalli.

function c = compactness2(pts)
% Compute the KD tree for fast nearest neighbour searching
tree = kd_buildtree(pts,0);
num = size(pts,1);
% Find the average distance from nearest neighbour
d_sum = 0;
for p = 1 : num
index_vals = kd_knn(tree, pts(p,:), 2,0);
d = sum((pts(p) - pts(index_vals(2))).^2);
d_sum = d_sum + d;
end
c = sqrt(d_sum / num);