2

设置
我有一个包含线串的表。线串由多个地理点组成。每个点都由纬度和经度组成。注意：线串值在数据库中存储为 TEXT。

所以表中的一行可能如下所示：
id: an integer
linestring: x1, y2, x2, y2, x3, y3, x4, y4

问题
Google 地图一次最多只能显示 1000 个元素。就我而言，我正在显示 850 个线串，并且将来需要添加更多。

问题
相当多的线串与一个或多个其他线串连接，这意味着它们开始和/或结束于相同的坐标。我要做的是找到优化数据集的最佳方法，以便将末端连接的线串合并到数据库表中。当我解析数据库表并为谷歌地图创建显示文件时，这将减少总元素数。

示例
在此示例中，假设 alpha (A,B,C) 值表示地理点。未优化的表可能如下所示：

优化前：
id linestring
1 A, B, C
2 C, D
3 B, A
4 F, G, H
5 G, I
6 H, J

优化后：
1 A、B、C、D
2 F、G、H、J
3 G、I

那么优化数据的最佳方法是什么？有没有一种效果最好的特定算法？我有一些我将制定和添加的解决方案的想法，但它们看起来很冗长和令人费解。

我不是 CS 专业的，所以请原谅草率的术语，让我知道是否需要在任何地方进行澄清。谢谢！

仅供参考..我正在使用 MySQL 数据库。我没有使用空间扩展。如果您有一个使用空间扩展的令人尴尬的简单解决方案，无论如何我很想听听。

4

3 回答 3

1

我认为最简单的方法是使用 MySQL 空间扩展。

特别是我只使用了 Oracle 空间扩展。在 Oracle 中，我们可以使用SDO_GEOM.RELATE或SDO_RELATE等函数来找出两个对象之间的空间关系（包含、接触、相交等）

我确信在 MySQL 中有一个等效的空间函数

编辑：

这是一个列出所有可用 MySQL 空间函数的链接。

于 2009-01-20T19:35:56.563 回答
1

需要意识到的一件事是，如果有多个线串可以连接到给定的线串，则选择哪个并不重要——优化表中的线串的最终数量将是相同的。

因此，在这种情况下，一个简单的贪心策略会反复寻找一对可以连接的线串并将它们连接起来，直到你再也找不到这样的一对，这将为你提供一个最佳表格。本质上，伪代码是：

while (there exists a pair of linestrings x and y that share an endpoint) {
    delete(x)
    delete(y)
    insert(x . y)
}

这不能在单个 SQL 查询中完成，因为可能x . y会再次使用生成的线串。您应该能够使用诸如 T-SQL 之类的过程语言或脚本语言（例如 Perl，使用 DBI 进行数据库访问）编写 while 循环，并使用 SQL SELECT 查询来查找一对或一对列表以及然后使用 DELETE 和 INSERT 语句处理每个。

我建议将两个字段添加到您的表中，begin并end为它们编制索引以加快搜索速度。

于 2009-01-21T18:07:33.777 回答
0

如果每个端点最多出现两次（结束一个线串并开始另一个线串），那么将有一个独特的解决方案，但可以保证吗？例如，如果您有以下情况会发生什么：

  1. 甲、乙、丙
  2. 丙、丁
  3. C、E、F

这应该产生：

  1. A B C D
  2. C、E、F

或者：

  1. A、B、C、E、F
  2. 丙、丁

?

还是你不在乎？

于 2009-01-21T13:29:02.777 回答