[Closed] Getting the verts between two vertices

Hello simchris.

Think that the path you have drawn is not the unique one to go from one vertex to the other.
You need to find a function that searchs the shortest (¿?) path between them.
I don’t know if someone has already written something similar.

First you have to collect the vertices that has only 2 edges. After that search for the nearest vertices and test if they connectable. If not get the second nearest that has two edges and test again. That’s how I should do it. (I’m on holiday so I can’t test it for you, but probably it should work.)

I’ve been looking into something similar myself recently, but not started on a solution yet.

However this might be of use for finding shortest path between 2 points in a network(verts and edges)

http://www.redblobgames.com/pathfinding/a-star/introduction.html

Oh I see that the vertices are connected (sorry on mobile phone it wasn’t visible) I thought they aren’t connected.

In this case the solution is much different. You have to select the first and the last vertex, than find the nearest vertices of the first vertex. Than just search from these vertices, which one is the closest to the last vertex. If you have found it than that one will be your next vertex. Do the same thing with the next vertex.

What if there is a gap between the start and end vertex? or one of them is on a peninsula? Just traversing the mesh from start to end looking for the closer vert on the way wont work in that case.

The gap means in this case that they are on different elements. In any other cases they are on the same element which means they can be connected.

The other scenario is more problematic. What if the shortest distance between the two point is leading through on a path that is longer, where the individual vertices are farther and farther from the , or when the closest vertex method leads to a border, which means that the mesh is not closed…

Ok I see the problem. Not easy… I will try thinking on this problem too…

I think a first attempt should be selecting by hand (or by code) a “hot area” of vertex to reduce the search.
Second, suppose we go from the right vertex to the left one. The “logical” path should always be selecting the second vertex to the left of the first one, discarding those on the right. Between those in the left side, I think it’s better to select the vertex which vector with the previous one points nearest to the target instead of selecting the one which is nearest to the target. It’s more a feeling than knowhow.

If any vertex to the left, take one to the right with the smallest angle and go on.

Ok I have another idea. If you start expanding a selection from a vertex, than sooner or later you will reach the designated target. You just have to grow and test, than grow and test again, until you reach the target vertex.

With the last function you will get the exact number of steps you need to reach the second vertex. And here comes the second part, that I don’t know which one.

Ok back to the drawing board…

(But anyway this might be useful for something that is straightforward. )

Yes, this is basically the technique. See the link I posted earlier in the thread and you will see the methodology there.
so you expand the selection each pass and with each new vert connected to the blob you store the vert it came from.
So when you finally reach your target vert you can follow the stored links all the way back to the start and there is your connected path. Its like walking though the forest leaving breadcrumbs as you go so you can find your way back.

There’ s a bit more after that to find which is the shortest path, but that is the essense