如何存储地点之间的距离？

Question

如何存储地点之间的距离？

5

我有一个包含地点信息的数据库，需要在我的网页中显示任意两个地点之间的距离。将这些距离存储起来可以节省大量工作量（加载它们应该比重新计算它们更容易）。但是如何保存距离的平方矩阵呢？每次插入新行时创建一个新列似乎不是一个好的解决方案，但我没有找到更好的解决方案（尽管我可以考虑一些变通方法，例如计算某些10或20个最近的距离，并假设我很少需要更多）。

在PHP/MySQL中，保存可变（且增长）大小的平方表的最佳方法是什么？还是没有好的解决方案，我的（或其他人的）变通方法更好吗？

- Pavel V.

6个回答

3

我会为所有地点存储纬度/经度，并编写一个函数来利用该信息计算它们之间的距离。这样，您无需为想要添加到数据库中的新地点计算距离。

此外，如果您有很多地点，使用透视表仅存储距离，您必须注意此表可能会增长得非常快。因为您需要覆盖所有地点的组合。

例如：对于1000个地点，您将在表中拥有1000 * 1000-1000 = 999000行。对于更大的数字，请进行数学计算，但是此表可能包含许多行，具体取决于您拥有多少地点。

- TheEwook

1

@Pavel 我有一个已经建立并在生产中运行的网站，它就像这样做。以下是它更快的最佳原因。假设你有100个地点，然后再添加一个。现在你需要计算101个距离并将它们插入到表中... 现在如果你有1,000个地点或者10,000个地点。相比每次计算距离所需的半秒钟，新地点的插入将需要越来越长的时间，而且需要花费5分钟来计算10,000个距离。你必须考虑长远的利益而不仅仅是眼前的利益。 - amaster

@Pavel 如果您使用经纬度，则可以轻松地在要搜索附近的位置周围绘制一个框，并计算该子查询的距离，仅返回圆形内的距离（在给定半径/距离内）。我在某个地方找到了一篇很棒的文章和教程，如果我能再次找到它，我会发布它。这样，您不需要计算所有地点的确切距离，只需要计算那些在该象限中的地点的距离即可。 - amaster

1

@Pavel Ah 我在搜索我的 Chrome 历史记录时找到了它 :) 在一个边界圆内选择点 - amaster

@Pavel，是的，这完全取决于应用程序的需求。在我的情况下有效的方法可能不适合你的情况。我理解这一点。感谢您考虑并选择最适合您情况的方法，同时也意识到这不是一个万能的解决方案。 - amaster

性能测试（使用非常简单的距离计算算法，仅涉及13个地点和它们之间的所有距离；从数据库中计算/加载一个地点到其他所有地点的距离）表明每次重新计算距离比从数据库加载距离要快得多。我很高兴我知道约翰内斯的算法，并希望它们在以后的某些情况下会更好，但现在我停止编写加载距离的函数。 - Pavel V.

显示剩余3条评论

3

将其拆分为另一个名为“distance”的表，与原始的“place”表相关联：

创建表距离（place_id_1 int，place_id_2 int，distance int）;

也就是说，对于每个地点，计算与另一个地点的距离，并将其保存在这个新表中。

- kbuilds

2

你可以创建一个新表，其中包含两列作为位置的外键以及一列用于它们之间距离的数据。

 |place1 | place2 | distance
-+-------|--------|---------
 |....   |.....   | .....

根据您拥有的位置数量，这个表格可能会非常快速地增长。

- Rikan

0

最简单的方法是创建另一个表，其中包含两个地点ID和距离，例如：

place1    place2    distance
a         b          20
c         d          30

在获取数据的时候，只需将其与位置表连接即可。

- ABorty

-1

我认为这样的东西可以完成工作。

         ORIGIN     | CITY 1 | CITY 2 | CITY 3 | CITY 4 | CITY 5
         +++++++++++++++++++++++++++++++++++++++++++++++++++++++
         CITY 1        0        20                 40      20
         CITY 5        10       50       20                0
         CITY 3        10                0         10      40

你可以轻松地获取到其他地方的距离，而且你不需要为每个已知距离存储城市名称。

SELECT 'CITY 2' FROM DISTANCES WHERE ORIGIN='CITY 5'

- Ruben Serrate

使用数据透视表更高效且易于维护。例如，使用此设置无法确保唯一索引，而使用数据透视表可以实现。 - Johannes

你会在那个表中添加新列，然后随着新城市的注册更新所有现有行以添加其距离的新值吗？那将是可怕的。 - Pedro Cordeiro

透视表基本上只用于存储另一个表中的条目数据。因此，它不需要自己的主键，而是使用其他表的键。在这里查看如何使用透视表的示例。 - Johannes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Johannes · Accepted Answer

