I have a this mesh with different surfaces. Of each surface I got its vertices. Now I want to create edges ( connect the vertices with lines). The vertices are in an arbitrary order, so I can’t simply connect v1 with v2, v2 with v3 and so on. I think I have to walk through them with a ray clockwise or counter clockwise and put them in the right order somehow and I have to somehow check their distances, so that the horizontal line between the inner vertices doesn’t appear, rather it should go right along the real edges,but I don’t know how… Any idea?
(the spheres are the vertices that are the real corners of the surface, the orange lines are the wrong edges that need to be corrected and the blue lines are the edges of each single face)
yes they are in 2D, but a 3D solution would be even better.
I need the 8 edges (here in red) - how that happens, doesn’t matter.
with regard to convex - I tried a convexhull but it results in a rectangle and it doesn’t consider the 2 inner lower vertices
It is not obvious how that single example generalizes to an arbitrary set of points.
Let me guess: You want the shortest path (or at least a very short one) that visits all vertices and does not intersect itself.
This has very little to do with computer graphics, but a lot to do with discrete mathematics, optimization metaheuristics etc… You may eventually have more success asking elsewhere. Nonetheless, it is an interesting challenge.
Some brainstorm thoughts:
Read about the Travelling Salesman Problem, with the addition of constraints.
Use a Genetic Algorithm with a cost function depending on total distance and on constraint violation (min-conflicts).
There are O(n^4) possible conflicts to consider, where n is the number of nodes.
Weight the severity of a conflict by a function of the proportion of individuals in the GA population that violate the same constraint. Something like w = log(1-V/(N+1))(edited), where V is the number of individuals that violate the constraint.
The population may be initialized with a set of good first guesses. They may be generated e.g. by first ordering vertices by angle around some assumed center point (such as the average position) and then applying a simple heuristic repeatedly from each of the points, such as “go to the nearest unvisited point that does not require an intersection, or else go to the nearest unvisited point”.
Mutations may defined as swapping of consecutive nodes.
A GA like this is not guaranteed to give an optimal, or even valid solution, or to be suitable for real-time updates. For a limited number of nodes, the chances are good, though. (For a very low number of nodes, you may also test all permutations by brute force.)
A faster and more stable solution may be to first order vertices by angle, and then start a depth-first search from any one node, which at each search depth step considers the nodes in order according to whether they are skipped already, and then by angle. A search branch returns false at any step if no continuation without intersections is found. The first valid path through all vertices is returned as the solution. (I am very unsure this solution will always be fast, as the search space is exponential with depth, while the number of valid solutions may also be huge. The heuristic of checking the nearest angles first will help in a lot of cases, but one may probably construct cases where that heuristic fails.)
In the general case, one will need fast intersection tests, which would be another job for a spatial index.
Line intersections are not an issue the same way in 3D as in 2D, so you would have to clarify what you mean by “a 3D solution”. Do you assume some projection from 3D down to a given 2D plane? Or are you interested in some generalization to surfaces built from triangles that have the original vertices as corners?
First of all, thanks for helping me. I’m not getting how the vertices’ angles could help here. Do you mean their angles to one another? If so, how would these angles help me? Could you explain?
With regard to the 2D 3D issue: For now I’m using meshes with flat surfaces, thats why I said 2D would be enough right now, but a 3D solution would be even better If I’d expand to circles and cylinders as well.
Let’s take an example where the benefit is obvious: You have a lot of vertices which are all positioned on the perimeter of a circle. You would like to connect the vertices into a polygon, but you do not control the order in which you consider the vertices when you are to decide which edges you will draw. Would you not prefer in that case that the vertices were ordered by angle around some point within the circle, so that the first edge you get to consider is to the next vertex on the circle?
This generalizes well to convex polygons, but for non-convex polygons it does not readily generalize. However, I think it is still a useful heuristic.
If you know which vertex belongs to which face, then it’s possible to form pairs of points, and then you compare ends of such “lines” by their coordinates (with some tolerance), sort of you make a chain.
Thanks for your ideas, thought days about it. I solved it by looking for all adjacent surfaces. Each of those share two corners with the current surface between these two corners is an edge
between these two corners is an edge 
