Search code examples
algorithmcomputational-geometrypath-findingconvex-hull

Algorithm to order a set of points clockwise and make sure the path connecting the points is closed

I have been going about this problem in many different ways, and after a month of trying to do it on my own I think it is time for fresh eyes to take a look at it. I am trying to make an image scaling application for re-sizing 8-bit sprites and turning them into a vector images. So far, what I have working is this; it takes the image, breaks it up into shapes (areas with adjacent pixels of the same color) and then each pixel in the shape is replaced with four pixels:

private Point[] expand(int x, int y){
    x *= factor;
    y *= factor;
    return new Point[]{new Point(x+half_factor,y), new Point(x+factor,y+half_factor),
            new Point(x+half_factor, y+factor), new Point(x,y+half_factor)};
}

Each of the four points is placed into a 2D boolean array:

private void placePoint(int x, int y){
    table[x][y] = !table[x][y];
    extrema(x,y);
}

And the result for one individual shape looks like this:

enter image description here

Now I want to turn all of those points (minus the ones in the interior) into a polygon, and I have tried many different solutions, most recently I have been trying to find the nearest neighbor until it gets to the start, but each algorithm I try fails. For this particular example, it gets to the goomba in the lower right that is upside down and gets messed up in the cluster of pixels to its left. The program believes the path is done, and creates a line from there to the upper left corner, completely disregarding the points in the lower left quadrant.

enter image description here

This is what I want it to look like:

enter image description here

Here are a few things that are always true in my sitution that may help with finding an algorithm that works:

  1. The first point in the list of all points is a part of the outermost path
  2. Each point in the outermost path has a neighbor that is either C units away or the √C units away from it
  3. The outermost path will always be a closed path

Any help will be much appreciated!

UPDATE:

I have tried all of the solutions and suggestion below and have had a little progress, but still I am not getting the desired output.

ORIGINAL:

enter image description here

OUTPUT:

enter image description here

FINAL UPDATE:

It now works, just got to iron out the small bugs!

enter image description here

Solution

  • I would try with a modified version of the classical contour following algorithm. http://www.imageprocessingplace.com/downloads_V3/root_downloads/tutorials/contour_tracing_Abeer_George_Ghuneim/ray.html

    The modification consists in that horizontal/vertical moves are made with a two pixel step (instead of one in the standard version).

    To find all contours, scan the whole image until you meet a pixel on; follow that contour, switching off all its pixels. Then continue the scan where you left it.