Je suis des sommets d'un polygone avec des étiquettes sur eux. Je veux placer les étiquettes pour qu'ils soient toujours à l'extérieur du polygone. Donc, dans l'image ci-dessus, toutes les étiquettes vont bien à l'exception des n ° 3 et n ° 4, que je veux être sur le fond, à l'extérieur du polygone. Donc, en général, comment puis-je déterminer, pour un sommet particulier, comment le compenser de telle sorte qu'il soit en dehors du polygone?
3 Réponses :
Puisque vous ne montrez aucun code à vous, je vais juste énoncer des idées. Si vous souhaitez plus de détails, y compris le code, montrez plus d'effort de votre choix alors demander.
Je vais supposer ici que le polygone est supposé être un simple polygone - celui qui ne se croisit pas. Si un polygone se croisit elle-même, la définition de son "intérieur" n'est pas si simple et il existe plusieurs définitions de l'intérieur. Je ne supposerai pas que le polygone est convexe - tous les angles intérieurs sont inférieurs à 180 °. (Cela permettrait une réponse plus facile.) Je suppose également que vous voulez que le centre de votre étiquette soit en dehors du polygone mais permettra à un coin ou une petite partie de l'étiquette d'être à l'intérieur.
Premièrement, traverser le polygone et trouver son "angle d'enroulement", la quantité d'angle de direction change pendant la traversée. Si le polygone est simple, l'angle sera de + 180 ° ou -180 °. Un de ceux-ci signifie que vous avez traversé le polygone dans le sens des aiguilles d'une montre, l'autre signifie dans le sens contraire des aiguilles d'une montre. (Qui dépend de votre système de coordonnées: cartésien ou graphique ou autre.)
puis traverser le polygone à nouveau. Maintenant que vous connaissez la direction du polygone, à chaque sommet, vous pouvez déterminer si l'angle extérieur va dans le sens des aiguilles d'une montre ou dans le sens anti-horaire du segment entrant. Trouvez cette direction et la taille de l'angle, puis déplacez la moitié de cet angle dans cette direction. Déplacez une distance donnée du sommet le long de cet angle et vous avez la position du centre de votre étiquette.
Cela devrait bien fonctionner pour la grande majorité des polygones. Dans certains cas de bord pour des polygones non convexes, cet emplacement s'est éloigné du polygone dans une autre partie du polygone. Vous réduisez ensuite la distance que l'étiquette provient de son sommet jusqu'à ce que l'étiquette se déplace dans l'extérieur du polygone.
J'ai donné une réponse à une question connexe: Comment déterminer efficacement si un polygone est convexe, non convexe ou complexe? < / a>.
sur chaque sommet, les bords entrants et sortants forment un angle qui couvre un secteur. Vous pouvez placer l'étiquette à une certaine distance le long du bisteur de cet angle. Vous trouvez le vecteur de direction du bissecteur en ajoutant deux vecteurs de l'unité provenant du sommet dans les directions des bords.
Trouver le côté bissecteur correct nécessite des soins. En premier lieu, vous devez orienter le polygone, c'est-à-dire. Vérifiez s'il est dans le sens des aiguilles d'une montre ou dans le sens anti-horaire. Ceci est simplement fait en calculant la zone avec la formule de la chaussée et en testant le signe.
Puis, si j'ai raison, vous pouvez tester la zone de triangle formé par les deux bords et comparer son signe à celui de l'ensemble du polygone. Cela vous indique si l'angle est convexe ou réflexe, et vous connaissez le côté approprié. Pour un polygone convexe, le côté est toujours négatif pour un vecteur calculé comme ci-dessus.
Suivez peut-être quelque chose comme ceci: d'abord, assurez-vous que le polygone ne se croisit pas, voir les réponses précédentes. Ensuite, laissez le polygone être à la contre-danses dans le sens des aiguilles d'une montre et représenté par une matrice (une matrice 2 par N + 2) de ses sommets (les sommets sont traversés dans le sens anti-horaire)
double P[n+2][2] = {{pxn, pyn}, {px1, py1}, {px2, py2}, ..., {pxn, pyn}, {px1, py1}};
double Label_position[n][2];
void generate_labels(const double (&P)[n+2][2], double (&Label_position)[n][2]){
double v1[2];
double v2[2];
for(j = 1, j <= n, j = j+1) {
v1[0] = P[j][0] - P[j-1][0];
v1[1] = P[j][1] - P[j-1][1];
v2[0] = P[j+1][0] - P[j][0];
v2[1] = P[j+1][1] - P[j][1];
v1 = normalize(v1);
v2 = normalize(v2);
t = add_vectors(v1, v2);
t = normalize(t);
Label_position[j][0] = t[1] + P[j][0];
Label_position[j][1] = - t[0] + P[j][1];
}
}
Vous n'avez pas correctement implémenter la solution, vous vous êtes préoccupé par l'orientation.
@Yvesdaoust Comme je l'ai dit dans ma réponse, je suppose que le polygone n'est pas intersser de soi-même et est donné par un éventail de sommets, commandé consécutivement à la suite d'une orientation dans le sens inverse des aiguilles d'une montre. Avec ces conditions imposées aux données d'entrée, la routine génère les pointes des bisectors de l'unité pointant vers l'extérieur. Je ne prétends pas résoudre le problème dans sa pleine généralité, essayant simplement d'aider au cas où la personne ait raisonnable (ce qui est tout à fait probable, en examinant la situation d'un polygone convexe fourni) une situation à portée de main et n'a pas besoin Tous les scénarios compliqués possibles.
@Yvesdaoust avez-vous un exemple d'exemple, où cela ne fonctionne pas? Je veux juste voir où j'ai commis une erreur. Et je veux dire un exemple d'exemple où les restrictions d'entrée sont respectées, donc aucun polygone auto-interseur ou des sommets ordonnés dans un ordre aléatoire.
Pourquoi le polygone serait-il convexe?
(Pour un contre-exemple, envisagez une fléchette ... épreuve à produqeri.org/wiki/definition :Quadrilater )
@Sneftel où est-ce que je suppose que le polygone est "convexe"? Ce que j'ai dit, dans mon commentaire, est que la photo fournie dans la question initiale est d'un polygone convexe, ce qui me fait penser que la personne qui demande ne traite pas de polygones auto-intersectifs.
Vous ne le faites pas, mais votre algorithme ne fonctionne que pour des polygones convexes.
@Sneftel non ce n'est pas. Cela fonctionne pour des polygones non convexes et non interssercents. Mes cas de test étaient non convexes.
Ah, je vois maintenant ... J'ai mal interprété votre code et je pensais que tu faisais la perp avant la bisection, plutôt qu'après.
@Sneftel Merci d'avoir corrigé les votes d'avance. Mon intention était de suggérer un élément d'un algorithme qui pourrait être utile de travailler sur ce problème, de ne pas le résoudre dans sa pleine généralité, ce qui pourrait être trop compliqué et prendre beaucoup de temps, surtout s'il semble que la personne qui demande peut ne pas être envisagée polygones auto-intersectant.
Est-il garanti que le polygone est simple (ne se croisit pas)? (Sinon, le "intérieur" du polygone n'est pas une question simple.) Est-il garanti que les angles intérieurs du polygone sont inférieurs à 180 °? (Si tel est le cas, il y a une réponse plus facile.) Avez-vous besoin de l'ensemble de l'étiquette pour être en dehors du polygone, ou si le centre peut-il être à l'intérieur avec le polygone éventuellement couper en face de l'étiquette? (Si tout doit être à l'extérieur, la routine aurait également besoin de détails sur la taille de l'étiquette.)
Vous pouvez construire des points de compensation extérieurs tels que décrit ici < / a>