Sorting of vertices after intersection of 3d isosurface with plane

Here is another geometric problem:

I have created an 3-dimensional triangulated iso-surface of a point cloud using the marching cubes algorithm. Then I intersect this iso-surface with a plane and get a number of line segments that represent the contour lines of the intersection.

Is there any possibility to sort the vertices of these line segments clockwise so that I can draw them as a closed p开发者_如何学Goath and do a flood fill?

Thanks in advance!

It depends on how complex your isosurface is, but the simplest thing I can think of that might work is:

• For each point, project to the plane. This will give you a set of points in 2d.
• Make sure these are centered, via a translation to the centroid or center of the bounding box.
• For each 2d point, run atan2 and get an angle. atan2 just puts things in the correct quadrant.
• Order by that angle

If your isosurface/plane is monotonically increasing in angle around the centroid, then this will work fine. If not, then you might need to find the 2 nearest neighbors to each point in the plane, and hope that that makes a simple loop. In face, the simple loop idea might be simpler, because you don't need to project and you don't need to compute angles - just do everything in 3d.