Zone d'intersection entre le cercle et le rectangle
Je suis à la recherche d'un moyen rapide pour déterminer la zone d'intersection entre un rectangle et un cercle (j'ai besoin de faire des millions de ces calculs).
Une propriété spécifique, c'est que dans tous les cas, le cercle et le rectangle ont toujours 2 points d'intersection.
- Ont-ils seulement 2 points d'intersection? Ou ont-ils au moins 2 points d'intersection?
- Avez-vous besoin de calculer l'aire en unités carrées, ou renvoyer un ensemble de segments de ligne qui définissent la zone?
- Si l'on est à l'intérieur de l'autre ou si les deux ne se chevauchent pas du tout, il n'y a pas de points d'intersection. Si le cercle est tangent à l'un des côtés du rectangle, il n'y a qu'un point d'intersection.
- Qu'est-ce exactement avez-vous besoin de savoir? Si c'est pour simple comparaison, vous pouvez être en mesure de faire moins que ce que vous devez faire pour la réponse exacte.
Vous devez vous connecter pour publier un commentaire.
2 points d'intersection:
0 sommets est à l'intérieur du cercle: L'aire d'un segment circulaire
1 vertex est à l'intérieur du cercle: La somme des surfaces d'un segment circulaire et d'un triangle.
2 sommets sont à l'intérieur du cercle: La somme des aires des deux triangles et un segment circulaire
3 sommets sont à l'intérieur du cercle: L'aire du rectangle moins l'aire d'un triangle plus l'aire d'un segment circulaire
Pour le calcul de ces domaines:
La plupart des points que vous aurez besoin de l'utiliser peut être trouvée par trouver le intersection d'une droite et d'un cercle
Les domaines dont vous avez besoin pour calculer peut être trouvé par le calcul de l'aire d'un segment circulaire et le calcul de l'aire d'un triangle.
Vous pouvez déterminer si un sommet est à l'intérieur du cercle par le calcul de la distance à partir du centre est inférieur au rayon de.
J'ai réalisé que c'était répondu il y a un moment mais je suis résoudre le même problème et je ne pouvais pas trouver un out-of-the-box solution viable que je pourrais utiliser. Notez que mes boîtes axe aligné, ce n'est pas tout à fait indiquée par l'OP. La solution ci-dessous est complètement générale, et il va travailler pour un certain nombre d'intersections (pas seulement deux). Notez que si vos boîtes ne sont pas de l'axe-alignés (mais encore des boîtes avec des angles droits, plutôt que général quads), vous pouvez prendre avantage de les cercles à l'ronde, faire pivoter les coordonnées de tout de sorte que les extrémités de la boîte en haut de l'axe aligné et puis utiliser ce code.
Je veux utiliser l'intégration - qui semble être une bonne idée. Commençons par l'écriture d'un évident formule pour tracer un cercle:
C'est gentil, mais je ne suis pas en mesure d'intégrer l'aire de ce cercle sur
x
ouy
; celles-ci sont différentes quantités. Je peux seulement d'intégrer plus de l'angletheta
, produisant des zones de tranches de pizza. Pas ce que je veux. Essayons de changer les arguments:C'est mieux comme ça. Maintenant, compte tenu de la gamme de
x
, je peux intégrer plus dey
, pour obtenir une zone de la moitié supérieure du cercle. Ceci tient seulement pourx
dans[center.x - radius, center.x + radius]
(les autres valeurs peuvent causer imaginaire sorties), mais nous savons que la zone à l'extérieur de cette gamme est de zéro, de sorte que est manipulé facilement. Supposons cercle unité pour des raisons de simplicité, on peut toujours brancher le centre et le rayon de revenir plus tard:Cette fonction a, en effet, une partie intégrante de la
pi/2
, puisque c'est une moitié supérieure du cercle unité (la zone du demi-cercle estpi * r^2 /2
et nous l'avons déjà dit unité, ce qui signifier = 1
). Maintenant, nous pouvons calculer la surface d'intersection du demi-cercle et un infiniment grande boîte, debout sur l'axe des x (le centre du cercle se trouve aussi sur la l'axe des x) par intégration sury
:Cela peut ne pas être très utile, comme l'infiniment grand boîtes ne sont pas ce que nous voulons. Nous avons besoin d'ajouter un paramètre plus afin d'être en mesure de libérer le bord inférieur de l'infiniment grande boîte:
Où
h
est le solde (positif) de la distance de la bordure inférieure de notre infinie box à partir de l'axe des abscisses. Lesection
fonction calcule le solde (positif) de la position de l'intersection du cercle unité avec la ligne horizontale donnée pary = h
et l'on pourrait définir par la résolution:Maintenant, nous pouvons obtenir le cours des choses. Alors, comment calculer l'aire d'intersection d'un nombre fini case d'intersection d'un cercle unité au-dessus de l'axe des x:
C'est gentil. Alors, comment sur une zone qui n'est pas au-dessus de l'axe des x? Je dirai que non, toutes les boîtes sont. Trois cas se présentent:
Assez facile? Nous allons écrire un peu de code:
Et quelques tests unitaires:
La sortie de ce est:
Qui semble correct pour moi. Vous pouvez inline fonctions si vous n'avez pas confiance en votre compilateur pour le faire pour vous.
Il utilise 6 sqrt, 4 asin, 8 div, 16 mul et 17 ajoute pour les boîtes qui ne coupe pas l'axe des x et un double de ce qui (et 1 de plus ajouter) pour les boîtes qui ne. Notez que les divisions sont en rayon et pourrait être réduit à deux divisions et un tas de multiplications. Si la zone en question a recoupé l'axe des x, mais ne coupe pas l'axe des y, vous pouviez faire tourner le tout par
pi/2
et de faire le calcul du coût d'origine.Je suis en utilisant comme référence pour déboguer sous-pixel précis de l'anticrénelage de cercle rasterizer. Il est lent comme l'enfer :), j'ai besoin de calculer l'aire d'intersection de chaque pixel de la zone de délimitation du cercle avec le cercle pour obtenir de l'alpha. Vous pouvez sorte de voir que cela fonctionne et pas de numérique, des artefacts apparaissent. La figure ci-dessous est le tracé d'un tas de cercles dont le rayon augmente de 0,3 px à environ 6 px, disposés en spirale.
J'espère que ce n'est pas mauvais formulaire pour poster une réponse à une question aussi ancienne. J'ai regardé sur les solutions ci-dessus et travaillé sur un algorithme qui est similaire à Daniels première réponse, mais bon d'un peu plus serré.
En bref, assumer l'ensemble de la zone est dans le rectangle, soustraire hors les quatre segments de la moitié externe des avions, puis ajouter tous les domaines dans les quatre quadrants externes, en écartant les cas triviaux le long du chemin.
pseudocde (mon code est seulement ~12 lignes..)
D'ailleurs, cette dernière formule pour l'aire d'un cercle contenu dans un plan quadrant est facilement calculée comme la somme d'un segment circulaire, deux triangles rectangles et un rectangle.
Profiter.
Les suivants est la façon de calculer la zone de chevauchement entre le cercle et le rectangle où le centre du cercle se trouve à l'extérieur du rectangle. D'autres cas peuvent être réduits à ce problème.
La zone peut être calculer par intégration de l'équation de cercle y = sqrt[a^2 - (x-h)^2] + k où a est le rayon, (h,k) est le cercle de centre, pour trouver l'aire sous la courbe. Vous pouvez utiliser l'ordinateur d'intégration où la zone est divisée en de nombreux petits rectangle et le calcul de la somme d'entre eux, ou tout simplement l'utilisation de la forme finie ici.
Et voici un source en C# en œuvre le concept ci-dessus. Notez qu'il existe un cas particulier où le x est à l'extérieur des limites du cercle. Je viens d'utiliser une solution de contournement simple ici (ce qui n'est pas de produire les réponses correctes dans tous les cas)
Remarque: Ce problème est très similaire à celle dans Google Code Jam 2008 ronde de Qualification problème: Tapette à Mouche. Vous pouvez cliquez sur le score liens pour télécharger le code source de la solution.
Merci pour les réponses,
J'ai oublié de mentionner que la zone estimatations étaient assez.
Qu'; s pourquoi à la fin, après avoir regardé toutes les options, je suis allé avec monte-carlo estimation où je générer au hasard des points du cercle et de tester si ils sont dans la boîte.
Dans mon cas, c'est probablement plus performant. (J'ai une grille placée sur le cercle et j'ai pour mesurer le rapport du cercle appartenant à chacune des mailles. )
Grâce
Peut-être vous pouvez utiliser la réponse à cette question, où la zone d'intersection entre un cercle et un triangle est demandé. Diviser votre rectangle en deux triangles et utiliser les algorithmes qui y sont décrits.
Une autre façon est de tracer une ligne entre les deux points d'intersection, ce partage votre région en un polygone (3 ou 4 bords) et un segment circulaire, pour à la fois vous devriez être capable de trouver les bibliothèques plus facile ou pour faire les calculs vous-même.
Voici une autre solution pour le problème: