0

我有一个数据库，其中包含英国每条道路的所有航点。

我正在尝试构建一个导航应用程序，给定用户的纬度和经度，它将从数据库中计算最近的道路并显示名称

数据库的 JSON 表示片段

[
{
    "NAME": "Trinity Road",
    "coordinates": [
        [
            1.7595267,
            52.4778475
        ],
        [
            1.7587864,
            52.4774
        ]
    ]
},
{
    "NAME": "Wilde Street",
    "coordinates": [
        [
            1.7593497,
            52.4795499
        ],
        [
            1.7594677,
            52.4795041
        ],
        [
            1.7598164,
            52.4793277
        ]
    ]
}
]

我遇到的问题是正确找到最近的道路。我找不到任何合适的算法，给定一个点会找到最近的路径/线

它不能简单地比较坐标，因为最近的道路可能在 2 个路点之间（排除“最近点对问题”）。

有人可以建议一个合适的算法吗？

我能想到的最佳解决方案是加权网格/矩阵，其中道路的权重取决于它们与用户的接近程度，然后选择用户周围价值最高的道路（但这可能很昂贵）。

我想在不使用诸如 google-maps 之类的 web api 或 PostGIS（必须使用 sqlite - 移动应用程序）的情况下解决这个问题

4

2 回答 2

3

您可以使用 r-tree 或四叉树来限制搜索空间，然后使用 voronoi 图来查找最近的道路。然后，您可以使用 2 个或更多道路点来输入 voronoi 图，然后在图中搜索包含该位置的 voronoi 单元格。也许您可以尝试加权 voronoi 图。你可以下载我的 php 类 additivley 加权 voronoi 图@https ://awvd.codeplex.com/。

于 2013-09-13T20:00:13.447 回答
0

使用四叉树是限制搜索空间的正确方法。对四叉树进行参数化，使其每个四叉节点的行数不超过 100 条。

您不需要（复杂的）voronoi 图。

在四叉树中搜索后，结果将是与四叉节点重叠的行列表。

现在使用 distanceToLineSegment(Point, point0, point1); （在互联网上搜索该名称）

走最短距离。

您必须在调用 distanceToLineSegment 之前动态转换点，以便它们位于笛卡尔空间中。使用四边形节点的中心作为变换中心。

于 2014-07-25T08:31:17.003 回答