Лучший способ оптимизировать набор данных, содержащий строки строк. Некоторые линии начинаются и заканчиваются в одинаковых координатах

Question

НАСТРОЙКА
У меня есть таблица, которая содержит строки. Линия состоит из нескольких географических точек. Каждая точка состоит из широты и долготы. Примечание: значение строки хранится в базе данных как TEXT.

Таким образом, одна строка в таблице может выглядеть следующим образом:
id: целое число
линейная строка: x1, y2, x2, y2, x3, y3, x4, y4

ПРОБЛЕМА
Карты Google позволяют отображать только до 1000 элементов одновременно. В моем случае я отображаю 850 строк и мне нужно будет добавить еще много в будущем.

ВОПРОС
Довольно многие из линий линий соединяются с одной или несколькими другими линиями линий, что означает, что они начинаются и / или заканчиваются в одинаковых координатах. Я хотел бы найти лучший способ оптимизировать набор данных, чтобы строки строк, соединяющиеся на концах, были объединены в таблице БД. Это уменьшит общее количество элементов при анализе таблицы БД и создании файла отображения для карт Google.

Пример * ** тысяча двадцать-один * тысяча двадцать два Представьте, что в этом примере значения альфа (A, B, C) представляют географические точки. Неоптимизированная таблица может выглядеть так:

до оптимизации:
id linestring
1 А, В, С
2 С, Д
3 B, A
4 F, G, H
5 г, я
6 H, J

---

После оптимизации:
1 A, B, C, D
2 F, G, H, J
3 г, я

---

Так каков наилучший способ оптимизации данных? Есть ли конкретный алгоритм, который работает лучше всего? У меня есть некоторые идеи для решений, которые я сформулирую и добавлю, но они кажутся многословными и запутанными.

Я не майор CS, поэтому извините за неаккуратную терминологию и дайте мне знать, если где-то нужны пояснения. Спасибо!

---

К вашему сведению ... Я использую БД MySQL. Я не использую пространственные расширения. Если у вас есть смущающее простое решение, использующее пространственные расширения, я бы все равно хотел услышать об этом.

Answer 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. Вы должны быть в состоянии написать цикл while, используя процедурный язык, такой как T-SQL, или язык сценариев (например, Perl, используя DBI для доступа к базе данных), и используя запрос SQL SELECT, чтобы найти пару или список пар и затем обрабатывает каждый с помощью операторов DELETE и INSERT.

Я бы предложил добавить в вашу таблицу два поля, begin и end, и проиндексировать их для ускорения поиска.

Answer 2

Я думаю, что самый простой способ - использовать пространственные расширения MySQL.

В частности, я использовал только пространственные расширения Oracle. В Oracle мы можем использовать такие функции, как SDO_GEOM.RELATE или SDO_RELATE , чтобы определить пространственные отношения между двумя объектами (содержит, касается, пересекается и т.

Я уверен, что в MySQL есть эквивалентная пространственная функция

EDIT:

Вот ссылка , в которой перечислены все доступные пространственные функции MySQL.

Answer 3

Будет уникальное решение, если каждая конечная точка появится не более двух раз (конец одной строки и начало другой), но гарантируется ли это? Например. что произойдет, если у вас есть:

1. А, В, С
2. С, Д
3. C, E, F

Если это даст:

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

или

1. A, B, C, E, F
2. С, Д

Или тебе все равно?