How to calculate the distance between X and Y with points of Intersection

2

In the image above I have mapped the separation positions inside the warehouse where I work. I need to calculate the distance that the person who is separating goes through the warehouse. For example if the person is separating in position 1AF-001-10 and moves to position 1AD-013-10 if I calculate only X and Y it will calculate in a straight line but it will be wrong I need it to go through the points of intersection is the problem. I do not know how I'm going to make him understand what points he needs to take to figure out the right route when he leaves the streets he's been ferrying. I put the intersection points that would be these connections ... and the right one I just can not reason as I do for him to understand what points he needs to get. For example in this case at the top it should calculate as follows:

    De           Para
1AF-001-10 || 1AD-013-10 = soma(valor1,valor2,valor3)

That is:

   De            Para
1AF-001-10  || interseçãoE = valor1

    De            Para
interseçãoE || interseçãoD = valor2

    De            Para
interseçãoD || 1AD-013-10 = valor3
    
asked by anonymous 30.06.2016 / 14:59

1 answer

3

A short answer that will require some research from the AP.

Model your problem as a graph and apply the algorithm A * . The nodes of your graph are your positions (1AF ...). Each edge of your graph is the link between two locations. If there is no connection, it means that the X position is not connected to the Y position. The edge will also load the distance information between each node.

At the moment you have this mounted graph, you just have to implement an algorithm with a smaller path (I indicated A *, but it may be the Dijkstra pure) and pass the initial and final node as parameters. The algorithm will return the smallest path between two locations, going through all intermediate positions.

As I said, it will require an initial research effort, but you have both an example of a graph on the Internet and both tutorials that will be worth it, because it will resolve the problem definitively.

    
30.06.2016 / 15:10