How do I sort a 2d array that stores xy coordinates in clock wise in python?

Question

From an array with consisted with ones and zeros, I'm trying to get the boundary of that array and plot it. This is the code that I used to get the boundary

import numpy as np
import math
import matplotlib.pyplot as plt


binI = np.array([[0,0,0,0,1,0,0,0,0,0,0],
                 [0,0,0,1,1,1,1,0,0,0,0],
                 [0,0,1,1,1,1,1,0,0,0,0],
                 [0,1,1,1,1,0,0,0,0,0,0],
                 [0,1,1,1,0,0,0,0,0,0,0],
                 [0,0,1,1,1,1,0,0,0,0,0],
                 [0,0,0,1,1,1,0,0,0,0,0],
                 [0,0,0,1,1,0,0,0,0,0,0]])


def boundary_Tracer(arr):
    indices_list = []
    for i in range (np.shape(arr)[0]):
        for j in range (np.shape(arr)[1]):
            if arr[i,j] == 1:
                if i == 0 and j == 0:
                    if (arr[i+1,j] == 0) or (arr[i,j+1] == 0):
                        indices_list.append([i,j])
                elif (i == 0) and (j == np.shape(arr)[1]-1):
                    if (arr[i,j-1] == 0) or (arr[i+1,j] == 0):
                        indices_list.append([i,j])
                elif (i == (np.shape(arr)[0]-1)) and j == 0:
                    if (arr[i-1,j] == 0) or (arr[i,j+1] == 0):
                        indices_list.append([i,j])
                elif (i == np.shape(arr)[0]-1) and (j == np.shape(arr)[1]-1):
                    if (arr[i-1,j] == 0) or (arr[i,j-1] == 0):
                        indices_list.append([i,j])
                elif (i in range (1,np.shape(arr)[0]-1)) and (j == 0):
                    if (arr[i-1,j] == 0) or (arr[i,j+1] == 0) or (arr[i+1,j] == 0):
                        indices_list.append([i,j])
                elif (i in range (1,np.shape(arr)[0]-1)) and (j == np.shape(arr)[1]-1):
                    if (arr[i-1,j] == 0) or (arr[i,j-1] == 0) or (arr[i+1,j] == 0):
                        indices_list.append([i,j])
                elif (i == 0) and (j in range (1,np.shape(arr)[1]-1)):
                    if (arr[i,j-1] == 0) or (arr[i,j+1] == 0) or (arr[i+1,j] == 0):
                        indices_list.append([i,j])          
                elif (i == np.shape(arr)[0]-1) and (j in range (1,np.shape(arr)[1]-1)):
                    if (arr[i-1,j] == 0) or (arr[i,j-1] == 0) or (arr[i,j+1] == 0):
                        indices_list.append([i,j])
                else:
                    if (arr[i-1,j] == 0) or (arr[i+1,j] == 0) or (arr[i,j-1] == 0) or (arr[i,j+1] == 0):
                        indices_list.append([i,j])
                
    indicies_array = np.array(indices_list)
    x_all = indicies_array[:,1]
    x_init_bw = np.min(np.where(x_all == np.min(x_all)))
    origin = np.reshape(indicies_array[x_init_bw,:],(1,2))[0]
    indicies_array = np.vstack((indicies_array,origin))
    
    return indicies_array, origin

bw = boundary_Tracer(binI)[0]
origin = boundary_Tracer(binI)[1]

plt.plot(bw[:,1],bw[:,0])
plt.gca().invert_yaxis()

I know it's ugly and I'm sure there is a better way to do it but this was my best. Anyways, when I plot this, the plot zigzags between the points. I would like to have the plot just connect the boundaries without crossing over the middle of the area that is marked with 1.

What would be the best way to rearrange array with the xy coordinates of the boundaries (which is bw)?

After some research I found an explanation why this is [not possible](https://scicomp.stackexchange.com/a/31076) with the set of points and no further information. I hope my answer can help in some way. — Michael Szczesny, Sep 07 '21 at 23:15

Michael Szczesny · Answer 1 · 2021-09-08T00:27:58.337

1

You can translate your data to the origin and use the complex angle to sort your data

bw = boundary_Tracer(binI)[0]
origin = boundary_Tracer(binI)[1]

xs = (bw - bw.mean(0))
x_sort = bw[np.angle((xs[:,0] + 1j*xs[:,1])).argsort()]

# Plot to test your trace
plt.imshow(binI, cmap='gray')
plt.plot(x_sort[:,1],x_sort[:,0])
plt.gca().invert_yaxis()
plt.axis('off');

Output

This clockwise solution is not the desired result. Points that are not on the convex hull are sorted in the wrong place.

One usable sorting to prove the problem is not in your data would be for example

x_sort = bw[[18,  7,  4,  1,  0,  2,  3,  6,  5,  8, 10, 12, 13, 15, 17, 16, 14, 11,  9]]
plt.imshow(binI, cmap='gray')
plt.plot(x_sort[:,1],x_sort[:,0], 'ro--')
plt.gca().invert_yaxis()
plt.axis('off');

Output

There are algorithms for 'star shaped' non convex shapes but no general unique solution without further information.

edited Sep 08 '21 at 00:27

answered Sep 07 '21 at 21:32

Michael Szczesny

4,911
5
15
32

I love how you sorted using np.angle. I actually tries this it seems like it works fairly good but the line still penetrates the inside instead of only drawing the boundaries. For example, point (5,1) should be connected to (0,4) and (6,1) but it seems like your answer connects it with (0,4) and (4,3). Do you think there is a way to arrange the points so the plot only draws the boundaries without crossing over the inside? – color_blue Sep 07 '21 at 21:44
1

Just a note that this method only works for convex polygons. The shape in the example is concave which presents two problems: 1) the centroid isn't guaranteed to be within the bounds of the polygon; 2) the "angular value" of points along the perimeter may not increase monotonically, meaning that sorting them will put them "out of order". – Woodford Sep 07 '21 at 21:53

How do I sort a 2d array that stores xy coordinates in clock wise in python?

1 Answers1