J'ai fouillé Internet pendant des jours, mais j'ai été incapable de trouver une bonne réponse (ou d'au moins une personne qui m'a logique) à ce qui semble être une question commune. Comment une échelle est-elle un polygone arbitraire? En particulier, des polygones concaves. J'ai besoin d'un algorithme pouvant gérer des polygones concaves (définitivement) et auto-interssers (si possible). L'algorithme évident et simple que j'utilise pour manipuler de simples polygones convexes consiste à calculer le centroïde du polygone, en traduisant ce centroïde à l'origine, à la mise à l'échelle de tous les sommets et à la traduction du polygone à son emplacement d'origine.
Cette approche ne fonctionne pas pour de nombreux polygones concaves (ou peut-être tous), car le centroïde tombe souvent en dehors du polygone. L'opération de mise à l'échelle entraîne également une traduction et je dois être capable d'élaborer le polygone "en place" sans le résultat final étant traduit.
est-il au courant d'une méthode de mise à l'échelle des polygones concaves? Ou peut-être une façon de trouver le "centre visuel" qui peut être utilisé comme cadre de référence pour l'opération de mise à l'échelle?
Juste pour clarifier, je travaille dans un espace 2D et j'aimerais accumuler mes polygones à l'aide du "Centre Visual" comme cadre de référence. Donc, peut-être qu'une autre façon de poser la question serait, comment puis-je trouver le centre visuel d'un polygone concave et / ou auto-intersection?
merci!
3 Réponses :
Je ne suis pas sûr de votre problème.
Vous travaillez dans un espace affiné et vous recherchez une transformation affine pour faire échelle votre polygone?
Si j'ai raison, écrivez simplement la matrice de transformation:
et transformer votre polygone avec matrice
Vous pouvez rechercher la matrice de transformation affine.
espère qu'il aide
Si vous voulez garder le même "centre", vous pouvez simplement faire une homotethy de paramètre lambda avec centre g = barycenter du polygone:
Il vérifie: g ne bouge pas car c'est le centre de l'homotethy.
Cela vérifiera toujours la relation ci-dessous, ce sera donc le barycenter. (Vous venez de multiplier la relation par Lambda)
Dans votre cas G est facile à déterminer: g (x, y): (moyenne des valeurs x des points, moyenne des valeurs de y des points)
Et cela devrait faire ce dont vous avez besoin
La raison pour laquelle vous ne pouvez pas trouver une bonne réponse, c'est parce que vous êtes imprécis avec vos besoins. Définissez d'abord explicitement ce que vous entendez par «in-place». Ce qui est maintenu constant?
Une fois que vous avez compris cela, puis traduisez le point constant à l'origine, échelle du polygone comme d'habitude et traduisez le dos.
Mon idée de mettre en place est le "centre visuel" reste constante entre le polygone d'origine et le polygone à l'échelle. Je ne sais pas comment faire la recherche du centre visuel des polygones concaves ou si vous descendez sur la route d'essayer de trouver / définir un "centre visuel" est la bonne façon d'y aller.
Pouvez-vous poster des images d'un cas où l'utilisation du centroïde ne fonctionne pas bien?
Peut-être que Craig recherche un algorithme "décalage de polygone" - où chaque bord du polygone est décalé par une valeur donnée. Par exemple, étant donné un polygone orienté dans le sens des aiguilles d'une montre, les bords de compensation vers la gauche augmenteront la taille du polygone. Si c'est ce que Craig recherche, cela a été posé et répondit avant ici - Un algorithme pour gonfler / dégonfler (compensation, tampon) polygones .
Si vous recherchez une solution à l'emploi (OpenSource Freeware), j'ai également créé une bibliothèque de coupure ( Clipper ) écrit dans Delphi, C ++ et C # qui comprend une fonction de compensation de polygone assez simple.
Petit Internet HA, j'utilise actuellement Clipper pour ce projet et même posté sur les forums Sourceforge pour le projet à quelques reprises :-). Je pense que je m'attendais à ce que j'attendais un comportement de type décalage (où le polygone grandit / rétrécit "en place") d'une balance comme une opération (à l'aide d'un facteur plutôt que d'un décalage de l'unité) ... Merci encore pour la bibliothèque de la tondeuse, elle a Prouvé extrêmement utile!
Construire peut-être un rectangle de liaison artificiel (ou une autre région) pour vous aider avec le centrage et la traduction.
HMM, j'ai essayé d'utiliser le centre d'une boîte de sélection comme un cadre de référence, mais cela a laissé mon résultat traduit également. Également essayé à la mise à l'échelle de la boîte de sélection par le facteur souhaité et à l'aide des bords comme des cadres de référence, mais ne finissait toujours pas avec une solution pure non traduite. Avez-vous eu quelque chose de spécifique à l'esprit que je devrais essayer avec une boîte à bornes? Merci pour la réponse!
Ce que je veux dire par centre est le "centre visuel" du polygone. La meilleure façon que je puisse penser de décrire ce serait un "zoomer" sur un polygone, vous voudrez donc que le centre visuel du polygone reste constant dans tout le zoom.
Dessinez un polygone concave et étiquetez ce que vous entendez par le "Centre Visual". Visual Center n'est pas un terme technique et il n'est pas moyen de savoir ce que vous entendez par cela sans donner une définition précise ni d'au moins quelques exemples afin que nous puissions en déduire un.
Je voudrais, mais je n'ai pas assez de points pour poster des images. Le polygone évident qui montre que le problème est un polygone en forme de L. Comme le polygone est mis à l'échelle, la zone de polygone est également traduite de plus en plus de la centrale. Je ne sais pas comment définir le centre visuel autre que ces images que cela ne veut pas que je pose: Original polygone et Polygon échelonné par 4x
On dirait que vous êtes un peu confus sur votre notion de centre. Quelle est votre application précise pour cela? Quel est le problème avec le centre de masse? Je ne vois pas pourquoi c'est un problème si le "centre" n'est pas à l'intérieur du polygone dans le cas de polygones concaves. Faire un dessin s'il vous plaît où vous montrez: " Ceci est le centre de la masse, mais j'ai besoin cet autre point autre point d'être invariant sous la transformation"
@CRAIG OK, je vois. Où diriez-vous est le "centre visuel" de cela alors? i.imgur.com/ge2mr.png Pourquoi avez-vous besoin Le point d'être à l'intérieur du polygone?
Vous avez raison, le "Centre Visual" ne serait pas à l'intérieur de ce polygone. Je me sens muet .. Je pense que je peux me confondre mon comportement attendu d'une échelle de polygone avec le comportement qui peut être observé en effectuant un décalage de polygone le long des normales de sommet. Je devrai avoir des éclaircissements sur les exigences. Quelle première question embarrassante: - * .. Le comportement semble maladroit dans l'affaire en forme de L, devinez que j'aurais dû y avoir pensé d'autres, merci de me donner droit.
Dupliqué possible de un algorithme de gonflage / dégonflant (compensation, tampon) polygones < / a>