Inledning

I sommar jobbar jag på en teknikavdelning i Västerås. Jag har jobbat på samma företag och på ungefär samma kontor under tre raka somrar. Arbetet är väldigt tekniskt, roligt och utmanande. Till skillnad från många andra sommarjobb på kontor har jag hittat ett där jag får ansvar och får jobba med vanliga arbetsuppgifter. Konkret så jobbar jag med att utveckla verktyg för att förenkla beräkningsarbete med hjälp av till största delen MatLab, GUI-programmering och Java. Den nya objektorienterade stilen i MatLab gör koden betydligt mer tydlig än för några år sedan.

Problemet

Här om dagen ställdes jag inför en liten utmaning. Förenklat gick det ut på att hitta ett polygon som omsluter en samling med komplexa punkter som ligger spridda i planet. Till en början hittade jag inte funktionen som gör detta i MatLab, vilket förstås var konstigt. Jag bestämde mig därför för att hitta en egen algoritm. I detta inlägg skall jag beskriva min algoritm.

Figur 1. Exempel på konvext hölje.

Min Alogritm

Jag ska beskriva min algoritm med hjälp av figur 2. Till att börja med skall jag förklara svårigheten med att hitta höljet. Grejen är att alla punkter ligger osorterade i en struktur. Om punkterna sorteras kring en centrumpunkt kan man använda deras ordning och avståndet från centrum för att lösa problemet. Det tar dock minst O(n log(n)) att göra en linjär sortering. Min algoritm jobbar på den osorterade listan och tar säkert ännu mer tid; jag har inte härlett något bevis.

Tanken är i alla fall att börja med min punkten i x-led och därefter hitta den punkt till vilken k värdet blir maximalt. dvs räkna ut:

max(k_i) = (y_min – y_i)/(x_min – x_i) för i = [alla punkter]. Detta ger dig punkten p_2.

Alla punkter med mindre y-värde än X_min kan uteslutas. Alla punkter med mindre x-värde än p_2 kan också uteslutas för vidare genomläsning.

k_2 hittas sedan genom att hitta den punkt som minimerar:

k_1 – (y_1 – y_i)/(x_1 – x_i) för i = [alla icke uteslutna punkter]

På samma sätt hittas k_a generellt genom:

min(k_a-1 – (y_a-1 – y_i)/(x_a-1 – x_i)) för i = [alla icke uteslutna punkter]

Uträkningen görs för övre halvan av polygonen tills man kommer till punkten som är maximal i x-led. Därefter görs samma algoritm för den undre halvan av polygonen.

Figur 2. Algoritm för konvext hölje.

Prestanda

Prestandan av algoritmen beror på hur många punkter som hamnar i polygonet. Jag gör lika många linjärsök i listan som det blir punkter i polygonet. Det innebär att komplexiteten är O(N*antalet sök). Antalet punkter i det optimala polygonet blir mellan 10 och 25 beroende på dina slumppunkter. Algoritmen är alltså relativt snabb.

Kod

Koden är inte publik.

MatLabs lösning – convex hull

Min algoritm gör samma sak som MatLabs funktion convhull. Convex hull är alltså det Engelska ordet för en omslutande polygon eller ett konvext hölje. En annan bra resurs är http://en.wikipedia.org/wiki/Convex_hull_algorithms som förklarar att den teoretiska minimum tiden för att hitta ett konvext hölje är av storleksordningen O(n log(n)).