Algoritmo para teste de hit em retângulos sem compensação

StackOverflow https://stackoverflow.com/questions/97762

  •  01-07-2019
  •  | 
  •  

Pergunta

Eu tenho uma coleção de retângulos não sobrepostos que cobrem um retângulo fechado. Qual é a melhor maneira de encontrar o retângulo que contém um clique do mouse?

A resposta óbvia é ter uma variedade de retângulos e pesquisá -los em sequência, fazendo a pesquisa o (n). Existe alguma maneira de ordená -los por posição para que o algoritmo seja menor que o (n), digamos, O (log n) ou O (sqrt (n))?

Foi útil?

Solução

Você pode organizar seus retângulos em um quadrilátero ou kd-árvore. Isso lhe dá O (log n). Esse é o método mainstream.

Outra estrutura de dados interessante para esse problema são as árvores R. Isso pode ser muito eficiente se você precisar lidar com muitos retângulos.

http://en.wikipedia.org/wiki/r-tree

E depois há o método O (1) de simplesmente gerar um bitmap no mesmo tamanho da tela, preencha-o com um suporte para "sem retângulo" e desenhe os índices de hit-sectange para esse bitmap. Uma pesquisa se torna tão simples como:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

Obviamente, esse método só funciona bem se seus retângulos não mudarem com frequência e se você puder poupar a memória do bitmap.

Outras dicas

Crie uma árvore de intervalo. Consulte a árvore do intervalo. Consulte 'Algoritmos' da MIT Press.

Uma árvore de intervalo é melhor implementada como uma árvore vermelha-preta.

Lembre -se de que é aconselhável classificar seus retângulos se você estiver clicando mais com eles do que está mudando suas posições, geralmente.

Você terá que ter em mente que construir seus índices para criar seus diferentes eixos separadamente. Por exemplo, você deve ver se você se sobrepõe a um intervalo em X e em Y. Uma otimização óbvia é apenas verificar se há sobreposição no intervalo X e, em seguida, verifique imediatamente a sobreposição em Y.

Além disso, a maioria das árvores de intervalo de estoque ou 'livro' apenas verifica um único intervalo e retorna apenas um único intervalo (mas você disse que "não sobrecarregar" não é?)?)

Empurrá -los em um Quadtree.

Use um BSP Árvore para armazenar os retângulos.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top