We have a 3d model. There is a simple path on that model's surface graph
G of the form:
<v_0, v_1 ... v_n-1, v_n> where if v_i == v_j then i == j
How do you programmatically tell in the human sense if
v_green are on the same side of the trail and if
v_blue are on the same side or not?
My intuition is that you Dijkstra the shortest path between them and if it goes through the trail an even number of times their on the same side. However that is not defined if you don't know what goes through the trail computes to. If thinking if it was 2d and we could project these trail edges on some flat surface this would be made trivial.
My current solution is a lie. Each edge is normally shared by two faces unless it's an orbifold which is currently not interesting to this question's input population set. Also, in our world, each face has percisely three vertices.
- Use Dijkstra to find the shortest path between them. If the path does not touch the trail, their relation to the trail isn't well defined or their on the same side (for now it outputs they are on the same side).
- Assuming the path does go through the path, we pick one of the edges it went through. Each edge belongs to two faces, each of these faces has precisely one vertex that is not on the edge trail. we now have two vertices that are supposed to be on different sides of the trail.
- Dijkstra from each of the trail side vertices to the vertices in question.
- If the shorter path to both vertices in question is from the same side then maybe they are on the same side. If it each vertex prefers a different side then maybe they are not.
This is a clarification inspired by wondra that felt nothing can be on the right side or the left side of a trail, something that in my opinion people would disagree with as we have a good sense of left & right.
Lets "split" the model where the trail is and add more faces between the two new trails (lips) and get something like this:
Trail 1 is
Blue, trail 2
Red and some epsilon wide faces between them. Now we use Dijkstra to find the shortest distance from both trails (Blue and Red). Some vertices are closer to the
Red, some to
Blue. Very few are (the same), closest simply to the last or first vertex in the original trail that are conjoined between the trails.