Rearranging a 2D point set to enclose the set with a line

Share icon

Hello all,

I am out of ideas and would appreciate any help. I have several sets of xy coords that form an approximately elliptical border (they are locations of a segmented region of an image). When I pulled them from the image they were arranged in a vertically ascending order. I'd like to rearrange them into a clockwise (or anti-clockwise) order so that the points form a border around the ellipse, like in the original image. Does anyone have an idea how to do this? I am attaching a picture of the plot as it stands. Essentially, I want to get rid of the zig-zag pattern.

Unfortunately, the order is not alternating (it looks like it from the image) so re-arranging it that way doesn't work. I've tried that!
One idea:

Find the center (average x and y) and then calculate the angle from the center to the point and then sort the wave based on the angle.

Andy

June 27, 2017 at 08:02 am - Permalink

Another alternative would be to do an implicit fit to the ellipse data, as discussed on p.698 of the IP7 manual "Example: fit to an ellipse". You will have to add an extra variable for the ellipse rotation angle, as well as the center coordinates. The resulting best-fit parameters will smooth out your apparent edge irregularities.

I think you will also have to make your own ellipse 'x' and 'y' waves from the best-fit parameters, because the automatically created waves will follow the original sorting irregularity.

June 27, 2017 at 08:40 am - Permalink

AG,

It seems to me that ConvexHull might miss some end points that are close to the boundary, but slightly concave. Your help file example show at least one point illustrating such behavior. Stephen's data show other such potential problem points. Perhaps that is not an issue for him.

June 27, 2017 at 10:54 am - Permalink

s.r.chinn wrote:
AG,

It seems to me that ConvexHull might miss some end points that are close to the boundary, but slightly concave. Your help file example show at least one point illustrating such behavior. Stephen's data show other such potential problem points. Perhaps that is not an issue for him.


If any point goes missing, one can use the convex hull path and solve for the shortest distance from the missing points to the hull path. The intersection with the hull-path would determine the order of the point in the sequence.

June 27, 2017 at 12:22 pm - Permalink

Hi,

I have another idea. It may not be too elegant but gave me the possibility to test my understanding of conditional operators. It expects the non-ordered coordinates in two waves and gives the ordered coordinates in two new waves (x_oval and y_oval).
I have tested it only with one hand-drawn example. It could give problems when two or more points lie exactly on a horizontal or vertical line.

I hope it helps.

Greetings, Klaus

#pragma TextEncoding = "Windows-1252"
#pragma rtGlobals=3     // Use modern global access method and strict wave access.
 
function oval(xp, yp)
    wave xp, yp
    variable x1, y1, x2, y2, x3, y3, x4, y4
 
    wavestats/q xp
    x1 = v_min
    y1= yp[V_minloc]
 
    x3 = V_max
    y3 = yp[V_maxloc]
 
    wavestats/q yp
    x2 = xp[V_maxloc]
    y2 = v_max
 
    x4 = xp[V_minloc]
    y4 = V_min
 
    duplicate /o xp x1p, x2p, x3p, x4p
    duplicate /o yp y1p, y2p, y3p, y4p
 
    x1p = (x1 <= xp[p] && xp[p] < x2) && (y1 <= yp[p] && yp[p] < y2) ? xp[p] : NaN
    y1p = (x1 <= xp[p] && xp[p] < x2) && (y1 <= yp[p] && yp[p] < y2) ? yp[p] : NaN
    WaveTransform zapnans x1p
    WaveTransform zapnans y1p
    sort x1p, x1p, y1p
 
    x2p = (x2 <= xp[p] && xp[p] < x3) && (y2 >= yp[p] && yp[p] > y3) ? xp[p] : NaN
    y2p = (x2 <= xp[p] && xp[p] < x3) && (y2 >= yp[p] && yp[p] > y3) ? yp[p] : NaN
    WaveTransform zapnans x2p
    WaveTransform zapnans y2p
    sort x2p, x2p, y2p
 
    x3p = (x3 >= xp[p] && xp[p] > x4) && (y3 >= yp[p] && yp[p] > y4) ? xp[p] : NaN
    y3p = (x3 >= xp[p] && xp[p] > x4) && (y3 >= yp[p] && yp[p] > y4) ? yp[p] : NaN
    WaveTransform zapnans x3p
    WaveTransform zapnans y3p
    sort /r x3p, x3p, y3p
 
    x4p = (x4 >= xp[p] && xp[p] > x1) && (y4 <= yp[p] && yp[p] < y1) ? xp[p] : NaN
    y4p = (x4 >= xp[p] && xp[p] > x1) && (y4 <= yp[p] && yp[p] < y1) ? yp[p] : NaN
    WaveTransform zapnans x4p
    WaveTransform zapnans y4p
    sort /r x4p, x4p, y4p
 
    Concatenate /O /NP /KILL {x1p,x2p,x3p,x4p}, x_oval
    Concatenate /O /NP /KILL {y1p,y2p,y3p,y4p}, y_oval
 
