Je ne sais pas ce que vous entendez par "essayer toutes les rotations possibles", car il y en a une infinité, mais cette idée de base donne en fait une solution très efficace :
La première étape consiste à calculer la coque convexe. L'économie réalisée dépend de la distribution de vos données, mais pour des points choisis uniformément dans un disque unitaire, le nombre de points sur la coque devrait être O(n^1/3) . Il existe un plusieurs façons de le faire :
- Si les points sont déjà triés par l'une de leurs coordonnées, l'algorithme de Graham le fait en O(n). Pour chaque point dans l'ordre donné, on le relie aux deux précédents dans la coque, puis on supprime tous les points concaves (les seuls candidats sont ceux voisins du nouveau point) sur la nouvelle coque.
- Si les points ne sont pas triés, l'algorithme de l'emballage cadeau est un algorithme simple qui tourne à O(n*h). Pour chaque point de la coque en partant du point le plus à gauche de l'entrée, on vérifie chaque point pour voir si c'est le prochain point de la coque.
h est le nombre de points sur la coque.
-
L'algorithme de Chen promet des performances O(n log h), mais je n'ai pas vraiment exploré comment cela fonctionne.
- Une autre idée simple serait de trier les points par leur azimut et de supprimer les points concaves. Cependant, cela semble seulement O(n+tri) au début, mais je crains que ce ne soit pas le cas.
À ce stade, il devrait suffire de vérifier tous les angles collectés jusqu'à présent (comme nous l'avons conjoncturellement fait, Oliver Charlesworth et moi, et pour lequel Evgeny Kluev a offert l'essentiel d'une preuve ). Enfin, permettez-moi de faire référence à la référence pertinente dans La réponse de Lior Kogan .
Pour chaque direction, la boîte englobante est définie par les quatre mêmes points (pas nécessairement distincts) pour chaque angle de cet intervalle. Pour les directions candidates, vous aurez au moins un choix arbitraire à faire. Trouver ces points peut sembler être une tâche O(h^2) jusqu'à ce que vous réalisiez que les points extrêmes de la boîte de délimitation alignée sur l'axe sont les mêmes que ceux à partir desquels vous commencez la fusion, et que les intervalles consécutifs ont leurs points extrêmes soit identiques, soit consécutifs. Appelons les points extrêmes A,B,C,D dans l'ordre des aiguilles d'une montre, et que les lignes correspondantes délimitant la boîte de délimitation soient a,b,c,d .
![]()
Alors, faisons les calculs. La surface de la boîte englobante est donnée par |a,c| * |b,d| . Mais |a,c| est juste le vecteur (AC) projeté sur la direction du rectangle. Soit u soit un vecteur parallèle à a et c et laissez v soit le vecteur perpendiculaire. Laissez-les varier doucement sur toute la plage. Dans le langage vectoriel, l'aire devient ((AC).v) / |v| * ((BD).u) / |u| = {((AC).v) ((BD).u)} / {|u| |v|} . Choisissons également que u = (1,y) . Ensuite, v = (y, -1) . Si u est vertical, cela pose un léger problème de limites et d'infinis, alors choisissons simplement u pour être horizontal dans ce cas. Pour des raisons de stabilité numérique, nous allons simplement faire une rotation de 90° chaque u qui est à l'extérieur (1,-1)..(1,1) . La traduction de l'aire en forme cartésienne, si elle est souhaitée, est laissée comme un exercice pour le lecteur.
