Situation is like that, there is a mesh, I cut it with a plane (actually I intersect the meshes edges). This produces a set of points, and I need to make a face based on those points. But I don’t know the order of the points. Is there a simple way to get the order?
This mesh is not very complex; it can be approximated to a cube. And all the newly created points are on one plane.
I thought that it can be done by calculating the medium value of the set of points, and then converting to the polar coordinate system, with the center in this medium point, so the angle would naturally sort all points, but I’m having a hard time to rotate the plane so I could omit one coordinate. Any solutions or simpler ways?
If the shape is very simple (convex+dense points) :
- start with any point A
- go to the nearest point B
- go to point C (nearest to B that is not C) -> first triangle.
Then build up on this, each time going to nearest point.
Yes, shape is simple, but not trivial. I tried this solution already and unfortunately it is not enough. If the shape is rhombus for example, finding nearest neighbor fails in cases like this.
There is no general way to find the information just from the points.
Imagine the result is 6 points on a circle and one in the center. The result could be a hexagon with a triangle cut out of it, but there is no way of knowing which triangle…
To get the correct solution, you have to use the face information of the original mesh. Whenever you cut a triangle by the plane, you get TWO points, connected by a line segment. And you’ll get every point exactly twice (when the mesh is closed), so you know two line segments that have a common point are adjacent to each other.
From there it should be easy to get the order of the vertices in the edge region. You still may have to tesselate the result, because the polygon resulting from the vertices could be non-convex, have holes, …
There was in Cormen’s algorithm book something about geometry, and I’m not sure, do I understand your problem good, but “Graham’s algorithm”.
(http://www.cs.princeton.edu/~ah/alg_anim/version1/GrahamScan.html)
Usually, I implement that, takeing the point from
the bottom (and if there are more than one, takeing this one left), and after that, I’m using atan2 function (man atan2) to determine selection order.
I hope it was helpful.