end

June 27, 2017 at 01:12 pm - Permalink

_sk wrote:
Can you post a sample set of xy coords?

best,
_sk


Yes. Here is one 2D wave, column 0 is x and column 1 is y.
16_00285_a_m_r.ibw (1.3 KB)

June 27, 2017 at 11:22 pm - Permalink

s.r.chinn wrote:
Another alternative would be to do an implicit fit to the ellipse data, as discussed on p.698 of the IP7 manual "Example: fit to an ellipse". You will have to add an extra variable for the ellipse rotation angle, as well as the center coordinates. The resulting best-fit parameters will smooth out your apparent edge irregularities.

I think you will also have to make your own ellipse 'x' and 'y' waves from the best-fit parameters, because the automatically created waves will follow the original sorting irregularity.


Thank you. Yes, I have already been down this path. Actually these final point sets have been centred at the origin and rotated so that the semimajor axis along x at y=0 and semiminor is along y at x=0 so the fit is similar to the example in the manual. The problem is that I want the plots to look like the real data and not a fit to it.

June 27, 2017 at 11:26 pm - Permalink

Igor wrote:
s.r.chinn wrote:
AG,

It seems to me that ConvexHull might miss some end points that are close to the boundary, but slightly concave. Your help file example show at least one point illustrating such behavior. Stephen's data show other such potential problem points. Perhaps that is not an issue for him.


If any point goes missing, one can use the convex hull path and solve for the shortest distance from the missing points to the hull path. The intersection with the hull-path would determine the order of the point in the sequence.


Thank you for the suggestion. Yes, I'd like all points recovered and this put me off convex hull. I like this idea of recovering the other points and hadn't thought of that as a solution when fitting a convex hull for other problems - I had investigated "alpha shapes" as a solution and not got very far with that.

June 27, 2017 at 11:31 pm - Permalink

Klaus wrote:
Hi,

I have another idea. It may not be too elegant but gave me the possibility to test my understanding of conditional operators. It expects the non-ordered coordinates in two waves and gives the ordered coordinates in two new waves (x_oval and y_oval).
I have tested it only with one hand-drawn example. It could give problems when two or more points lie exactly on a horizontal or vertical line.

I hope it helps.

Greetings, Klaus


Hi Klaus,
Thank you for your answer and your code! I just tried one point set. It **nearly** worked for my data (see attached pic). From the original image I do have several consecutive horizontal and vertical values because they are pixel locations. However, because of the rotation I thought that these values would no longer be horizontal or vertical, so it should work. I'll investigate a bit more. Thank you.
Screen Shot 2017-06-28 at 07.32.35.png (77.09 KB)

June 27, 2017 at 11:40 pm - Permalink

Thanks to everybody for the suggestions.
Andy's idea worked and my code is below in case it is useful for anyone. Note that the points are centred at the origin and atan2 is used to get unique values for theta round one rotation.
I pass the 2-column wave to this as part of a larger stack.

/// @param  m1  2D wave with 1st two columns as XY coords
Function Threader(m1)
    Wave m1
    
    String mName = NameOfWave(m1)
    MatrixOp/O c0 = col(m1,0)
    MatrixOp/O c1 = col(m1,1)
    Variable nRows = DimSize(m1,0)
    Make/O/FREE/N=(nRows) threadW=0
    // measure angles, store in threadW
    Variable theta
    
    Variable i
    
    for(i = 0; i < nRows; i += 1)
        theta = atan2(c1[i],c0[i])
        threadW[i] = theta
    endfor
    
    // sort x coords and ycoords based on theta
    Sort threadW, c0, c1
    // add last point equal to first to complete the shape
    InsertPoints nRows,1, c0,c1
    c0[nRows] = c0[0]
    c1[nRows] = c1[0]
    // put back together and overwrite original
    Concatenate/O/KILL {c0,c1}, $mName
End

June 28, 2017 at 12:35 am - Permalink