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:
delaunay triangulation meets cartesian grid

Subject: delaunay triangulation meets cartesian grid

From: Sam Van der Jeught

Date: 4 Jan, 2011 10:00:14

Message: 1 of 5

Hi all,

I have some scattered data points and I've delaunay traingulated them. I plot them and get a nice image of all the points being connected in triangles in the typical delaunay way.

The next thing I want to do, is to impose a cartesian grid onto this map of triangles and find out, for each pixel, which are the triangles that have some part in that pixel. For example, let's say we have the case where there is one original data point completely in the pixel, then we can have up to 6 neighbouring triangles that are all for some certain percentage in this pixel. I want to know what that percentage is, and what the vertices of those triangles are.

I'm kind of stuck on this, so if any of you has a brilliant idea, please let me know,

Thanks,

Sam

Subject: delaunay triangulation meets cartesian grid

From: Yumnam Kirani

Date: 4 Jan, 2011 10:36:06

Message: 2 of 5

If you could show a graph of what you are intending to do, it would be helpful to understand your problem more clear.

Yumnam Kirani Singh
Tronglaobi Awang Leikai
 
"Sam Van der Jeught" <sam_vanderjeught@hotmail.com> wrote in message <ifur3e$oda$1@fred.mathworks.com>...
> Hi all,
>
> I have some scattered data points and I've delaunay traingulated them. I plot them and get a nice image of all the points being connected in triangles in the typical delaunay way.
>
> The next thing I want to do, is to impose a cartesian grid onto this map of triangles and find out, for each pixel, which are the triangles that have some part in that pixel. For example, let's say we have the case where there is one original data point completely in the pixel, then we can have up to 6 neighbouring triangles that are all for some certain percentage in this pixel. I want to know what that percentage is, and what the vertices of those triangles are.
>
> I'm kind of stuck on this, so if any of you has a brilliant idea, please let me know,
>
> Thanks,
>
> Sam

Subject: delaunay triangulation meets cartesian grid

From: Sam Van der Jeught

Date: 4 Jan, 2011 11:04:07

Message: 3 of 5

Hi,

I made a simple drawing of what it's supposed to do. I only drew the effect for one pixel, but the others should be treated likewise. In this example, red and green will have the highest surface precentage in the pixel.

http://i56.tinypic.com/t6x8av.png

Sam

Subject: delaunay triangulation meets cartesian grid

From: Sam Van der Jeught

Date: 4 Jan, 2011 11:05:20

Message: 4 of 5

Hi,

I made a simple drawing of what it's supposed to do. I only drew the effect for one pixel, but the others should be treated likewise. In this example, red and green will have the highest surface precentage in the pixel.

http://i56.tinypic.com/t6x8av.png

Sam

Subject: delaunay triangulation meets cartesian grid

From: John D'Errico

Date: 4 Jan, 2011 11:07:05

Message: 5 of 5

"Sam Van der Jeught" <sam_vanderjeught@hotmail.com> wrote in message <ifur3e$oda$1@fred.mathworks.com>...
> Hi all,
>
> I have some scattered data points and I've delaunay traingulated them. I plot them and get a nice image of all the points being connected in triangles in the typical delaunay way.
>
> The next thing I want to do, is to impose a cartesian grid onto this map of triangles and find out, for each pixel, which are the triangles that have some part in that pixel. For example, let's say we have the case where there is one original data point completely in the pixel, then we can have up to 6 neighbouring triangles that are all for some certain percentage in this pixel. I want to know what that percentage is, and what the vertices of those triangles are.
>
> I'm kind of stuck on this, so if any of you has a brilliant idea, please let me know,
>

It will take some work. Doable. But not trivial, since
its a big search problem, and then on top of that you
need to test to see if there is any intersection of a pair
of polygonal domains.

At first thought, I'd do something like compute the set
of circumcircles for each triangle. This will tell you if a
triangle has any possible intersection with a given pixel.
Once you can narrow down the set of triangles which
MAY intersect a pixel, then you apply a more accurate
test.

The above scheme will work. Probably faster is to build
a quad-tree form the triangulation. Use that to potentially
more efficiently find a list of triangles that may intersect
a given pixel. Then do the same operations I described
above. Again, it becomes a test for the intersection of
two polygonal domains. In the end it must come down
to that.

Nothing will avoid doing some work here. There is no
magic.

John

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