Cómo calcular la distancia entre dos polígonos no convexos en tiempo lineal

[editar] Nuevamente reformulo mi respuesta, cualquier comentario es bienvenido.

A continuación, supongo que está hablando sobre polígonos en un espacio 2D sin agujero y auto intersección. Todos los comentarios sobre este algoritmo son bienvenidos. Mi referencia para la complejidad del tiempo y las estructuras de datos proviene de la Biblioteca de Algoritmos de Geometría Computacional.

Llamamos a P y Q los dos polígonos con vértices n y m respectivamente.

La idea principal es que es suficiente encontrar el borde más cercano a cada vértice para calcular la distancia mínima entre P y Q. Esto significa iterar sobre todos los vértices y encontrar un vecino más cercano, por lo que puede esperar una complejidad en O ((m + n) * log (m * n)).

Paso 1: la distancia mínima implica al menos un vértice

Primero, te muestro que es suficiente encontrar el borde más cercano a cada vértice. Afirmo que si P y Q no se intersectan, la distancia mínima es una distancia que involucra al menos un vértice de uno de los polígonos. Tome dos bordes de P y Q, y tome un par de puntos más cercanos en esos bordes:

  • si los bordes son paralelos, puede deslizarse a lo largo de los bordes para que uno de los puntos sea un vértice de uno de los polígonos;
  • si no, es obvio que uno de los puntos es un vértice de uno de los polígonos.

Paso 2: calcula la triangulación de un polígono

Para ubicar los vértices de Q dentro de P, calculamos una triangulación de P tal que los bordes de P son bordes de la triangulación. Tal triangulación se conoce en la biblioteca CGAL como una triangulación restringida (ver Triangulación 2D: Manual del usuario). Primero, se construye una triangulación de Delaunay a partir de los vértices, luego se insertan los bordes de P uno por uno eliminando los triángulos de la triangulación. La construcción de tal triangulación tiene una complejidad sensible a la salida: restringir un borde del polígono tiene un costo proporcional al número de triángulos a eliminar.

Una vez que se construye la triangulación, la estructura de datos CGAL ofrece buenas características para iterar y consultar la triangulación. En particular, la comprobación de si un borde de la triangulación está restringido, es decir, pertenece a P, se realiza en tiempo constante, y la localización de un punto q en la triangulación se realiza en tiempo logarítmico. También hay un vértice especial llamado vértice “infinito” que permite encontrar fácilmente el casco convexo de los vértices de la triangulación. Para nosotros, será útil determinar si un punto localizado q está dentro o fuera de P.

Paso 3: etiquetar triángulos de la triangulación como interior o exterior

Este paso es necesario para saber si un punto localizado está dentro o fuera de P. Tenga en cuenta que hay dos casos en los que un triángulo de triangulación de P puede estar fuera de P:

  • P no es convexo:

  • un triángulo de la triangulación es “infinito”. Para localizar fácilmente un punto en una triangulación, la biblioteca CGAL introduce un vértice “infinito”. Todos los vértices finitos de la triangulación que están en el casco convexo comparten un borde con este vértice “infinito”. Esto crea triángulos “infinitos” hechos de un vértice “infinito” y dos vértices finitos en el casco convexo. Tal “triángulo infinito está necesariamente fuera de P.

Para ubicar los triángulos, primero encuentre un vértice de P que tenga un borde “infinito” (es decir, un borde con el vértice “infinito”). Esto se hace en O (n) ya que el número de bordes incidentes en un vértice está limitado. Desde este vértice, encuentre un triángulo “infinito”, anótelo como exterior.

Ahora, puede iterar sobre triángulos que comparten un borde común para que los triángulos tengan un borde de P, o dos vértices de P, y etiquetar estos triángulos como fuera de P. Esta operación debería estar en O (n) ya que los triángulos tienen solo tres triángulos vecinos y siempre tienen un vértice de P como vértice.

Paso 4: localizar y calcular distancias

Luego, para cada vértice q de Q, ubique q en la triangulación (hecho en O (m * log (n)). Localizar q en la triangulación significa encontrar el triángulo que contiene espacialmente el punto q. Hay dos posibilidades:

  • q no está en un triángulo fuera de P, puede detener el algoritmo: la distancia es 0 ya que P y Q se cruzan;
  • q está en un triángulo fuera de P: calcula la distancia entre q y cada borde y vértice del triángulo que pertenece a P, y almacena el mínimo.

Ahora, tiene la distancia mínima entre los vértices de Q y el polígono P. Puede calcular la triangulación de Q y hacer las mismas operaciones para encontrar el vértice más cercano de P al polígono Q. La distancia mínima será la mínima entre las dos distancias.

Análisis de complejidad.

El problema es con la triangulación restringida que hace que la salida de este algoritmo sea sensible: si las formas de los polígonos son “agradables”, lo que significa que se deben eliminar pocos triángulos al restringir la triangulación, entonces debe tener un algoritmo en O ((m + n) * log (m * n)).

Puede ser, es posible tener esta complejidad exacta usando una triangulación clásica, pero entonces, no estoy seguro de que la complejidad de la consulta sea logarítmica, ese es uno de los puntos clave del uso de la triangulación.

[Editar] ¡Gracias a Stephan Hugel que me ayudó a aclarar mi respuesta!