快速的知名度图求解？ [英] Fast visibility graph solver?

问题描述

我想在编程世界海洋探路者。我已经使用了A *算法对含土地和水的细胞的细胞网状previously。但我认为，一个更好的解决方案将是有大陆和岛屿和多边形;在两者之间（只有一次），计算的知名度网的空间;那么包括始发地和目的地的知名度图。那么解决的结果图A *。环顾四周，我发现了一本书，叫做计算几何描述的算法来计算的知名度图。然而，试图在C ++中实现它之前 - 这听上去是个好主意。

I am trying to program a pathfinder on the worlds oceans. I have used an A* algorithm on a cell mesh containing land and water cells previously. But I think that a better solution will be to have continents and islands and polygons; calculate a visibility mesh for the space in between (just once); then include origin and destination in the visibility graph; then solve A* on the resulting graph. Looking around, I have found a book called computational geometry that describes an algorithm for computing the visibility graph. However, before trying to implement it in C++ - does that sound like a good idea?

据我所知，已经提出了很多不同的算法来计算的知名度图形，具有不同数值的复杂性。它还在我看来，这是一个活跃的领域，不是一个已经解决为好。所以这对我来说似乎是一个真正的问题。如果您认为否则，请让我知道为什么！

As far as I know, a lot of different algorithms have been proposed for computing visibility graphs, with differing numerical complexity. It also seems to me that this is an active field, not something that's been solved for good. So this seems to me to be a genuine question. If you think otherwise, please let me know why!

编辑： 我现在已经实现了一种算法，首先计算能见度曲线图中，在世界地图上，包括多边形的，具有约5,000的顶点。在第二个步骤中，A *运行在能见度曲线图。 有可能是一个限制，在运行时间和存储器，以怎样的详细地图可以是表示。目前，能见度图形大约需要10分钟来计算我的笔记本电脑（我认为该算法是非常有效的，但我也相信我的code是不是很有效，并且可以显著加快）。一旦能见度图形进行计算，在A *是非常快的。 再次感谢您的答案和意见给予！

I have now implemented an algorithm that first computes the visibility graph, on a world map comprising of polygons, with about 5,000 vertices. In a second step, A* runs on the visibility graph. There is probably a limit, in terms of running time and memory, to how detailed the map can be. Currently, the visibility graph takes about 10 minutes to compute on my laptop (I believe that the algorithm is quite efficient; but I also believe that my code is not very efficient and could be speeded up significantly). Once the visibility graph is calculated, the A* is very quick. Many thanks again for the answers and comments given!

推荐答案

计划是一个很好的方式，以提高道路和运动规划算法的性能。但是，处理计算几何的很多算法都充满着挑战（尤其是当你不能犯错误），这是通常最好依赖于该领域的专家制定可靠的计算几何库。

Planning on a graph rather than a cell decomposition is a fantastic way to improve the performance of path and motion planning algorithms. However, many algorithms that deal with computational geometry are fraught with challenges (particularly when you can't afford to make mistakes), and it's often best to rely on reliable computational geometry libraries developed by experts in the field.

而不是过于复杂的解决方案，它可能是值得萎靡不振，许多在过去15年的研究路径规划一直专注于概率运动规划技术。这些技术在两个最著名的例子是快速-探索随机树（RRTS）和概率路线图（的PRM）。这些算法很容易实现，也有大量的例子可用，并且几乎不需要在几何深入了解上手。

Rather than overcomplicating your solution, it's probably worth flagging that much of the research in path planning over the last 15 years has been focused on Probabilistic Motion Planning techniques. The two best known examples of these techniques are Rapidly-exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRMs). These algorithms are easy to implement, there are plenty of examples available, and require little in depth knowledge of geometry to get started.

• 第五章 - 采样算法从规划算法通过拉瓦列涵盖了大部分的东西你需要知道要开始使用概率运动规划
• 第六章 - 来自同一组合算法越过最经典的知名度等分解，并pfaced与警告的警告$ P $：有些方法是不切实际要小心，不要学习本章的算法时做出了错误的假设，他们几个是外汇基金fi古老而易于实现，但。很多人可能会既不是的

• Chapter 5 - Sampling Algorithms from "Planning Algorithms" by LaValle covers most of what you'll need to know to get started with Probabilistic Motion Planning
• Chapter 6 - Combinatorial Algorithms from the same goes over most of the classic visibility like decompositions, and is prefaced with the warning "Warning: Some methods are impractical. Be careful not to make the wrong assumptions when studying the algorithms of this chapter. A few of them are efficient and easy to implement, but many might be neither"

这篇关于快速的知名度图求解？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！