Order points from array based on 8-connectivity (Moore neighborhood)

Questions & Answers
1

Well, I’m working with pixels right now in Unity… I was wondering if anyone could help me with this.

For example, I created an image like this:

And now I store every black pixel in a List<Point> like this:

//Think that I can get all pixels as an Color[,] array (actually, I can)

List<Point> points = new List<Point>();

for(int i = 0; i < width; ++i)
	for(int j = 0; j < height; ++j)
		if(colorMap[i, j] == Color.black)
			points.Add(new Point(i, j));

Now I have stored all the points in a List, but with the problem that they are ordered as the image was looped out. So, now I have the question, how can I order it?

I have tried something like that:

public Shape SortDistance()
{
        List<Point> vlist = vertices.ToList(), //Get all the vertices in a list
                    orderedList = new List<Point>(); //This will be the final list
        Point fp = vlist.Find(x => x == position), //Get the first pixel that was detected before... (This is )
              curPos = fp;
        int maxLoops = vertices.Length * 10, //I tried to avoid freezes without luck
            lp = 0;
        while(vlist.Count > 0 && lp < maxLoops)
        {
            var clockwiseDirs = new Point[] { Point.upperLeft, Point.up, Point.upperRight, Point.right, Point.downRight, Point.down, Point.downLeft, Point.left }; //8-connectivity array

            List<Point>[] neighs = new [] { new List<Point>(), new List<Point>() }; //This is a little bit confusimg, but here, the only trhing I do, is store in the first array the 4-connectivity (up, left, bottom and right) points and in the seconds the corners
            foreach (Point p in clockwiseDirs)
            {
                int j = p.x,
                    k = p.y;
                if (j != 0 && k != 0)
                { //If this position isn't the center...
                    Point nPoint = vertices.FirstOrDefault(x => x == curPos + new Point(j, k)); //Check if there is any pixel, if not return null
                    if (nPoint == null || nPoint == Point.zero)
                        continue; //And skip...
                    List<Point> mergedNeighs = neighs[0].Union(neighs[1]).ToList(); //If yes, merge the two arrays
                    if (!mergedNeighs.Contains(nPoint)) //Only for check if this points wasn't already added
                        if ((nPoint - curPos).sqrMagnitude == 1)
                            neighs[0].Add(nPoint); //If the distance is 1 it means that the position is top or left or bottom or right...
                        else if ((nPoint - curPos).sqrMagnitude == 2)
                            neighs[1].Add(nPoint); //If it's 2, it means the corners 
                }
            }

            bool n1 = neighs[0].Count > 0, //Sides
                 n2 = neighs[1].Count > 0; //Corners

            if (n1 || n2)
            { //If it has neighbors
                List<Point> mergedNeighs = n1 && n2 ? neighs[0].Union(neighs[1]).ToList() : neighs[n1 && !n2 ? 0 : 1]; //There we have to sleect what we want, depending on the neighbors found before
                foreach (Point ne in mergedNeighs) //Now we loop over them
                { //Comprobamos cada uno de los vecinos
                    List<Point> fPoints = new List<Point>();
                    if (!orderedList.Contains(ne)) //Check if the final list doesn't has this point
                        fPoints.Add(ne);
                    if (fPoints.Count == 1)
                    { //If there is only one neighbor
                        orderedList.Add(fPoints[0]); //Add it to the fional list
                        vlist.Remove(curPos); //Delete it from the other list
                        curPos = fPoints[0]; //And set the new pos to revise
                    }
                    else
                    { //If there are several neighbors
                        Point np = fPoints.FirstOrDefault(x => x.sqrMagnitude == 1); //We select the nearest one
                        foreach(Point vp in fPoints)
                            orderedList.Add(vp); //They are orderer, so we have to add them
                        vlist.Remove(curPos);
                        curPos = np;
                    }
                }
            }
            else //If the pixel is alone remove it, impossible case??
                vlist.Remove(curPos);
            ++lp;
        }
        if (lp > vertices.Length * 5)
            Debug.Log("Mmmm..."); //If this goes up something is going wrong, but I have noticed it because my pc freezes
        vertices = orderedList.ToArray();
        return this;
}

I’m aware this is better to be in Code Review, but I don’t know, I have to optimize it, but first fix it, because I think that the while freezes, but I have small RAM size and a lot of “Shapes” to check, so I cannot know exactly where it fails, because, my PC freezes.

One option could be to make a coroutine, but my problem there is that my script is a messm and If I do this I could cause a null object reference.

If anyone could help me I would be so happy! Thanks in advance.

2

Your shape is a concave shape so using the angle to some sort of center point won’t work. That only works for convex shapes.

Your problem can be solved easier when you work directly on the grid. Do you really need all pixels or is it enough to get the boundary pixels? Because keeping those extra pixels just creates ambiguity where the path continues.

So there are two solutions depending on if you want all pixels or the boundary pixels:

Getting the boundary pixels is the easiest and most straight forward. You simply pick a point that is for sure on the outer boundary. If you simply scan the image row by row the first pixel you find does met that criteria.

Now you simply go ahead in the same direction on the x axis. You know that in the row below the current is empty since in the current row you found the first pixel. So the pixel you’ve found is one of the lowest one on the y axis. (just in case you didn’t know, images are stored left to right and bottem to top. So the first pixel is the bottom left pixel in an image).

For this algorithm you have to store / carry over to the next step:

  • the current position
  • the current direction.

The direction can be an enum / int with 8 values or a direction vector. The logic is now this:

  • Check the pixel that is 90° clockwise from the current direction.
  • If there is a pixel, store it and set the new direction to this direction
  • if there is no pixel rotate the direction 45° counter clockwise until you find a pixel
  • repeat

Note that if the shape is a closed shape you should end at the starting pixel. Though it’s possible in some cases that you get stuck somewhere. If might be a good idea to build in some safe-guards. Either remember which pixels you already processed and terminate when you reach the same pixel again, or simply restrict the amount of iterations. (you never need more iterations than there are pixels in the image ^^).

The resulting list is already sorted since you walked the boundary in counter clockwise order.

If you want to process those extra pixels as well it get’s a bit more complicated. You can use the same procedure as above, but in addition each step you would also check the “next” 45° rotation and if there’s a pixel you add it in between the current and the last.

So it’s basically like this:

  • Check the pixel that is 90° clockwise from the current direction.
  • If there is a pixel, check 45° counter clockwise and if there is another pixel add this first. Now add the current pixel
  • if there is no pixel rotate the direction 45° counter clockwise.
  • repeat

Note that this will also only process a “connected” path. If there are additional pixels inside the path that aren’t part of the outer path, they will be ignored.

If you plan to have multiply pathes in one image it can get tricky. The easiest solution is as you process the pixels you actually remove them from the image data. So once one path is done you can simply continue the search for the first pixel from the last starting position. A safe way to remove a completed path would be to iterate through the path and remove the 9 pixel area around each path point. This ensures everything that belongs to this path is gone.

I haven’t tested this approach but it should work as described. The “rotation” can be easily done with adding / subtracting from the int / enum and wrap the value properly, or when using a direction vector by some simply vector math. Rotating a 2d vector by 90° you simply flip x and y and invert one of them. Depending which one you invert it’s +90° or -90°. 45° can be easily done by adding the current vector and the 90° rotated version together and “normalize” the vector. “normalize” here means ensure each component is either -1, 0 or 1. So a 45° vector would be (1, 1) so it can be used as offset into the image grid.

edit
In case you don’t know what boundary pixels i mean, see this image:

85521-boundarypixels.png