Version imprimable
Le problème est le suivant: soit un polygone P quelconque du plan (i.e. pas forcément convexe). On recherche l'ensemble des points M vérifiant d(M,P)<D, où D est une constante.
L'idée est de donner la séquence des sommets du polygone définissant cette nouvelle zone.
J'ai construit une solution à ce problème, mais je voulais avoir votre avis...
Salut,
La distance d'un point par rapport à un polygone, c'est bien la plus petite distance entre ce point et chacun des points du polygone?
Tu dis que tu obtiens un polygone, mais géométriquement, certains côtés sont des arcs de cercle. Sinon pour obtenir les sommets, il suffit de projeter les sommets du polygone initial sur des parallèles aux côtés de ce polygone pour des côtés adjacent avec un angle extérieur supérieur à 180. Pour des côtés adjacent avec un angle inférieur à 180, c'est l'intersection des parallèles.
non?
Je ne sais pas si j'ai été très clair, j'essaierai de faire un schéma si j'ai un peu de temps.
Bonne réponse, ce n'est pas un polygone c'est une chaine de segments et de portions de cercle!
Un petit exemple ci-dessous...
http://www.imageshotel.org/images/Nemerle/ex.jpg
J'ai gagné, alors? :king: Et j'ai gagné quoi? :wow:
Bonjour,
Je dirais que ça ressemble beaucoup à une dilatation non ?
nan, t'as pas gagné, ta "solution" est un peu légère... ou disons partielleCitation:
Envoyé par magelan
Ah zut!
C'est vrai que avec un papier et un crayon, c'est facile mais l'implémentation est plus délicate...
Une idée mais je ne l'ai pas vérifié :
On trace l'ensemble des segment parallèle aux côtés du polygone : on obtient un ensemble de point. On calcule l'enveloppe convexe de cet ensemble de points. cela devrait permettre d'éliminer l'ensemble des segments qui n'appartiennent pas au contour final. Dans cette enveloppe convexe, on retire les segments qui ne sont pas des segments parallèles aux cotés du polygone initial et on complète le contour avec les arcs de cercle en parcourant les segments dans un sens donné. Si le cercle possède une intersection avec le segment suivant, on continue, sinon il faut un autre arc de cercle. Et ainsi de suite jusqu'au point initial.
Et ta solution, c'est quoi?
La somme de Minkowski entre P et un disque de rayon D ? :PCitation:
Envoyé par Nemerle
J'ai implémenté un algo pour trouver l'envellope d'un polygone de forme quelconque, mais l'envellope résultante n'est qu'approchée en fonction d'une précision fournie en paramètre.
Ok, ci-dessous une solution. On approxime polygonalement un arc de cercle par 3 points, pour simplifier. Sautez le point (b) en 1ière lecture, cas d'exception.
Soit P1…Pn les sommets du polygones, et n(i,i+1) la normale extérieure unitaire au coté PiPi+1. Soit Ai le segment [P(i)+D* n(i,i+1),P(i+1)+D n(i,i+1)], i.e « PiPi+1 décalé de D ». On dira que Ai est un segment décalé. Soit Ri le rectangle défini par Ai et PiPi+1. Enfin, soit Ci le cercle de centre Pi et de rayon D, et Di son disque associé. On va constuire la séquence [W]=W1…Wq en ordre trigo des sommets définissant la zone d’exclusion :
a. On recherche un i tel que l’intersection de Ai avec X\{Ri} ne soit pas tout Ai.
b. Si le terrain n’est pas « une petite étoile » (a) est toujours vérifié. Si ce n’est pas le cas, on prendra i tel que :
i. le centre de Ci a sa coordonnée en x minimale
ii. on trouvera j tel que le centre de Cj, vu comme un sommet du parc, a son angle > à 180°, et est le plus proche du centre de Ci avec de plus Ci inter Cj non vide.
c. Une fois le i de (a) trouvé :
• le complémentaire de l’intersection de Ai avec X\{Ri} est un segment {A,B}=[Ai1+x(Ai2-Ai1), Ai1+y(Ai2-Ai1)] avec 0<=x<y<=1. De cette façon, le « sens » A->B reste dans l’ordre trigonométrique. Rq : on a noté {A,B}, car le segment a au moins une extrémité ouverte.
• A est le 1ier point de [W], et B est le second.
• Par construction, il existe au moins un objet Y de X qui contienne B.
• S’il n’existe qu’un tel Y, on le sélectionne.
• S’il en existe plus d’un (oh malheur…), notons X’ cet ensemble d’objets.
• soit D la droite de sommets les points Ai1+n(i,i+1)/10 et Ai2+n(i,i+1)/10. C’est donc la droite contenant le segment « Ai translaté du dixième de sa normale ».
• Pour chaque Y de X, soit éventuellement Q=Q(Y) le point d’intersection de Y avec D qui minimise d(Q,A). Si Q existe, on vérifie que Y appartient à X’. Si oui, Q est valide.
• Pour chaque Q valide, on calcule le produit scalaire BQ.BA
• On choisit l’objet Y tel que Q(Y) maximise ce produit scalaire. Un tel Y est UNIQUE.
• S’il n’existe aucun point d’intersection avec D, alors il existe dans X’ un unique segment décalé : on le sélectionne.
• Alors soit Y est un rectangle Rj, soit c’est un disque Dj. La 1ière passe de l’algo est finie. On sélectionne Z=Aj ou Cj en fonction de ce qu’est Y.
d. A partir de Z, on détermine alors le plus grand segment ou arc de cercle {B,B’} issu de B qui ne coupe pas X\{Y} :
• si Z est un segment, on ajoute B’ a la liste
• si Z est un cercle de centre c, on ajoute 1.025*(cB+cB’)/2 puis B’.
On réapplique alors (c) pour obtenir un nouvel objet Z.
e. On réitère alors (d) jusqu’à ce que le point B’ soit égal à A.