用neo4j找路/导航

我知道我可能会因为问这个问题而被骂，但我希望有人能帮助我指出正确的方向。用neo4j找路/导航

我正在尝试创建一个像Google地图一样的应用程序查找应用程序，但它会将路线标记为地图上的多个点。

我试图让一个动物运输的工具，允许多人在从A点的路径见面B.我想我念你可以用图形数据库做到这一点。

任何人都可以提供地图数据库，文章等资源来帮助我吗？我一直在试图谷歌的文章，但可以找到任何匹配，所以我认为我使用了错误的术语如“寻路”或“方向”

谢谢！

来源

2015-06-06 Wally Kolcz

你能澄清你的意思吗？在地图上标记多个点的路线？你稍后提到从A到B的路径，但这只有2点。 – cybersam

我想start with this article。要问一个更具体的问题，你需要一个数据模型和你想要做的一个例子。

但是一般来说，使用的语言可能是“最短路径”。一般来说，如果您试图找到从A点到B点的路径，那么您正在寻找“路径成本”最小的“最短路径”。有时候成本是距离，有时候成本是时间 - 但是无论哪种方式，你通常都在寻找最短路径，而不是任何路径。由FrobberOfBits提到

来源

2015-06-06 17:10:44 FrobberOfBits

根据运输链中的人数，它将成为2点和x点之间的最佳映射路线。根据他们愿意开车在每个点的中点开多远的距离，爱也能够做到每个人的半径 –

图形数据库可以很好地用于寻路，尤其是shortestPath。

只要您有可以形成路径的节点，就可以很好地工作。根据我在您的评论中了解的内容，事实上，您需要首先根据用户驾驶偏好动态构建这些节点。

此外，显然你目前没有A点到B点的数据模型？

这是我会怎样着手，简要：

用例是A点是我的家，点2是在那里生活的Neo4j的社区照顾者，在地图上这将是：

enter image description here

所有小白在从A到B的路由点可以是Neo4j的节点。

现在你说，对于例如，有一个真棒女孩50公里，以加盟路线的驾驶偏好，因此目前的路线必须改变。

enter image description here

在你的应用程序，你不强制用户选择一个中间点，你将不得不在飞行创建它。

所以我快速的解决方案，是让在半径，这将是最接近于初始路径的目标点的点。

要实现它，首先你需要从女孩的当前位置的初始方位到目的地（这里德累斯顿）

凡LAT1和lon1是女孩的位置，LAT2，lon2的德累斯顿的位置

然后，鉴于此初始方位，您可以计算从轴承bearing和50公里的距离中的女孩开始的位置，例如

在PHP它会是什么样子（测试）：

// Function that calculate new coordinates from point A 
// Given a bearing and a distance to point B 
function getAwayPosition($lat1, $lon1, $lat2, $lon2, $distance) 
{ 
    // Getting true course from point A to point B 
    $la1 = deg2rad($lat1); 
    $la2 = deg2rad($lat2); 
    $lo1 = deg2rad($lon1); 
    $lo2 = deg2rad($lon2); 

    $y = sin($la2-$la1)*cos($lo1); 
    $x = cos($lo1*sin($lo2))-sin($lo1)*cos($lo2)*cos($la2-$la1); 
    $course = fmod(rad2deg(atan2($y, $x)+360), 360); 

    // Getting the new lat/lon points from lat1/lon1 given the course and the distance 
    $bearing = deg2rad($course); //back to radians for the coordinates calculation 
    $laa = asin(sin($la1 * cos($distance/6371 + $la1 * cos($course)))); 
    $loo = $lo1 + atan2(sin($bearing) * sin($distance/6371) * cos($la1), cos($distance/6371) - sin($la1) * sin($laa)); 

    return array(
     'lat' => rad2deg($laa), 
     'lon' => rad2deg($loo), 
     'bearing' => $course 
    ); 
}

注：也有haversin功能Cypher支架计算地球的距离，我没有打那么多与它虽然

因此，您可以添加一个代表女孩所需位置的节点，以加入旅程。

到目前为止，我们现在已经3良好的节点为Neo4j的：

enter image description here

现在，我认为这将是最多可为过程的其余部分的数据模型，如果从A到B的路由不要在数据库中形成已有的Neo4j节点，您可以通过使用Google Maps API计算所有点的距离来动态构建它，并将其设置为关系属性。然后你可以做一个Cypher最短路径并减少关系距离属性。

如果您已经有节点代表从A到B的初始路线的多个中间点，则可以使用Neo4j Spatial并从女孩的所需位置到路线的中间节点获取最近点并创建一个关系与距离。再次shortestPath最佳映射路线。

第二个解决方案会更好，因为你会立刻有一个图表一起玩：

enter image description here

和简单的Cypher查询，如果你想用最少公里的路径：

MATCH (a:Point {id:'A'}), (b:Point {id:'B'}) 
MATCH p=allShortestPaths((a)-[:NEXT_POINT]-(b)) 
RETURN p, reduce(totalKm = 0, x in relationships(p)| totalKm + x.kilometers) as distance 
ORDER BY distance ASC

也有Djikstra算法与成本性能可与Neo4j的REST API http://neo4j.com/docs/stable/rest-api-graph-algos.html

个一些资源：

所以，作为一个结论，如果你想使用的Neo4j确定最佳路线，你需要帮助他在数据库中的一些数据;-)

来源

2015-06-07 11:51:04

哦，我的上帝，真棒！非常感谢你提供的所有信息 –

我用经过测试的PHP代码取代了JS代码 –

你看起来要描述的是从A到B经由不同的航点（人的位置）的路线，但是目标是从A到B的总距离被最小化。具有这些特征的图表中的路径称为Minimum Spanning Tree。最重要的是，人们可以通过旅行来实现“主要路线”的事实只是引入了额外的路标，它并没有改变整体问题，也没有改变它的传统解决方式。

Cypher和REST API都没有函数来计算最小生成树，不幸的是，简单地收集各个节点之间的最短路径（例如使用Dijkstra算法），然后尝试从这些最短路径段创建路径将不是最优的在一般情况下。

但是，通过服务器插件或Neo4j中的非托管扩展来实现Prim's algorithm并不困难，我建议您查看一下。

来源

2015-06-07 18:22:03 Vince

你在哪里找到了该国的地理数据库？ –

用neo4j找路/导航

回答

相关问题