Zone D'Intersection de deux Rectangles tournés
j'ai deux rectangles 2D, définis comme un origine (x,y) un taille (hauteur, largeur) et un angle de rotation (0-360°). Je peux garantir que les deux rectangles sont de la même taille.
je dois calculer la zone approximative d'intersection de ces deux rectangles.
le calcul n'a pas besoin d'être exact , bien qu'il puisse être. Je vais comparer le résultat avec d'autres zones d'intersection pour déterminer la plus grande zone d'intersection dans un ensemble de rectangles, il n'a donc besoin d'être précis par rapport à d'autres calculs du même algorithme.
j'ai pensé à utiliser la zone de la boîte limite de la région intersectée, mais j'ai du mal à obtenir les sommets de la région intersectée à cause de tous les différents cas possibles:
j'écris ce programme dans Objective-C dans le cadre du Cocoa, pour ce que ça vaut, donc si quelqu'un connaît des raccourcis en utilisant NSBezierPath ou quelque chose vous êtes invités à Le suggérer aussi.
6 réponses
un algorithme simple qui donnera une réponse approximative est l'échantillonnage.
divisez un de vos rectangles en grilles de petits carrés. Pour chaque point d'intersection, vérifier si ce point est à l'intérieur de l'autre rectangle. Le nombre de points qui se situent à l'intérieur de l'autre rectangle sera une assez bonne approximation de la zone de la zone de chevauchement. L'augmentation de la densité de points d'augmenter la précision du calcul, au détriment des performances.
pour compléter les autres réponses, votre problème est une instance de line clipping , un sujet fortement étudié en infographie, et pour lequel il existe de nombreux algorithmes disponibles. Si vous tournez votre système de coordonnées de sorte qu'un rectangle a un bord horizontal, alors le problème est exactement découpage de ligne à partir de là.
vous pourriez commencer par article Wikipédia sur le thème , et enquêter à partir de là.
dans tous les cas, calculer le polygone exact d'intersection de deux polygones convexes est une tâche facile, car tout polygone convexe peut être considéré comme une intersection de demi-plans. "Découpe séquentielle" fait le travail.
choisir un rectangle (n'importe quel) comme rectangle de coupe. Iterate à travers les côtés du rectangle de découpe, un par un. Couper le deuxième rectangle par la ligne qui contient le côté courant du rectangle de coupe et jeter tout ce qui se trouve dans le demi-plan "extérieur".
une fois que vous avez fini d'itérer à travers tous les côtés de coupe, ce qui reste de l'autre rectangle est le résultat.
vous pouvez calculer la zone exacte.
- faites un polygone parmi les deux rectangles. Voir cette question (en particulier cette réponse ), ou utiliser la bibliothèque gpc .
- trouvez l'aire de ce polygone. Voir ici .
-
L'espace partagé est
area of rectangle 1 + area of rectangle 2 - area of aggregated polygon
prendre chaque segment de ligne de chaque rectangle et voir s'ils se croisent. Il y aura plusieurs possibilités:
-
si aucune zone partagée n'est intersectée, zéro - à moins que tous les points de l'un soient à l'intérieur de l'autre. Dans ce cas, l'espace commun est le domaine de la petite.
-
a si deux bords consécutifs d'un rectactangle se croisent avec un seul bord d'un autre rectangle, celui-ci forme un triangle. Calculer son aire.
B. Si les bords ne sont pas conséquents, cela forme un quadrilatère. Calcule une ligne à partir de deux coins opposés du quadrilatère, ce qui fait deux triangles. Calculer la superficie de chaque zone et la somme.
-
Si deux bords d'une intersection avec les deux bords de l'autre, alors vous aurez un quadrilatère. Calculer comme en 2b.
-
si chaque bord d'un croisement avec chaque bord de les autres, vous aurez un octogone. Divisez - le en triangles ( par exemple, dessinez un rayon d'un sommet à l'autre pour faire 4 triangles )
@edit: j'ai une solution plus générale.
Vérifier le cas particulier en 1.
alors commencez avec n'importe quel vertex qui se croise, et suivez les bords de là à n'importe quel autre point d'intersection jusqu'à ce que vous soyez de retour au premier vertex qui se croise. Ceci forme un convexe polygone. dessinez un rayon du premier vertex vers chaque vetex opposé (par exemple, sautez le vertex à gauche et à droite. Cela le divisera en un tas de triangles. calculer la superficie de chaque zone et la somme.
Un brute-force-ish:
- prendre tous les points de l'ensemble des rectangles] + [points d'intersection des bords]
- supprimer les points qui ne sont pas à l'intérieur ou sur le bord des deux rectangles.
- maintenant vous avez des coins d'intersection. Notez que l'intersection est convexe.
- trier les points restants par angle entre le point arbitraire de l'ensemble, arbitraire autre point, et le point donné.
- Maintenant, Vous avez les points d'intersection dans l'ordre.
- calculer la superficie de la façon habituelle (par produit croisé)
.