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:
Is there any fast algorithm to get the intersection of the mesh and a polygon?

Subject: Is there any fast algorithm to get the intersection of the mesh and a polygon?

From: zedong

Date: 12 Jan, 2009 11:14:02

Message: 1 of 5

I have a triangulationed domain using triangle.Also I have a polygon.I want to find out all the intersection point coordinate?
Is there any fast algorithm?
for example:
the mesh data:
node=[0 0;1 0;1 1;0 1];%node is all the vertex of the mesh
elem=[1 2 3;1 3 4];%store each triangle elem(i,:) is the ith element.It store the three vertex of this element.
the above is the mesh data.
the polygon data:
     polyvertex=[-0.4 -0.4;0.4 -0.4;0.4 0.4;-0.4 0.4]



               

Subject: Is there any fast algorithm to get the intersection of the mesh and a polygon?

From: Matt

Date: 12 Jan, 2009 13:09:02

Message: 2 of 5

"zedong
" <zdongwu@gmail.com> wrote in message <gkf8lq$dc2$1@fred.mathworks.com>...
> I have a triangulationed domain using triangle.Also I have a polygon.I want to find out all the intersection point coordinate?
> Is there any fast algorithm?
> for example:
> the mesh data:
> node=[0 0;1 0;1 1;0 1];%node is all the vertex of the mesh
> elem=[1 2 3;1 3 4];%store each triangle elem(i,:) is the ith element.It store the three vertex of this element.
> the above is the mesh data.
> the polygon data:
> polyvertex=[-0.4 -0.4;0.4 -0.4;0.4 0.4;-0.4 0.4]


In previous threads we talked about a way to find the intersection point of a line segment and a triangle. The same algorithm will find the intersection of a line segment with a 2D polygon. So you could loop over the line segments of your triangles and find their intersection with the polygon.

           

Subject: Is there any fast algorithm to get the intersection of the mesh and a polygon?

From: zedong

Date: 12 Jan, 2009 13:54:02

Message: 3 of 5

"Matt " <mjacobson.removethis@xorantech.com> wrote in message <gkffde$ani$1@fred.mathworks.com>...
> "zedong
> " <zdongwu@gmail.com> wrote in message <gkf8lq$dc2$1@fred.mathworks.com>...
> > I have a triangulationed domain using triangle.Also I have a polygon.I want to find out all the intersection point coordinate?
> > Is there any fast algorithm?
> > for example:
> > the mesh data:
> > node=[0 0;1 0;1 1;0 1];%node is all the vertex of the mesh
> > elem=[1 2 3;1 3 4];%store each triangle elem(i,:) is the ith element.It store the three vertex of this element.
> > the above is the mesh data.
> > the polygon data:
> > polyvertex=[-0.4 -0.4;0.4 -0.4;0.4 0.4;-0.4 0.4]
>
>
> In previous threads we talked about a way to find the intersection point of a line segment and a triangle. The same algorithm will find the intersection of a line segment with a 2D polygon. So you could loop over the line segments of your triangles and find their intersection with the polygon.
>
>

Thank you very much for your kind help.Your algorithm is very excellent.But now the polygon may not be convex.And I need to add these intersection point in the polygon
Thank you for another time

Subject: Is there any fast algorithm to get the intersection of the mesh and a polygon?

From: Kenneth Eaton

Date: 12 Jan, 2009 15:56:02

Message: 4 of 5

"zedong
" <zdongwu@gmail.com> wrote in message <gkfi1q$7no$1@fred.mathworks.com>...
> Thank you very much for your kind help.Your algorithm is very excellent.But now the polygon may not be convex.And I need to add these intersection point in the polygon
> Thank you for another time

I don't know if this will help you any more than Matt already has, but I had submitted some code to the File Exchange (http://www.mathworks.com/matlabcentral/fileexchange/20637) that could find the intersections of line segments and rendered triangular surfaces. You might be able to adapt the guts of my code (the triangle-line intersection part) for your purposes. You would just break your polygon into its individual lines.

hth,
Ken

Subject: Is there any fast algorithm to get the intersection of the mesh and a polygon?

From: Matt

Date: 12 Jan, 2009 16:07:01

Message: 5 of 5

> Thank you very much for your kind help.Your algorithm is very excellent.But now the polygon may not be convex.And I need to add these intersection point in the polygon


But the triangles are convex, so as Ken pointed out, you can break the polygon into individual lines and use the previous algorithm to find their intersections with the triangles.

Tags for this Thread

No tags are associated with 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