J'ai un ArrayList de Point -s. Il est garanti que les points font partie d'un polygone convexe.Java: Périmètre d'un polygone convexe
Comment calculer le périmètre de ce polygone convexe?
Mise à jour: Les points du ArrayList sont de tout ordre
Mise à jour 2: Tous les points font partie du bord du polygone convexe
sont les points dans l'ordre? Si oui, vous avez juste besoin de résumer la distance de chaque sommet à la suivante
Ils sont hors de toute commande, de sorte que la méthode de commande est mon réel question je suppose. – makesz1
Je sais comment faire cela, mais j'ai pensé que je vous mettrais au défi en premier: Juste en utilisant les points, pouvez-vous trouver le centre du polygone? Et si oui, une fois que vous avez le centre, pouvez-vous en quelque sorte utiliser les angles des lignes faites du centre à tous les points pour les ordonner? – ControlAltDel
Si les points ne sont pas commandés, c'est impossible sans déterminer le bon ordre. C'est parce que s'il y a plus de 3 points, il y a plus d'un polygone qu'ils pourraient former.
Je ne suis pas entièrement sûr que la contrainte que les points forment un polygone convexe soit suffisante pour déterminer une forme canonique à partir du nuage de points.
Je suppose que cela en prenant un point aléatoire de la liste, puis en recherchant le le plus proche le point restant, vous pouvez construire un ordre canonique. De là, il suffit de résumer la longueur des lignes formées par des points consécutifs.
Modifier: À la réflexion, grattez cette idée. Cela ne marchera pas dans tous les cas. Cela vous laisse permuter les points et vérifier si le polygone formé est bien convexe.
La question sur la façon de vérifier si un polygone est convexe a été posée et répondue ici: How do determine if a polygon is complex/convex/nonconvex?
Ne serait-il pas possible de déterminer si les points étaient hors service en cherchant des segments de ligne qui se chevauchent? –
@SaviourSelf Eh bien, une intersection entre deux segments de ligne serait à coup sûr une preuve que le polygone n'est pas convexe; C'est donc une pièce pour aider à résoudre le puzzle. – Durandal
Oui, mais si tous les points sont utilisés, y aurait-il seulement 1 circuit sans intersections? –
Vous pouvez convertir des points dans une nouvelle classe de LineSegments, puis additionnez la longueur des segments de ligne. Si les points sont hors service, vous pouvez construire une matrice pour déterminer qui est connecté entre eux, et si vous avez un polygone complet. –
Quelle serait la bonne méthode pour trouver les paires de points autour du polygone? Comment dois-je commander la liste? – makesz1
Tous les points sont-ils utilisés dans la création de ce polygone? –