Si el universo es número entero, o si el nivel de precisión es bien conocida y no es demasiado alto, puede utilizar abelsson 's sugerencia de la hilo, utilizando O (1) las operaciones de búsqueda utilizando colorante:
Primero, el problema micro. Tiene un rectángulo rotado arbitrariamente y un punto . ¿Está el punto dentro del rectángulo ?
Hay muchas formas de hacerlo. Pero lo mejor, creo, es el uso del producto 2d vector cruzado. Primero, asegúrese de que los puntos del rectángulo estén almacenados en el sentido de las agujas del reloj. A continuación, haga el vector producto cruzado con 1) el vector formado por los dos puntos del lado y 2) un vector desde el primer punto del lado hasta el punto de prueba. Compruebe el signo del resultado - positivo es dentro (a la derecha de) el lado, negativo está afuera. Si está dentro de los en los cuatro lados, está dentro del rectángulo . O, de forma equivalente, si es fuera de cualquiera de los lados, está fuera del rectángulo . More explanation here.
Este método se llevará a 3 resta por vector * veces 2 vectores por lado, más un producto cruzado por cada lado que es tres multiplica y dos añade.11 fracasos por lado, 44 fracasos por rectángulo.
Si no te gusta el producto vectorial, entonces se podría hacer algo como: averiguar la inscripción y círculos circunscritos de cada rectángulo, comprobar si el punto dentro de la inscrita uno. Si es así, también está en el rectángulo . De lo contrario, verifique si está fuera del rectángulo circunscrito. Si es así, está fuera del rectángulo también. Si cae entre los dos círculos, está f **** d y usted tiene que comprobarlo de la manera difícil.
Encontrar si un punto está dentro de un círculo en 2d toma dos sustracciones y dos squarings (= multiplica), y luego se comparar la distancia al cuadrado para evitar tener que hacer una raíz cuadrada. Eso es 4 fracasos, multiplicado por dos círculos es de 8 fracasos - pero a veces todavía no lo sabrá. También esto supone que usted no paga tiempo de CPU para calcular los círculos circunscritos o inscritos, que puede o no puede ser cierto dependiendo de la cantidad de pre-cálculo que está dispuesto a hacer en su conjunto rectángulo .
En cualquier caso, probablemente no es una gran idea para probar el punto en contra cada rectángulo, sobre todo si se tiene cien millones de ellos.
Lo que nos lleva al problema macro. ¿Cómo evitar probar el punto en contra de en cada rectángulo del conjunto? En 2D, este es probablemente un problema quad-tree . En 3D, lo que generic_handle dijo: un octárbol. De la parte superior de mi cabeza , probablemente lo implementaría como a B+ tree. Es tentador usar d = 5, para que cada nodo pueda tener hasta 4 niños, ya que se asigna tan bien a la abstracción del árbol cuádruple. Pero si el conjunto de rectángulos es demasiado grande para ajuste en la memoria principal (no muy probable estos días), entonces tienen nodos del mismo tamaño como bloques de disco es probablemente el camino a seguir.
Cuidado con degenerada molesto casos, como un conjunto de datos que tiene diez mil rectángulos casi idénticos con centros en el mismo punto exacto. : P
¿Por qué es importante este problema? Es útil en gráficos de computadora, para verificar si un rayo se cruza con un polígono. Es decir, ¿Acaso ese rifle de francotirador disparó solo golpeó a la persona a la que estaba disparando ? También se usa en el software de mapas en tiempo real, como unidades de GPS. El GPS le indica las coordenadas en que se encuentra, , pero el software de mapas tiene que encontrar dónde ese punto está en una gran cantidad de datos de mapa , y hacerlo varias veces por segundos.
¿Están los lados de sus rectángulos alineados con los ejes, o están orientados en ángulos arbitrarios a los ejes? –
Están todos alineados, sin rotación ni nada de fantasía como ese – pafcu
¿se superponen los rectángulos en absoluto? –