punto eficiente dentro de los límites del rectángulo de búsqueda

Question

Estoy trabajando en un editor de mapas vectoriales y tengo un conjunto de elementos, cada uno de los cuales especifica su cuadro delimitador dentro de la vista. A medida que el mouse se mueve, quiero resaltar el primer elemento cuyo cuadro delimitador contiene la ubicación actual del mouse. En este momento, utilizo una lista simple y la reviso, pero como es probable que aumente el número de elementos, la complejidad de O (n) del algoritmo de búsqueda actual será problemática para una aplicación interactiva.

lo que sería una mejor estructura de algoritmo/datos para esto?

Algunos restricciones adicionales/requisitos:

• El llenado de la estructura de datos de los cuadros delimitadores tendrían que ser relativamente rápida (ya que tengo que hacer que cada vez que el mapa se mueve o el zoom o cambios de proyección).
• El algoritmo tendría que ser capaz de encontrar todas de los elementos coincidentes (no sólo el primero). La razón es que algunos elementos del mapa pueden tener una forma irregular, por lo que la simple coincidencia del cuadro delimitador no es lo suficientemente estricta. Luego revisaría la lista de coincidencias y haría una coincidencia precisa.
• El fin en la que se han añadido las cajas para el conjunto necesita ser mantenido alguna manera - un elemento de mapa que se dibuja por encima de otro elemento debe tener una prioridad al momento de contrastar sus cuadros delimitadores.

Answer 1

Después de hojear libros, encontré una respuesta en el libro Computational Geometry (p.237). Este tipo de búsqueda a menudo se conoce como consulta de apuñalamiento y generalmente se implementa utilizando segment trees.

Complejidades:

• la consulta: O (log2N + k), donde k es el número de cuadros delimitadores reportados
• La estructura de datos utiliza S de almacenamiento (n * log n)
• El la estructura se puede construir en O (n * log n) tiempo

Answer 2

Si ordena sus elementos por una menor ubicación x, puede omitir todos los elementos antes de un cierto punto. Si tiene una segunda lista con la ubicación x superior, sabrá cuándo ha terminado.

Otra idea: Crear una cuadrícula tal vez dividir toda el área en 100x100 partes. Ahora encontrar una vez fuera, en el que partes de su red de una figura se superponen:

5 
4 
3 xx 
2 xxxx 
1 xx 
0 
0 1 2 3 4 5 

para esta figura que sería (1,1), (1,2) (2,2) (2,3) Un mapa de x * y Listas contendría ahora esta forma s para las 4 ubicaciones (1,1) -> s, (1,2) -> s, ...

Si tiene pocas veces inserciones/eliminaciones , pero a menudo comparaciones, esto aceleraría tus búsquedas. Solo visitaría las formas, asociadas a una determinada celda, e investigaría las coordenadas exactas de éstas.

Answer 3

tabla de búsqueda: los usuarios tienden a volver a las mismas áreas de la pantalla (lo que la tasa márgenes visita es por lo general baja, y la tasa de centro de visita es generalmente alta). para que podamos utilizar este conocimiento para mejorar nuestro rendimiento.
después de encontrar un punto una vez (podría ser cualquier otro método de búsqueda) puede almacenar en caché los resultados como una lista, y la próxima vez que el usuario visite el mismo lugar, la búsqueda sería O (1). por supuesto, tendrá que volcar el caché una vez que se haya agregado una nueva forma.

otra posibilidad es usar Observer Pattern, cada nueva forma se registrará en los puntos necesarios (esto podría ser costoso, dependiendo de cuánto inserto de forma es frecuente ...) y una vez que el mouse está en este punto, todo lo que tiene que hacer es llamar a quien se registró en este punto.

tercera posibilidad es por supuesto la tala de su área de búsqueda como @user desconocida sugirió.esta posibilidad se puede combinar con la tabla de búsqueda.