Trim lasso that contains closed loop

Question

I'm plotting data in matplotlib that the user can interact with via a lasso, which is internally represented as a list of vertices that make up a polygonal chain. What I would like to be able to do is to trim lassos as illustrated in this highly professional picture:

Formally, I have a list of vertices in the Euclidean plane, and I would like to find two vertices that are not adjacent in the list such that

• their difference in both x and y direction is each below a certain threshold (I was thinking 1% of the axis range visible in the the figure where I'm lassoing)

• the number of vertices lying between them in the list is maximized

If no such pair exists, the lasso will be discarded altogether.

The naive approach is O(n^2), where n is the length of the list: for each number of vertices 1 ≤ i ≤ n - 2, check each pair of vertices exactly i indices apart, and for the highest i where a suitable pair exists, select the first pair that is found.

That might even be tolerable complexity-wise since some basic tests showed that the lassos will rarely exceed 500 vertices, and more than roughly 1000 can probably be ruled out altogether. Still, it seems to me I should be able to do better than this.

Is there an algorithm that runs in less than O(n^2) and finds the indices of the desired pair, if it exists?

Answer 1

1. you can test for line intersections

   this is O(n^2) with naive approach if you segmentate the lines into segments then the complexity became much better see

   • Implementing Hoey Shamos algorithm with C#

   for this and other approaches in better complexities then O(n^2)

2. you can exploit periodicity of loop

   closed loop is similar to circle so the x axis goes through the same point twice and the y axis too. So remember starting x,y loop through all lines and when x or y gets near the starting point (just single axis not booth whichever first) then stop.

   This is O(n) now just test for intersection around the line you stop and forward from start point up to some treshold distance. If no intersection found do this again with the other axis stop point. The test is still O(m^2) but this time m<<n

3. you can integrate the angle

   compute center as average point O(n) now loop through lines from start and compute angle its covering in a lasso circle (from center) add it up to some variable and when reach 360 degrees stop. Do the same from end.

   Now you have selected the inner part of the loop so test only lines from the stop points to start/stop of lasso

   

[edit1] had a bit time/mood today for this so here is the bullet 2 in more detail

1. compute bounding box of lasso

   need min,max of x,y coordinates let call them x0<=x1,y0<=y1 this is done easy by single for loop in O(n)

2. allocate and compute line counters per coordinate

   you need 2 arrays int cntx[x1-x0+1],cnty[y1-y0+1] if you have floating coordinates truncate to some grid/scale. Do not forget to clear the values to zero. The computation is easy for any rendered pixel(x,y) of the lasso.

   Increment counter cntx[x-x0]++; cnty[y-y0]++; do not increment on endpoint (to avoid duplicate increments). This is also O(n)

3. find first line from start that has more than 2 lines per coordinate

   let it be i0

4. find next line after it that has less or equal lines then 2 per coordinate

   let it be i1

5. do the same from end and call the indexes j0,j1

6. find the intersection

   now you need to check just intersection between any line from <i0,i1> against any line from <j0,j1> this is O(n^2)

Here an example:

hand drawed lasso in mine svg editor (sadly SO does not support svg images). On left side you see blue lines (lines count > 2) and on sides there is graphs for cntx,cnty contents. The right side is computed selection (i0,i1),(j0,j1) in red

Some source code in C++:

int i,i0,i1,j0,j1;
int a,x,y,x0,y0,x1,y1;
int *cntx,*cnty;
List<int> pnt;  // laso points (x,y,flag)

// bounding box O(n) and reset flags
x=pnt[0]; x0=x; x1=x;
y=pnt[1]; y0=y; y1=y;
for (i=0;i<pnt.num;)
    {
    x=pnt[i]; i++;
    y=pnt[i]; i++;
    pnt[i]=0; i++;
    if (x0>x) x0=x;
    if (x1<x) x1=x;
    if (y0>y) y0=y;
    if (y1<y) y1=y;
    }
// allocate and compute counter buffers (count how many line at x or y coordinate)
cntx=new int[x1-x0+1];
cnty=new int[y1-y0+1];
for (x=x0;x<=x1;x++) cntx[x-x0]=0;
for (y=y0;y<=y1;y++) cnty[y-y0]=0;
x=pnt[0];
y=pnt[1];
for (i=0;i<pnt.num;)
    {
    a=pnt[i]; i++;
    for (;x<a;x++) cntx[x-x0]++;
    for (;x>a;x--) cntx[x-x0]++; x=a;
    a=pnt[i]; i++; i++;
    for (;y<a;y++) cnty[y-y0]++;
    for (;y>a;y--) cnty[y-y0]++; y=a;
    }
// select sections with 3 lines (trimable)
for (i=0;i<pnt.num;)
    {
    x=pnt[i]; i++;
    y=pnt[i]; i++;
    if ((cntx[x-x0]>2)||(cnty[y-y0]>2)) pnt[i]=1; i++;
    }
// select trim areas from start (i0,i1) and from end (j0,j1)
for (i=0      ;i<pnt.num;) { i0=i; i++; i++; a=pnt[i]; i++; if ( a) break; }
for (         ;i<pnt.num;) { i1=i; i++; i++; a=pnt[i]; i++; if (!a) break; }
for (i=pnt.num;i>0      ;) { i--; a=pnt[i]; i--; i--; j1=i; if ( a) break; }
for (         ;i>0      ;) { i--; a=pnt[i]; i--; i--; j0=i; if (!a) break; }
delete[] cntx;
delete[] cnty;

• pnt[pnt.num] is mine dynamic array holding the laso coordinates and flags for each vertex

• pnt[0]=x(0),pnt[1]=y(0),pnt[2]=flag(0),pnt[3]=x(1),...

  at the end the i0,i1,j0,j1 contains the trimable point/lines selection so it is part where at least 3 parallel lines exist and from that selected just first from start and end. Hope it is clear enough now.