Detecting arbitrary shapes

Greetings,

We have a set of points which represent an intersection of a 3d body and a horizontal plane. We would like to detect the 2D shapes that represent the cross sections of the body. There can be one or more suc开发者_StackOverflowh shapes. We found articles that discuss how to operate on images using Hough Transform, but we may have thousands of such points, so converting to an image is very wasteful. Is there a simpler way to do this?

Thank you

In converting your 3D model to a set of points, you have thrown away the information required to find the intersection shapes. Walk the edge-face connectivity graph of your 3D model to find the edge-plane intersection points in order.

Assuming you have, or can construct, the 3d model topography (some number of vertices, edges between vertices, faces bound by edges):

1. Iterate through the edge list until you find one that intersects the test plane, add it to a list
2. Pick one of the faces that share this edge
3. Iterate through the other edges of that face to find the next intersection, add it to the list
4. Repeat for the other face that shares that edge until you arrive back at the starting edge

You've built an ordered list of edges that intersect the plane - it's trivial to linearly interpolate each edge to find the intersection points, in order, that form the intersection shape. Note that this process assumes that the face polygons are convex, which in your case they are. If your volume is concave you'll have multiple discrete intersection shapes, and so you need to repeat this process until all edges have been examined.

There's some java code that does this here

The algorithm / code from the accepted answer does not work for complex special cases, when the plane intersects some vertices of a concave surface. In this case "walking" the edge-face connectivity graph greedily could close some of the polygons before time.

What happens is, that because the plane intersects a vertex, at one point when walking the graph there are two possibilities for the next edge, and it does matter which one is chosen.

A possible solution is to implement a graph traversal algorithm (for instance depth-first search), and choose the longest loop which contains the starting edge.

It looks like you wanted to combine intersection points back into connected figures using some detection or Hough Transform.

Much simpler and more robust way is to immediately get not just intersection points, but contours of 3D body, where the plane cuts it.

To construct contours on the body given by triangular mesh, define the value in each mesh vertex equal to signed distance from the plane (positive on one side of the plane and negative on the other side). The marching squares algorithm for isovalue=0 can be then applied to extract the segments of the contours:

This algorithm works well even when the plane passes through a vertex or an edge of the mesh.

To better understand what is the result of plane section, please take a look at this short video. Following the links there, one can find the implementation as well.