Soustraire un rectangle d'un polygone

Question

Je cherche un algorithme qui soustrait un rectangle d'un polygone simple et concave et qui renvoie un reste de polygones. Si le rectangle entoure le polygone, le reste est nul. Dans la plupart des cas, il semble qu'au moins un bord soit partagé entre le rectangle et le polygone.

J'ai fait des recherches sur l'internet, mais je n'ai pas trouvé de bonne piste.

Quelqu'un peut-il m'indiquer la bonne direction ?

Answer 1

C'est facile : trouvez les intersections entre le rectangle et les bords du polygone simple et coupez les segments à cet endroit. Cela ne nécessite pas de structure de recherche spatiale, car les 4 arêtes du polygone sont un facteur constant, de sorte que cela s'exécute en temps linéaire.

Il calcule ensuite une triangulation de Delaunay contrainte de tous les segments et utilise des points d'amorçage pour développer les régions. Combinez les régions de manière appropriée (les triangles à l'intérieur du polygone simple moins ceux à l'intérieur du rectangle moins les triangles à l'extérieur. Les triangles restants sont votre résultat et les bords de la bordure sont les bords du polygone résultant.

Edit : Je suis désolé si la réponse était trop courte. La figure ci-dessous illustre l'idée.
a) Les deux polygones d'entrée
b) Le CDT après insertion des segments (coupés)
c) Les régions cultivées
d) La région verte moins la région rouge
e) Les bords de la région d.