Fusionner des régions rectangulaires (Union booléenne) avec une précision entière

Question

Étant donné un certain nombre de rectangles intersectés, disjoints et en contact, comment trouver les polylignes de contour (multiples)? Les rectangles sont définis en coordonnées de pixels, donc ils ont une précision entière, mais ils peuvent être des milliers d'unités de grande taille.

j'ai vraiment besoin des coordonnées numériques pour les grandes lignes, la fusion des régions GDI ne fera pas. Je sais que je peux simplifier le problème en créant une région GDI et en appelant GetRegionScans, mais cela ne résoudra toujours pas le problème. Cela fait partie de l'interface utilisateur en temps réel, donc l'algorithme doit être raisonnablement rapide (je ne devine jamais plus d'une douzaine de boîtes, peut-être une centaine). Je le fais en C#, mais comme il s'agit d'une question algorithmique, je ne me soucie pas vraiment du langage. Toutes les idées sont les bienvenues.

Answer 1

Je ne sais pas si cela répond à vos exigences de performance, mais il devrait fonctionner:

1. Commencez avec un ensemble vide de rectangles.
2. Ajoutez chaque rectangle à l'ensemble. Si un rectangle chevauche un rectangle existant, divisez les rectangles en autant de rectangles que nécessaire, de sorte qu'aucun rectangle n'en chevauche un autre.
3. Ajoutez les quatre côtés de chaque rectangle sans chevauchement à un ensemble de lignes.
4. Supprime toutes les lignes qui ne sont pas uniques.

L'ensemble résultant contient toutes les lignes qui constituent le contour.

---