Rastérisation de disque, la case appartient-elle au disque ?

Bonjour,

Les maths n'étant pas mon point fort, je viens ici pour vous demander un peu d'aide pour décider si une case du cadrillage appartient au disque ou non. Un petit schéma :

http://img43.imageshack.us/img43/4236/schemau.png

L'espace est découpé en cases (carrées). Le centre d'une case correspond à un point du plan (un point avec des coordonnées entières). La case dont on se s'occupe est la case 1. Le centre de la case 1 correspond au point de coordonnées (x = 0 ; y = 0).

Pour déterminer si la case 2 appartient au disque de rayon 4 du schéma, je n'arrive pas à me décider entre deux solutions :
- regarder si le centre de la case 2 apartient au disque
- regarder si le disque "occupe" plus de la moitié de la case

Déjà, à votre avis, c'est quoi le plus logique entre les deux ?

Ensuite, pour la première solution, c'est pas trop difficile, il faut calculer la distance entre le centre de la case 1 et celui de la case 2, puis regarder si cette distance est plus petite que le rayon du cercle. Par contre, je vois pas bien comment calculer la surface commune à la case 2 et au disque. Quelqu'un à une idée ?

Citation:

---

Envoyé par hellfoust

Pour déterminer si la case 2 appartient au disque de rayon 4 du schéma, je n'arrive pas à me décider entre deux solutions :
- regarder si le centre de la case 2 apartient au disque
- regarder si le disque "occupe" plus de la moitié de la case

Déjà, à votre avis, c'est quoi le plus logique entre les deux ?

---

"Logique", je ne sais pas. Mais on utilise très fréquemment la méthode 1 (midpoint).

Citation:

---

Par contre, je vois pas bien comment calculer la surface commune à la case 2 et au disque. Quelqu'un à une idée ?

---

Tu peux déjà faire des approximation :
- en calculant les 4 distances aux 4 coins du carré et en faire la moyenne.
- en approximant l'arc de cercle dans le carré par une droite
- ...

Salut!

Citation:

---

la case appartient-elle au disque ?

---

Tout dépend de la définition que tu donnes du verbe appartenir et cette définition est arbitraire; elle dépend de ce que tu veux faire avec le résultat.
Jean-Marc Blanc

Bonjour,

Déjà, merci de votre intérêt !

@Jean-Marc Blanc : dans la case du centre se trouve un personnage, le rayon du cercle correspond à la distance jusqu'à laquelle il voit. Donc une case appartient au disque si le personnage peut voir les objets ou les autres personnages qui se trouvent dessus.

Pour ce qui est des approximations, j'ai l'impression que faire la moyenne des quatres coins de la case vas me donner le même résultat qu'avec la technique du centre de la case. Pour la deuxième approximation, elle à l'air plutôt satisfaisante, mais je suis un peu maniac et je voudrais avoir un résultat exact.

J'ai trouvé une solution un peu lourde mais qui marche :

http://img198.imageshack.us/img198/8...straction1.png

- calculer les deux intersections entre la case et le cercle (intersec1 et intersec2)
- calculer l'angle <intersec1 - centre - intersec2>
- calculer l'aire (aire 1 + aire 2 + aire 3) en faisant : (aire_disque / 360) x angle <intersec1 - centre - intersec2>
- trouver l'aire 3 par soustraction des aires 1 et 2 qui sont faciles à calculer (car ce sont des triangles)

Dans le cas où il y aurait deux sommets de la case à l'intérieur du cercle :
(j'en ai mis trois à l'intérieur pour qu'on voit mieux, mais il faut considérer qu'il n'y en a que deux)

http://img194.imageshack.us/img194/1...straction2.png

Pour obtenir l'aire a6, on fait pareil, on calcule (a4 + a5 + a6) en faisant (aire_disque / 360) x angle, puis on obtient a6 en déduisant a4 et a5 qui sont des triangles.

Cette solution marche, mais il y a surement un moyen plus efficace.
On considère uniquement le quart de disque nord-est :

http://img194.imageshack.us/img194/4...aisolution.png

Lorsqu'on déplace le segment S vers la droite, l'aire qui est initialement égale à la surface du disque divisée par quatre diminue. Il faudrait arriver à exprimer l'aire restante en fonction du déplacement vers la droite du segment S.

Si ton cercle est beaucoup plus grand que ton carré, il y a 3 cas d'intersection possibles :

• 1 point à l'extérieur du cercle
• 2 points à l'extérieur du cercle
• 3 points à l'extérieur du cercle

La surface commune peut se décomposer en un polygone (à 3, 4, ou 5 sommets) + un segment circulaire.

L'aire du polygone se calcule aisément (par géométrie ou intégration).
L'aire du [ame]http://fr.wikipedia.org/wiki/Segment_circulaire[/ame] est une formule connue.

Merci :ccool:
En fait le segment circulaire c'est tout ce qu'il me manquait. Topic résolu.