Tengo un conjunto de polígonos simples (sin agujeros, sin auto-intersecciones), y necesito verificar que no se crucen entre sí (uno puede estar completamente contenido en otro; eso está bien). Puedo comprobar esto simplemente comprobando el interior por vértice de un polígono frente a otros polígonos.

También necesito determinar el árbol de contención, que es el conjunto de relaciones que dicen qué polígono contiene un polígono dado. Como ningún polígono puede cruzarse con otro, cualquier polígono contenido tiene un contenedor único; el "próximo más grande". En otras palabras, si A contiene B contiene C, entonces A es el padre de B, y B es el padre de C, y no consideramos que A sea el padre de C.

La pregunta: ¿Cómo determino eficientemente las relaciones de contención y verifico el criterio de no intersección? Hago esto como una pregunta porque quizás un algoritmo combinado es más eficiente que resolver cada problema por separado. El algoritmo debe tomar como entrada una lista de polígonos, dada por una lista de sus vértices. Debe producir un B booleano que indique si ninguno de los polígonos se cruza con ningún otro polígono, y también si B = verdadero, una lista de pares (P, C) donde el polígono P es el padre del hijo C.

Esto no es tarea. Esto es para un proyecto de pasatiempo en el que estoy trabajando.