Área total de los cuboides proyectados sobre el plano

Question

Definamos n cuboides arbitrariamente escalados, rotados, situados y planos por vector de dirección normalizado.

Se supone que los cuboides se "aplanan" mediante proyección ortogonal sobre el plano, por lo que podemos tratarlos como figuras 2D.

La tarea consiste en encontrar un método algorítmico eficaz para calcular el área total (la inexactitud también está bien) ocupada por figuras en ese espacio 2d, evitando la duplicación debida a los solapamientos.

Answer 1

Es difícil explotar el hecho de que estás proyectando cuboides (en lugar de objetos más complejos), y difícil de explotar la aleatoriedad de la dirección de proyección. Así que probablemente el mejor algoritmo es un genérico algoritmo de barrido plano (también conocido como "barrido de línea"). Se pueden encontrar apuntes de estos algoritmos por toda la web, normalmente calculan la intersección de objetos pero sólo se necesitan pequeñas modificaciones para construir la unión.

Ya que mencionas "inexactitud", se ha prestado atención a polígonos inexactos y "tolerados":

Cazals, Frédéric, y G. D. Ramkumar. "Algoritmos para calcular la intersección y la unión de polígonos tolerados con aplicaciones". AI EDAM 11, no. 4 (1997): 263-272.

Si quieres profundizar en las cuestiones de complejidad combinatoria, empieza por aquí:

Pach, János, Pankaj K. Agarwal y Micha Sharir. Estado de la unión (de objetos geométricos). American Mathematical Society, 2008.

Allí encontrarás este bonito teorema para una restringida restringida de formas: La complejidad de la unión es lineal en lugar de cuadrática.

TEOREMA 2.2 (Kedem et al.). Sea $C = \{C_1, C_2, . . . , C_n\}$ sea una familia de $n \ge 3$ pseudodiscos en el plano. Entonces el límite de $U(C)$ consta como máximo de $6n – 12$ arcos elementales, y este límite es estricto en el peor de los casos.

Los límites de dos pseudodiscos cruzar como máximo dos veces.