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:
add-remove edges in a delaunay triangulation

Subject: add-remove edges in a delaunay triangulation

From: Faisal Ahmed

Date: 6 Jul, 2010 15:58:08

Message: 1 of 4

Hi, I want to do the following:

1. Construct Delaunay Triangulation T
2. Remove edges from specific nodes in T if node degree > D
  (By node degree, I mean the number number of edges connected to each vertex of triangle.)
3. Add edges to specific nodes in T if node degree < D

I am a new user in Matlab. I could only do the basic triangulation but due to my lack of knowledge, I could not proceed further. If anyone can help, I would be very grateful.

Subject: add-remove edges in a delaunay triangulation

From: Faisal Ahmed

Date: 6 Jul, 2010 16:06:04

Message: 2 of 4

By the way I used the following code for basic triangulation

x = rand(10,1);
y = rand(10,1);
dt = DelaunayTri(x,y)
triplot(dt);

Subject: add-remove edges in a delaunay triangulation

From: Roger Stafford

Date: 6 Jul, 2010 18:06:15

Message: 3 of 4

"Faisal Ahmed" <fap87@yahoo.com> wrote in message <i0vjqg$ftk$1@fred.mathworks.com>...
> Hi, I want to do the following:
>
> 1. Construct Delaunay Triangulation T
> 2. Remove edges from specific nodes in T if node degree > D
> (By node degree, I mean the number number of edges connected to each vertex of triangle.)
> 3. Add edges to specific nodes in T if node degree < D
>
> I am a new user in Matlab. I could only do the basic triangulation but due to my lack of knowledge, I could not proceed further. If anyone can help, I would be very grateful.
- - - - - - - - - - -
  I think you need to explain what you are trying to do and why you are doing it in far greater detail. What you have described so far seems like some kind of random, reckless procedure. It is as though you had said "I have a matrix with too many elements in it and wish to remove some of them. How do I do that?"

  Removing edges from a triangulation will yield quadrilaterals or other polygons so you would no longer have a triangulation. On the other hand adding edges encounters the difficulty that you may produce edges that cross over each other which would also not be a valid triangulation. If you remove an edge because the "degree of one of its endpoints is too great, that also lowers the "degree" of the other end even if that one was below your D. When a vertex has too great a "degree", which connecting edge do you wish to remove? If you remove or add edges one at a time, the order in which this is done may well affect which edges are to be removed or added later on.

  Also you need to realize that by making such alterations you will almost certainly lose the fundamental delaunay property that "no data points are contained in any triangle's circumscribed circle".

Roger Stafford

Subject: add-remove edges in a delaunay triangulation

From: Faisal Ahmed

Date: 7 Jul, 2010 08:57:03

Message: 4 of 4

If removing or adding edges spoil the triangulation than it will not be a problem for me. I want to use the final pattern as a topology of my free space optical sensor network.

If removing an edge from one point lowers the degree of the other end, it's also fine.

In case of a vertex having too great a degree than expected, the edge removal will be done in this way: the longest edge will be removed first, and so on.

In case of adding edges to a node where the degree is low, it will be connected to another neighbor node who is also short in degree. If every possible neighbor node has satisfactory degree, than I may just leave the node with it's lower degree.

*** It may sound weird, but I need the final diagram only for a topology design. It doesn't have to look like a triangulation at the end.

Thanks for your quick reply.

-Faisal

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