编辑说明：如评论中所提到的，一旦您拥有足够多的地点，将长/纬度值存储起来并基于它们实时计算距离可能更有意义。然而，本文中解决方案仍可能适用于其他应用程序。

处理这个问题的最佳方式是使用数据透视表，每行都有两个位置ID和一个距离值。

现在，由于A-B的距离与B-A的距离相同，我们只需要存储每个配对一次。我们可以通过仅在A的ID小于B时存储距离来实现此目的。

设置

首先需要一个places表来存储你的地点

id | name
---+---------
 1 | Place_A
 2 | Place_B
 3 | Place_C
 4 | Place_D

然后是一个places_distances透视表：

place_id_1 | place_id_2 | distance
-----------+------------+----------
         1 |          2 | 10.0
         1 |          3 | 20.0
         1 |          4 | 15.0
         2 |          3 | 12.0
         2 |          4 |  8.0
         3 |          4 | 14.0

请注意，数据透视表不需要自己的ID字段（尽管有些人可能会认为有时仍然很有用）。您将按以下方式设置唯一键（您需要查阅文档以获取正确的用法）：

UNIQUE KEY `UNIQUE_placesDistances_primary`(`place_id_1`,`place_id_2`)

这可以确保表中没有相同的位置/地点配对。

您还需要设置外键：

CONSTRAINT FOREIGN KEY `FK_placesDistances_place1` (`place_id_1`) 
    REFERENCES `places`(`id`),
CONSTRAINT FOREIGN KEY `FK_placesDistances_place2` (`place_id_2`)
    REFERENCES `places`(`id`)

这将确保您只能为实际在places中定义的地点添加条目。这也意味着（如果您使用默认的外键行为），如果您有距离行引用该地点，则无法删除该地点。

使用示例

查找两个地点之间的距离

(假设有两个变量 @id_1 表示第一个地点的ID，@id_2 表示第二个地点的ID)

SELECT `distance`
FROM `places_distances`
WHERE (`place_id_1` = @id_1 AND `place_id_2` = @id_2)
    OR (`place_id_2` = @id_1 AND `place_id_11` = @id_2)
LIMIT 1;

我们使用OR来处理查找距离2到1而不是1到2的情况 - 请记住，我们仅存储第一个位置id小于第二个位置id的值，以避免存储重复值。

插入新的距离

(给定三个变量，@id_1 为第一个地点的 id，@id_2 为第二个地点的 id，@distance 为距离)

INSERT `places_distances`(`place_id_1`,`place_id_2`,`distance`)
    VALUES(LEAST(@id_1, @id_2),GREATEST(@id_1, @id_2), @distance)

我们正在使用内置的比较函数LEAST和GREATEST来帮助维护我们的规则，即仅存储第一个ID小于第二个ID的位置，以避免重复。

展示一个地名列表，按照距离由远及近排序。

为了让原始的地名从“places”表中显示在我们的“places_distances”查询中，我们需要将它们连接在一起。在这种情况下，“LEFT JOIN”是最好的选择，因为我们只关心“places_distances”表中的内容。有关MySQL连接更多信息，请查看此处。

SELECT 
    `p_1`.`name` AS `place_1`,
    `p_2`.`name` AS `place_2`,
    `distance`
FROM `places_distances`
LEFT JOIN `places` AS `p_1`
    ON `distances`.`place_id_1` = `p_1`.`id`
LEFT JOIN `places` AS `p_2`
    ON `distances`.`place_id_2` = `p_2`.`id`
ORDER BY `distance` DESC

应该返回这样的表格：

place_id_1 | place_id_2 | distance
-----------+------------+----------
   Place_A |    Place_C | 20.0
   Place_A |    Place_D | 15.0
   Place_C |    Place_D | 14.0
   Place_B |    Place_C | 12.0
   Place_A |    Place_B | 10.0
   Place_B |    Place_D |  8.0

展示一个地点表格，其中包含它们与特定给定地点的距离。

这有点棘手，因为我们需要在不是输入地点的行中显示名称，但我们可以使用另一个有用的函数IF(CONDITION,'TRUE_OUTPUT','FALSE_OUTPUT')来实现。

（@place_name是包含地点名称的变量，在本例中为'Place_B'）

SELECT 
    IF(`p_1`.`name`=@place_name, `p_2`.`name`, `p_1`.`name`) AS `name`,
    `distance`
FROM `places_distances`
LEFT JOIN `places` AS `p_1`
    ON `distances`.`place_id_1` = `p_1`.`id`
LEFT JOIN `places` AS `p_2`
    ON `distances`.`place_id_2` = `p_2`.`id`
WHERE `p_1`.`name` = @place_name OR `p_2`.`name` = @place_name
ORDER BY `distance` DESC

应该返回这样的表格：

   name | distance
--------+-----------
Place_C | 12.0
Place_A | 10.0
Place_D |  8.0