Comment trouver un arbitrairement orienté minimum bounding box en c++

Donc, disons que j'ai une liste de N paires de positifs à long coordonnées (points).

Comment puis-je trouver le plus petit rectangle contenant tous?

Le rectangle peut aussi avoir flottant coordonnées et être tourné dans n'importe quel angle et plus rétréci... et Pas seulement X, Y, Largeur et Hauteur!

Comment trouver un arbitrairement orienté minimum bounding box en c++

Je sais déjà comment faire pour trouver le plus petit polygone ou de ne pas faire pivoter le rectangle, mais ce n'est pas ce dont j'ai besoin...je voudrais savoir comment trouver la arbitrairement orienté minimum de la boîte englobante.

  • "Vecteur de la composition de l'algorithme de" ressemble à quelque chose de CSI:Miami 😛
  • Wow. Ça serait bien, mais je ne pense pas qu'ils vont trouver une quelconque utilité pratique pour le mien...
  • Code de Golf avait une similaire mais pas exactement la même question que vous pourriez être en mesure de s'adapter.
  • +1 pour le CSI boutade
  • Non, il n'est même pas proche de ce dont j'ai besoin.
  • Comment "parfait", a-t-elle de l'être? Est "proche de l'optimal" ok?

InformationsquelleAutor Vercas | 2011-03-15
  1. 9

    Voir http://www.geometrictools.com/Source/ComputationalGeometry.html

    La section "Minimum-zone de la zone" a différents exemples.

    • Merci!!!! Ce fichier contient la fonction dont j'ai besoin! J'ai aussi trouvé plus de choses que j'ai besoin sur ce site!
    • Je savais qu'il n'a que je l'ai utilisé ce matin moi-même. La moitié de la bataille dans la recherche de quelque chose, c'est de savoir les termes corrects!
    • J'avais su les termes mieux si l'anglais était ma langue naturelle...
    • Eh bien j'ai entendu assez pour savoir ce que vous voulez dire...même si google n'a pas 😉
    • À partir de la description, cela ne semble plus précis. Un vrai minimale de la zone de la zone serait le plus susceptible d'avoir un centre qui était pas à la moyenne des points. Ils semblent être l'aide d'un raccourci pour simplement obtenir quelque chose d'assez près.
    • cela ne permet pas de calculer le minimum de la boîte. La réponse correcte est donnée par la "rotation des étriers". cgm.cs.l'université mcgill.ca/~orm/rotcal.html
    • Le lien d'origine n'a, donc, j'ai roulé la réponse même si maintenant il d'une erreur 404.

    InformationsquelleAutor Fraser
  2. 10

    Ce page wikipedia notes, que vous pouvez résoudre ce problème en utilisant le fait que le minimum rectangle doit avoir un bord colinéaire avec l'un des bords de l'enveloppe convexe.

    • Cette page de Wikipédia ne contient pas un algorithme; la "rotation des étriers" page de liens vers elle contient un algorithme, mais pas pour ce problème. Quelques liens: cgm.cs.l'université mcgill.ca/~orm/maer.html, google.com/codesearch/.... Notez que cette approche fonctionne pour n'importe quel raisonnable définition de "minimum"; en particulier, il travaille pour "surface minimale" et "minimum de périmètre"; ces deux coïncident souvent, mais pas toujours.
    • Grâce Gareth (hi!) J'ai modifié le libellé de ma réponse.
    • Pour chaque segment de l'enveloppe convexe, vous pouvez calculer l'aire du rectangle de délimitation de l'utiliser, et de choisir la plus petite. Il s'exécute en O(n^2) du nombre de points sur la coque, cependant.
    • Salut, Paul. Je pensais que c'était probablement la même Paul Hankin :-). Thomas, en effet, il s'avère être O(n) une fois que vous avez l'enveloppe convexe, si vous le faites à droite. Voir, par exemple, le premier lien dans mon commentaire ci-dessus.
    InformationsquelleAutor
  3. 3

    Peut-être que ce livre peut aider: Plus petit k point rectangle d'encadrement de l'arbitraire de l'orientation

    • Malheureusement, cela n'aide pas.
    • Ce document aborde le difficile problème de trouver un cadre place. Comme vous pouvez le voir, la complexité est O(N2Log(N)), alors que le rectangle de délimitation est facilement obtenue en O(N Log(N)).
    InformationsquelleAutor fbafelipe
  4. 1

    Je ne sais pas si cela peut vous aider, mais voici mes réflexions sur la façon dont je voudrais aborder le problème.

    Vous aurez besoin des fonctions de trouver votre "coin-la plupart des" points (dans votre exemple, la gauche, 2 à droite et 2 points). Compte tenu de ces 4 points, les relier par des lignes.

    (Dans votre exemple, l'image, le point le plus haut ne serait pas contenue par l'généré rectangle, alors...)
    Vous aurez alors besoin d'une fonction pour déterminer si le rectangle généré contient tous les points donnés; si pas, d'étendre les points de terminaison (dans ce cas, les 2 premiers points de l'généré rectangle) par N (qui est soit une mesure unique ... dire un pixel, ou si vous êtes intelligent, la distance du point qui est en dehors des limites plus ou moins une personne à charge sur la direction) et de ré-évaluer.

    • Qui ne fonctionne que pour axe les aligner MBBs
    • Bon point; dans ce cas, vous auriez besoin de dériver la fonction (y=mx+b) représente la connexion entre les deux points, et continuer sur cette voie-le long des deux côtés de l'original de votre rectangle.
    InformationsquelleAutor JNadal
  5. 1

    Peut-être ce qui fonctionne pour vous:

    • trouver le point central de tous vos points (somme de tous les x /nombre de x, de même pour y)
    • prendre le point le plus éloigné du centre comme un point d'angle
    • projet de ligne à travers le 2e point le plus éloigné dans un angle de 90° de l'angle de point de
    • itérer sur tous les points de l'autre côté du point central et trouver le minimum
    • J'ai essayé, jusqu'à la 2ème étape... 🙁
    • Étape #3 et #4 est super confus et ne font pas de sens pour moi
    InformationsquelleAutor DaClown