I write on with ++. There is a 3d model (stl file), which consists of triangles. I need to find the shortest path between two vertices along the edges of the triangles, as I understand it, along the edges of the graph. Which container should I use to store vertex structures? Or maybe it is better not to store the vertices, but something else edges, for example? How is it generally better to form the input data? I apologize if a poorly formulated question is given this topic very poorly.

Stl file structure of binary format

  • A graph can be defined via an adjacency matrix, an adjacency list, an incidence matrix, or a list of edges ( Graph (mathematics) —Ancards for representing a graph in computer science ). How to implement it programmatically - many options. - insolor
  • @insolor And can you give an example of how you can programmatically implement it. In general, at least. - WhoAreYou
  • In any case, you will have to store vertices, since each vertex has its own characteristics. Next you need to somehow set the connection between the vertices. Best of all, as I understand it, it will be implemented through a list of edges . It is better to store the vertices separately, and in the adjacency list use pointers to the vertices. With the implementation I will not help, because I do not write in C ++. - insolor
  • And why do not you realize your container and call it a graph. Those. Each element of the container is a vertex and has pointers to the vertices with which it is associated. - Unick
  • IMHO, the formulation of the problem is not entirely correct: one should think not how to store the graph, but in what form to feed it to the algorithm ... because here it seems that Dijkstra’s algorithm will be used, and | V | comparable to | E |, then the natural option would be to use adjacency lists. Next, the question of what to do with the values ​​of the weights - in this case, I would keep them together with the lists - is likely to increase the locality of the algorithm; although it is possible to calculate and store each time separately ... - Fat-Zer

0