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

Question

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:

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.

This is what I want it to look like:

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:

OUTPUT:

FINAL UPDATE:

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

Answer 1

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.

Answer 2

At a high level,

1. Flood fill to find a connected set of pixels.
2. Apply the boundary operator to get an embedded planar graph.
3. Find the outer face.

Steps 2 and 3 are new. Step 2 is accomplished by putting two half-edges wherever a pixel in the set adjoins a pixel not in the set, one in each direction. For example,

***
* *
***
* *

turns into

._._._.
|* * *|
. ._. .
|*| |*|
. ._. .
|* * *|
. ._. .
|*| |*|
._. ._.

where each _ or | denotes two half-edges, one in each direction. For each point ., gather the half-edges directed toward it and make a pointer from each such half-edge to the next in counterclockwise order. Each half-edge should also point to the half-edge in the opposite direction.

Step 3 is accomplished by traversing as follows: given a half-edge, find the next half-edge in counterclockwise order directed toward the same point, and then find the half-edge opposite that half-edge, repeatedly. This will trace out one of the faces. If you want the outermost, start with the top boundary of a topmost pixel in the set.