Introduction

Cet été, je travaille sur une section de technologie à Västerås. J'ai travaillé dans la même entreprise et à peu près le même bureau pendant trois étés consécutifs. Le travail est très technique, amusant et stimulant. Contrairement à beaucoup d'autres emplois d'été dans un bureau, j'ai trouvé un où j'ai la responsabilité et d'apprendre à travailler avec les tâches courantes. Plus précisément, je travaille sur le développement d'outils pour simplifier les calculs en utilisant la plupart du temps MatLab, programmation de GUI et Java. Le nouveau orientée objet style de MatLab rend le code beaucoup plus clair que il ya quelques années.

Le problème

L'autre jour, j'ai fait face à un défi de taille. Simplifié elle s'est concentrée sur la recherche d'un polygone qui renferme un ensemble de points complexes qui sont dispersés dans le plan. Au début, je n'ai pas trouvé la fonction qui fait cela dans MatLab, qui était bien sûr très étrange. J'ai donc décidé de trouver un algorithme personnalisé. Dans ce post, je vais décrire mon algorithme.

Figure 1. Des exemples de shell. Convexe

Mon Alogritm

Je décris mon algorithme est en utilisant la figure 2. Pour commencer, je vais vous expliquer la difficulté à trouver un logement. La chose est que tous les points ne sont pas triés dans une structure. Si les points sont ordonnés autour d'un point central, on peut utiliser leur ordre et la distance du centre de résoudre le problème. Cependant, il faut au moins O (n log (n)) pour faire un tri linéaire. Mon algorithme fonctionne dans la liste non triés et sera probablement encore plus de temps, car je n'ai pas tiré la moindre preuve.

L'idée est certainement de commencer par mon point de vue dans la direction x et ensuite trouver le point à partir duquel la valeur de k devient le maximum. c'est à dire comprendre:

max (K_i) = (y_min - y_i) / (x_min - x_i) pour i = [tous les articles] Cela vous donne le point de p_2..

Tous les points de moins de valeur y X_min peut être omis. Tous les points ayant une valeur plus petite que x p_2 peut également être exclu pour en savoir plus.

K_2 se trouve alors en trouvant le point qui minimise:

k_1 - (y_1 - y_i) / (x_1 - x_i) pour i = [tous les points ne sont pas exclus]

De même trouvé k_a généralement par:

min (k_a-1 - (y_a-1 - y_i) / (x_a-1 - x_i)) pour i = [tous les points ne sont pas exclues]

Le calcul est fait pour la moitié supérieure du polygone jusqu'à ce que vous arriver au point qui est au maximum dans la direction x. Par la suite, le même algorithme de la moitié inférieure du polygone.

Figure 2. Algorithme pour le cas convexe.

Performance

La performance de l'algorithme dépend de combien de points qui finissent dans le polygone. Je fais linjärsök autant la liste qu'il pointe dans le polygone. Cela signifie que la complexité est en O (N * nombre de recherche). Le nombre de points dans le polygone optimale se situe entre 10 et 25 en fonction de vos points de chance. L'algorithme est donc relativement rapide.

Code

Le code n'est pas public.

Matlab solution - la coque convexe

Mon algorithme fait la même chose en fonction Matlab convhull . Convexe est donc le mot anglais pour un polygone fermé ou un corps convexe. Une autre bonne ressource est http://en.wikipedia.org/wiki/Convex_hull_algorithms expliquant que le temps théorique minimale pour trouver une coque convexe est de l'ordre (n log (n)) O.