Comment croiser plusieurs polygones?

Question

Je recherche un algorithme avec les entrées et sorties suivantes:

Entrée: un ensemble de polygones dans un plan. EG P1 ... PN et S. (P1 ... PN pourrait être concave, S est convexe.)

Sortie: la zone de l'ensemble de polygones dans ce plan qui est égale à la différence de S et de l'union de P1 ... Pn.

J'ai trouvé des algorithmes pour croiser ou fusionner deux polygones. Mais comme chacune de ces opérations pourrait produire plusieurs polygones I créet des tonnes de polygones si je le faisais naïvement.

SO: comment gérer l'intersection de plusieurs polygones?

Ce serait OK, si tous les polygones sont connectés ensemble car seule la zone est ce que je suis. Ma pensée était d'utiliser des polygones dirigés pour simuler des trous, mais j'ai encore un problème pour savoir si j'ai une "représentation minimale" comme N pourrait exploser. [Comprenez-vous de quoi je parle? C'est assez étrange ...)

Answer 1

Vous pouvez jeter tous les bords ensemble dans un algorithme de ligne de balayage. Ce n'est peut-être pas optimal (?) Mais au moins vous obtiendrez la représentation minimale que vous recherchez.

Answer 2

Une solution consiste à convertir chaque polygone en un tas de triangles. Une fois que vous faites cela, il est assez facile de trouver l'union / intersection / différence entre un ensemble de zones, car vous pouvez remplir les mêmes fonctions trivialement sur un triangle (le résultat sur deux triangles peut inclure jusqu'à 6 triangles).

Answer 3

L'approche la plus simple serait de décomposer vos polygones concaves en convexes. Ensuite, se croisant deux polygones convexes est presque trivial.