Surface Intersecting Mesh

Intro

Consider the problem where given a 2D convex mesh and a polyline find the intersection points of the polyline with the mesh.

This was a problem raised in a GCAL discussion mailing list where the person asking the question was looking for a computationally fast algorithm to do this.

This problem can be generalized to any dimension where given a N-1 dimensional surface and a convex N dimensional object find the intersections.

Solutions 2D

Let the mesh have O(M) points and the polyline have O(N) points.

Let the mesh be linked.
From the starting segment of the polyline find a starting triangle on the mesh that the segment intersects.

Iterate over the polyline and mesh together O(M+N).
The segment is either inside the current triangle or intersects a border or through a point. Find the intersection if it exists and move to the next polyline segment.

If the mesh is not connected a brute force approach could be used.

Let i be each segment in the polyline
    Let k be each triangle face in the mesh
        Test if i intersects k and save the intersection point if it exists.

Clearly this is a O(MN) method.

<TODO>

• Implement in 2D