C++ 中的图形绘制/TSP 路线绘制与“已知”坐标:如何?哪个库/工具?
我正在为 C++ 中的车辆路由问题的变体开发某种启发式方法。
生成解决方案后,我想绘制该解决方案。解决方案是各种旅行的组合,所有旅行都在一个公共站点开始和结束。 因此,我有一个顶点集,其中所有坐标和边均由两个顶点 ID 定义。此外,我当然有顶点对之间的所有距离。
在我的程序中打开一个额外的窗口来绘制它会很有帮助,但是将绘图写入图形文件也应该没问题。
绘制此图的简单方法是什么?你会如何解决这个问题?
首先我尝试寻找常见的图形可视化包(graphviz、tulip、networkx(python)),但我意识到它们都专门用于图形布局(当没有坐标)。当我错的时候纠正我。 我不知道是否可以告诉这些包我已经有了坐标,以帮助布局算法。
接下来我尝试的是带有 geomview 输出的 CGAL 库 ->到目前为止还没有运气 -> ubuntu 使 geomview 崩溃。
还有一个问题:使用一些冒着绘图风险的非布局 2d 绘图库是否是一个更好的主意,这些库看起来不太好(除了缩放之外还有更多要做的事情吗?)还是使用一些基于布局算法的库(例如 graphviz、tulip、networkx),向它们提供顶点之间的距离,并希望布局算法在以易于查看的方式绘制时保持距离?
- 如果非布局绘图是实现此目的的方法:您推荐哪个库?
- 如果基于布局的绘图是实现这一点的方法:我如何利用这些库中的距离/坐标?您推荐哪个图书馆?
感谢您的所有投入!
Sascha
编辑:我使用 PLplot 库 (http://plplot.sourceforge.net/) 完成了原型实现。结果很好,目前应该足够了。我发现并选择这个库是因为一个相关项目(VRPH软件包/Groer)使用了这个图并且源代码已分发。所以在很短的时间内就完成了实施。我认为该 API 有点笨拙且低级。也许有一些更现代的(可能不是基于 C 的库)库?数学GL?迪斯林?也许我也会尝试一下。
在车辆路径问题中绘制多个路线的好处是,“不太糟糕”的算法往往会发现漂亮的非重叠和发散的路线,这对眼睛来说确实有好处;-)
i'm developing some kind of heuristics for a variation of the vehicle-routing-problem in C++.
After generating a solution, i want to plot this solution. The solution is a composite of various tours, all starting and ending at a common depot.
Therefore i have a vertex-set with all the coordinates and edges defined by two vertex-id's each. Furthermore i have all the distances between vertex-pairs of course.
It would be helpful to plot this in an extra-window opening in my program, but writing a plot to a graphics-file should be okay too.
What is an easy way to plot this? How would you tackle this?
First i tried to look for common graph-visualization packages (graphviz, tulip, networkx (python)), but i realized that all of them are specialized at graph-layouting (when there are no coordinates). Correct me when i'm wrong.
I don't know if it is possible to tell these packages that i already have the coordinates, helping the layouting-algorithms.
Next thing i tried is the CGAL library with geomview output -> no luck until now -> ubuntu crashes geomview.
One more question: Is it a better idea to use some non-layouting 2d-plot-libraries risking a plot, which isn't really good to view at (is there more to do than scaling?) or to use some layout-algorithm-based-libraries (e.g. graphviz, tulip, networkx), feed them with the distances between the vertices and hope the layouting-algorithms are keeping the distances while plotting in a good-to-view-at way?
- If non-layouting-plotting is the way to do it: which library do you recommend?
- If layout-based-plotting is the way to do it: how can i make use of the distances/coordinates in these libraries? And which library do you recommend?
Thanks for all your input!
Sascha
EDIT: I completed a prototype implementation using the PLplot library (http://plplot.sourceforge.net/). The results are nice and should be enough for the moment. I discovered and chosed this library because a related project (VRPH Software Package / Groer) used this plot and the source code was distributed. So the implementation was done in a short amount of time. The API is in my opinion bit awkward and low-level. Maybe there are some more modern (maybe not a c-based library) libraries out there? MathGL? Dislin? Maybe i will try them too.
The nice thing about drawing multiple tours in a vehicle routing problem is that "not so bad" algorithms tend to discover nice non-overlapping and divergent tours which is really good for the eye ;-)
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
目前还不太清楚您要存档的内容,但如果我正确理解您的问题,那么您可以使用 OpenGL 来完成。有了顶点坐标,这应该相当容易。
It is not quite clear what you are trying to archive, but if I understand your question correctly, then you could do it using OpenGL. Having vertex coordinates, it should be fairly easy.
您可以将 Gnuplot 与包含解决方案的输入文本文件一起使用。
绘制点(顶点)然后绘制线(代理路径)比连接它们更方便。
为了使绘图脚本变得简单,您可以为每辆车创建一个单独的文件,如果数量
车辆的数量是已知的。
查看:
http://www.cleveralgorithms.com/nature-inspired/advanced/visualizing_algorithms.html
You can use Gnuplot with a input text file that contains your solution.
It is convenient to draw the points (vertex) then lines (agents paths) than link them.
To make the plot script easy, you can have a separate file for each vehicle, if the number
of vehicles is known.
check out:
http://www.cleveralgorithms.com/nature-inspired/advanced/visualizing_algorithms.html