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

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]



               

"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.

           

"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

"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

> 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.