4
\$\begingroup\$

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

Great! now the simple question appears:enter image description here

How do you programmatically tell in the human sense if v_orange and v_green are on the same side of the trail and if v_green and 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.

  1. 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).
  2. 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.
  3. Dijkstra from each of the trail side vertices to the vertices in question.
  4. 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.

Here is one fault in this solution: enter image description here Sometimes the two are on the same side and the other route is shorter.


Clarification

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.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ @Steven The first sentence said "we have a 3d model"? Not sure your inquiry was comprehensible? \$\endgroup\$ – wolfdawn Dec 26 '15 at 16:26
3
\$\begingroup\$

I believe the solution is simple - mark vertices of the path as impassible and run regular Dijkstra for this input. If it fails to find a path you are sure they are on different sides.
Edit: If your path does not split the graph into two components you can still use method described above with only difference - after finding the shortest route check whether it contains endpoints of the path. If it contains exactly one endpoint, you know the points lies on different sides (if it contains both of them, you know it went "the other way around", in example given in question it would take the bottom path, points still can be assumed on same side).


You might point out now: "But unsuccessful Dijkstra will visit every vertex of the component!". Yes that is correct, and there can be no other way - imagine the example given in answer what if there was not just the spike but whole labyrinth? Running full Dijkstra is necessary if you need 100% correct answer (OP found in solution it will give you only "maybe" answers otherwise).
If the speed proves to be problem, and you are confident that the path is "simple enough" you can speed the process up by giving up early, after n steps this should give better results with A* instead of plain Dijkstra. Alternatively, you can do (offline) pre-computation by giving each vertex its component ID using flood fill, this is way fastest solution(for answer just compare component IDs), but also the least flexible one.

\$\endgroup\$
  • \$\begingroup\$ You have it all wrong... It will always find a path. The trail is not a cycle that splits the model into two parts. So in other words you suggested to use some computational resources and then return true. \$\endgroup\$ – wolfdawn Dec 26 '15 at 16:27
  • 2
    \$\begingroup\$ @zehelvion if the trail does not split the model, then you question is not well-defined. In that case it can never lies on the other side of trail. What is your criterion to say it lies on different sides? \$\endgroup\$ – wondra Dec 26 '15 at 16:47
  • \$\begingroup\$ @ when you (a virtual character or camera) move from the starting point to the finish point always looking forwards (same as the velocity vector), is this item on the left side or the right side. If they are both on the left, it's the same. If one is on the right and the other is on the left, they are different. If both are on the right, it's the same. You must have walked in paths a couple of times. The vertices are near the path. You are thinking Math instead of Pragmatic Game programming friend. Is the concept of a camera looking left and right, targeting something alien (as in unfamiliar)? \$\endgroup\$ – wolfdawn Dec 29 '15 at 17:50
  • \$\begingroup\$ @zehelvion like it or not, computers work only with (subset) of mathematics. While one can get away with lack of knowledge of math when coding, it is essential when programming especially in relation with algorithms. Dont give up on math, nobody likes it but everybody needs it, more than you realize. Also updated the answer with new idea how to "split" object surface without actually splitting it. \$\endgroup\$ – wondra Dec 30 '15 at 17:02
  • \$\begingroup\$ Have a degree in Comp-Sci + many courses in Math from an established University. finished in the top third of my class for every math class I've taken except Probability. Thinking you might have the wrong idea cause your understanding of the question is constrained somehow and you're insisting it's not. Could go on establishing my Mathematical credibility, doing so online seems futile. Take it easy mate. \$\endgroup\$ – wolfdawn Jan 5 '16 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.