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:
Navigating a Delaunay triangulation

Subject: Navigating a Delaunay triangulation

From: carlos lopez

Date: 18 Aug, 2009 15:35:23

Message: 1 of 3

Hello:
I have a Delaunay triangulation for a region, plus a polyline which might cross the region, be inside the region, or any combination you might guess. My final goal is to augment the polyline with additional extra intermediate vertex located along it and at the crossed edges of the triangles.
To my surprise, I found no ready-made procedure to carry the task. I wrote some code, but it fails here and there when the polyline cuts a triangle exactly in a vertex, and hopefully I will have some problems when an edge coincides with part of the polyline.
I found no seemengly related code looking at www.qhull.org, neither at FEX.
As an intermediate result, I would like to find which triangles of a delaunay triangulation are crossed by a given polyline. Doesn't look too strange a requirement, but... apparently no one else have had the problem before.
I might use brute force, intersecting every edge of the triangulation and the polyline. Very crude, but possible... However, I have yet to devise how to build the right vertex order in the resulting polyline.
Regards
Carlos

Subject: Navigating a Delaunay triangulation

From: Damian

Date: 24 Aug, 2009 18:24:19

Message: 2 of 3

"carlos lopez" <clv2clv_00000000_@adinet.com.uy> wrote in message <h6ehnr$b3p$1@fred.mathworks.com>...
> Hello:
> I have a Delaunay triangulation for a region, plus a polyline which might cross the region, be inside the region, or any combination you might guess. My final goal is to augment the polyline with additional extra intermediate vertex located along it and at the crossed edges of the triangles.
> To my surprise, I found no ready-made procedure to carry the task. I wrote some code, but it fails here and there when the polyline cuts a triangle exactly in a vertex, and hopefully I will have some problems when an edge coincides with part of the polyline.
> I found no seemengly related code looking at www.qhull.org, neither at FEX.
> As an intermediate result, I would like to find which triangles of a delaunay triangulation are crossed by a given polyline. Doesn't look too strange a requirement, but... apparently no one else have had the problem before.
> I might use brute force, intersecting every edge of the triangulation and the polyline. Very crude, but possible... However, I have yet to devise how to build the right vertex order in the resulting polyline.
> Regards
> Carlos

Hi Carlos,

The function you are looking for is called a Line Walk. While we have improved the computational geometry functions in release R2009a, we do not support the line walk, but we do provide some useful triangulation adjacency functions that should make it easier to implement.

Suppose your line segment is defined by points Pa, Pb, you could proceed as follows;

Construct a Delaunay triangulation using the DelaunayTri class.
Use the DelaunayTri pointLocation function to locate the triangle T enclosing Pa
Examine each edge Ei (i = 1:3) of T and compute the intersection between Ei and [Pa, Pb]. If Ei intersects [Pa, Pb] log the intersection point and step into the i’th neighbor of T. Repeat the procedure until you terminate at Tb, the triangle that contains point Pb.

Once you have iterated through the first step you can reduce the number of intersection tests by ignoring the triangle edge that was processed in the previous step. You can also potentially reject an intersection by testing whether Pb lies to the left/right of the oriented edge Ei, though this latter test may not save you much.

For more information on the new computational geometry features check out the following links;

http://www.mathworks.com/products/demos/shipping/matlab/demoDelaunayTri.html

http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/trirep.html

http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/delaunaytri.html


Let me know if you need more details.


Damian

Subject: Navigating a Delaunay triangulation

From: carlos lopez

Date: 25 Aug, 2009 03:31:03

Message: 3 of 3

Thank you Damian. I'll do my best.
Regards
Carlos

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