Melhor maneira de conjunto de dados que contém otimizar cadeias de linha. Algumas linhas de início e fim no mesmas coordenadas

Question

A CONFIGURAÇÃO
Eu tenho uma tabela que contém cadeias de linha. Cadeias de linhas são compostas de vários pontos geográficos. Cada ponto é composta de uma latitude e longitude. Nota:. O valor cadeia de linhas é armazenado como texto no banco de dados

Assim, uma linha na tabela pode ter esta aparência:
id: um inteiro
linestring: x1, y2, x2, y2, x3, y3, x4, y4

O PROBLEMA
O Google Maps permite apenas até 1000 elementos a serem exibidos de cada vez. No meu caso, estou exibindo 850 linestrings e precisará adicionar muitos mais no futuro.

A PERGUNTA
Muito poucos dos linestrings conectar com uma ou mais outras cadeias de linha, o que significa que eles começam e / ou terminar nas mesmas coordenadas. O que eu olhar a fazer é encontrar a melhor maneira de otimizar o conjunto de dados de modo linestrings que ligam nas extremidades são mescladas na tabela DB. Isto irá reduzir a contagem total elemento quando eu analisar a tabela de banco de dados e criar o arquivo de exibição de mapas do Google.

Exemplo
Neste exemplo, imaginar, o alfa (A, B, C) os valores representam pontos geográficas. A tabela unoptimized pode ter esta aparência:

Antes de otimização:
linestring id
1 A, B, C
2 C, D
3 B, A
4 F, G, H
5 G, I
6 H, J

---

Depois de otimização:
1 A, B, C, D
2 F, G, H, J
3 G, I

---

Então, qual é a melhor maneira de otimizar os dados? Existe um algoritmo especial que funciona melhor? Eu tenho algumas idéias para soluções que vou formular e adicionar, mas eles parecem detalhado e convulado.

Eu não sou um grande CS para desculpar a terminologia desleixado e deixe-me saber se é necessária uma clarificação em qualquer lugar. Obrigado!

---

FYI .. Eu estou usando um banco de dados MySQL. Eu não estou usando as extensões espaciais. Se você tiver uma solução embaraçosamente simples que usa as extensões espaciais que eu gostaria de ouvir sobre isso de qualquer maneira.

Answer 1

Uma coisa a perceber é que, se houver mais do que uma cadeia de linhas que pode ser conectado a uma determinada cadeia de linha, ele não importa qual é escolhido - o número final de linestrings no mesa otimizado será o mesmo.

Então, nesse caso, uma estratégia gulosa simples de encontrar repetidamente um par de cadeias de linha que podem ser unidos e juntando-os até que você já não pode encontrar tal um par lhe dará uma mesa ideal. Essencialmente, o pseudocódigo é:

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

Isto não pode ser feito em uma única consulta SQL por causa da possibilidade de que o x . y cadeia de linhas resultante será usado novamente. Você deve ser capaz de escrever o loop while usando uma linguagem processual como T-SQL, ou uma linguagem de script (por exemplo, Perl, utilizando DBI para acessar banco de dados), e usando uma consulta SQL SELECT para encontrar um par ou uma lista de pares e em seguida, o processamento de cada usando instruções DELETE e INSERT.

Gostaria de sugerir a adição de dois campos para a sua mesa, begin e end, e indexá-las para acelerar a pesquisa.

Answer 2

Eu acho que a maneira mais fácil de ir aqui é usar as extensões espaciais do MySQL.

Particularmente eu ter utilizado o Oracle extensões espaciais. No Oracle, podemos usar funções como SDO_GEOM.RELATE ou SDO_RELATE para descobrir a relação espacial entre duas objetos (contém, toques, cruza, etc.)

Estou certo de que é uma função espacial equivalente no MySQL

EDIT:

Aqui é um ligação que lista todos os espacial MySQL disponíveis funções.

Answer 3

Haverá uma solução única se cada endpoint aparece no máximo duas vezes (que termina uma cadeia de linha e começando outro), mas isso é garantido? Por exemplo. o que acontece se você tem:

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

Se este produto:

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

ou

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

?

Ou você não se importa?