Coordinates Python

Question

I am facing with the sorting airfoil coordinates. In particular given a set of coordinates, which are not sorted, I have to sorted them starting from the trailing edge upper surface. Here I report the code that I have developed but as you can see, the starting point do not match with what I suppose, moreover exist several oscillations as you can see in the reported figure (and a detail, in blue the starting point after the sort). Can someone suggest me what I miss? How can I do?

Thanks you in advance.

def sort_airfoil(points):



            x0 = np.mean(-points[:,1])

            y0 = np.mean(points[:,2])           

            r = np.sqrt((-points[:,1]-x0)**2 + (points[:,2]-y0)**2)
            
            tempx=-points[:,1]

            xmax=np.max(tempx)

            ind_max=np.where(tempx==xmax)

            ymax=np.max(points[ind_max,2])
            
            ind_max_t=np.where((tempx>0.95*xmax) & (tempx<xmax))
            
            ymax_t=points[ind_max_t,2]
            
            ymin=np.min(ymax_t)
            
            indx_temp=np.where(points[:,2]==ymin)
            
            xmin=np.max(tempx[indx_temp])
            
            xmed=(xmin+xmax)/2
            ymed=(ymin+ymax)/2
            
            print(x0,y0)
            print(xmin,ymin)
            
            print((xmin+xmax)/2, (ymin+ymax)/2)

            
            angle0=np.arctan2((ymed-y0),(xmed-x0))
            
            print("angle", angle0)

            angles = np.where((points[:,2]-y0) > 0, np.arccos((-points[:,1]-x0)/r), 2*np.pi-np.arccos((-points[:,1]-x0)/r))

            angles=angles-angle0

            for i in range(len(angles)):

                if angles[i]<0:

                    angles[i]=angles[i]+2*np.pi
                elif angles[i]>2*np.pi:
                    angles[i]=angles[i]-2*np.pi



            mask = np.argsort(angles)          

            x_sorted = points[mask,1]

            y_sorted = points[mask,2]         

            points_new=np.zeros([len(points), 3])


            points_new[:,0]=points[:,0]

            points_new[:,1]=x_sorted

            points_new[:,2]=y_sorted


            return points_new   

Answer 1

The issue comes from the algorithm itself: it only work when the points form a convex polygon. However, the shape is concave.

More specifically, the first sorted points (and the last ones) form a zigzag-shaped lines because there is two sets of points (green arrows) interleaving with growing angles (red arrow) from the median point (red line).

Note the points are horizontally flipped on the gathered point from the question. Thus the points are sorted clockwise.

One simple solution is to split horizontally the shape in many set of point (eg. 10 set) so that each set form a convex shape. Then, the parts can be merged to form the final shape. The merge consists in finding the points at the "edge" of each locally-sorted set of points (parts) and reorder the partially sorted array of points consequently.

More specifically, the points of each part are split in 2 sub-sets: the upper ones and the lower ones. You can find them easily by selecting the 2 left-most points of a right part with the right-most points of a left part. The 2 top-most points needs to be connected each other and the same for the 2 bottom-most points. Thus, the sequence of the two upper sets of points needs to be reordered so they are contiguous and the same for the lower part.

Here is an example:

Note that if you are unsure about how to split the points in many parts so that each one form a convex-shaped sets of points, then you can: split the shape in n parts, check if the set of points form a convex shape by computing a convex hull (eg. using a Graham scan) and split evenly the parts that are concave (recursively). This is quite expensive, but more robust.