Algoritmo para encontrar segmentos sobreposição de linha

Question

n4------------------n3--------------------n2--n1
|                    |                    |    |
|                    |                    | P1 |
|                    |                    |    |
|                    |                    n6--n5
|                    |                    |
|              n11--n10                   |
n17      P4     |    |         P2         |
|               | P3 |                    n7
|              n12---n9                   |
|               |                         n8
|               |                         |
n16------------n15---------n14------------n13

Na arte ASCII acima, existem quatro polígonos (P1, P2, P3, P4) com exactamente sobrepostos segmentos de linha. Por exemplo, P2 polígono (formado por segmentos de linha entre os nós n3, 10, 9, 12, 15, 14, 13, 8, 7, 6, e 2) e P1 (n1, 2, 5, e 6) se sobrepõem no segmento de linha entre N2 e N6.

O que é a maneira mais rápida de encontrar segmentos de linha que se sobrepõem exatamente?

Answer 1

Se cada forma é uma lista de bordas, em seguida:

initialize map<edge, list of shapes> map
for each Shape s
  for each Edge e in s
    list l = map.get(e)
    if(l == null) 
      l = new list()
    l.add(s)
    map.put(e, l)

for each <edge, list> in map.entries
  if(list.size > 1)
    do something with this common edge

seu O (bordas), e não o seu curso para fazer melhor do que isso. esta solução pode não ser satisfatória dependendo do que você quer fazer especificamente embora.

Answer 2

Dado segmentos de linha N, no pior caso, não pode ser O (n ^ 2) intersecções. Basta pensar no caso em que você tem N polígonos onde cada polígono ações da mesma geração. A menos que haja uma restrição adicionado para evitar esta situação aconteça (que você omitido para adicionar), então o melhor algoritmo que você pode vir até com será O (n ^ 2), no pior caso, uma vez que simplesmente listar as interseções é O (N ^ 2).

Na prática, os algoritmos mais eficientes em geometria computacional para encontrar interseções de segmentos de linha são de varredura algoritmos de linha. Seu pior caso de tempo para encontrar todos os cruzamentos de execução é O (log n k), onde k é o número de interesections (isso pode ser N ^ 2, no entanto, raramente é.)

Você pode encontrar uma descrição de exatamente o algoritmo que você precisa em Introdução aos algoritmos por Thomas H Cormen na seção sobre geometria computacional.

Answer 3

O algoritmo do twolfe18 parece ser bom. Pode haver uma complicação adicionada, no entanto, se as arestas correspondentes não estão identicamente descrito. No seu exemplo, P1 e P2 ambos compartilham a borda n2-n6. Mas borda da P2 pode ser descrito pelo segmento n2-N7 vez (se n2-n6 e N6-N7 são colineares). Em seguida, você precisa de um método de hash mais complicado para determinar se duas bordas se sobrepõem. Você pode dizer se duas bordas se sobrepõem por segmentos de mapeamento em linhas, olhando para a linha em uma tabela hash, então testar se dois segmentos em uma linha de interseção usando uma árvore de intervalo no espaço de parâmetros na linha.