Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Obtaining edge list from Delaunay triangulation

Subject: Obtaining edge list from Delaunay triangulation

From: Peter Bone

Date: 13 Dec, 2010 12:16:05

Message: 1 of 7

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.

Subject: Obtaining edge list from Delaunay triangulation

From: Bruno Luong

Date: 13 Dec, 2010 13:02:05

Message: 2 of 7

"Peter Bone" <peterbone@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

Subject: Obtaining edge list from Delaunay triangulation

From: Peter Bone

Date: 13 Dec, 2010 13:41:07

Message: 3 of 7

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie55gd$2fa$1@fred.mathworks.com>...
> "Peter Bone" <peterbone@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

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

Subject: Obtaining edge list from Delaunay triangulation

From: Peter Bone

Date: 13 Dec, 2010 13:46:08

Message: 4 of 7

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie55gd$2fa$1@fred.mathworks.com>...
> "Peter Bone" <peterbone@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

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?

Subject: Obtaining edge list from Delaunay triangulation

From: John D'Errico

Date: 13 Dec, 2010 14:02:05

Message: 5 of 7

"Peter Bone" <peterbone@hotmail.com> wrote in message <ie5830$hgk$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie55gd$2fa$1@fred.mathworks.com>...
> > "Peter Bone" <peterbone@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
>
> 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?

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

Subject: Obtaining edge list from Delaunay triangulation

From: Steven_Lord

Date: 13 Dec, 2010 14:38:32

Message: 6 of 7



"Peter Bone" <peterbone@hotmail.com> wrote in message
news: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.

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
slord@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

Subject: Obtaining edge list from Delaunay triangulation

From: Peter Bone

Date: 13 Dec, 2010 16:10:09

Message: 7 of 7

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <ie590t$4s6$1@fred.mathworks.com>...
> "Peter Bone" <peterbone@hotmail.com> wrote in message <ie5830$hgk$1@fred.mathworks.com>...
> > "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ie55gd$2fa$1@fred.mathworks.com>...
> > > "Peter Bone" <peterbone@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
> >
> > 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?
>
> 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

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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us