Introduction

This summer I'm working on a technology section in Västerås. I have worked at the same company and at roughly the same office for three straight summers. The work is very technical, fun and challenging. Unlike many other summer job in an office, I have found one where I have responsibility and get to work with common tasks. Specifically, I work on developing tools to simplify the computations using mostly MatLab, GUI programming and Java. The new object-oriented style of MatLab makes the code much more clear than a few years ago.

The problem

The other day I faced a small challenge. Simplified it focused on finding a polygon that encloses a set of complex points that are scattered in the plane. At first I did not find the function that does this in MatLab, which of course was very strange. I therefore decided to find a custom algorithm. In this post I will describe my algorithm.

Figure 1. Examples of convex shell.

My Alogritm

I describe my be algorithm using figure 2. To begin with, I will explain the difficulty in finding housing. The thing is that all points are unsorted in a structure. If the points are ordered around a center point, one can use their order and the distance from the center to solve the problem. However, it takes at least O (n log (n)) to make a linear sorting. My algorithm works in the unsorted list and will probably even more time, because I have not derived any evidence.

The idea is certainly to start with my point in the x direction and then find the point at which the k value becomes the maximum. ie figure out:

max (k_i) = (y_min - y_i) / (x_min - x_i) for i = [all items]. This gives you the point p_2.

All points of less than y value X_min may be omitted. All points with smaller x value than p_2 can also be ruled out for further reading.

k_2 is then found by finding the point which minimizes:

k_1 - (y_1 - y_i) / (x_1 - x_i) for i = [all the points are not excluded]

Similarly found k_a generally by:

min (k_a-1 - (y_a-1 - y_i) / (x_a-1 - x_i)) for i = [all the points are not excluded]

The calculation is done for the upper half of the polygon until you get to the point which is maximum in the x direction. Thereafter, the same algorithm to the lower half of the polygon.

Figure 2. Algorithm for the convex case.

Performance

The performance of the algorithm depends on how many points that end up in the polygon. I make as many linjärsök the list that it points in the polygon. This means that the complexity is O (N * number of search). The number of points in the optimal polygon is between 10 and 25 depending on your chance points. The algorithm is thus relatively fast.

Code

The code is not public.

Matlab solution - the convex hull

My algorithm does the same thing as a Matlab function convhull . Convex hull is thus the English word for an enclosed polygon or a convex body. Another good resource is http://en.wikipedia.org/wiki/Convex_hull_algorithms explaining that the theoretical minimum time to find a convex shell is of the order O (n log (n)).