我在matplotlib中绘制数据，用户可以通过套索与之交互，套索在内部表示为组成多边形链的顶点列表。我想做的是修剪套索，如这张非常专业的图片所示：
形式上，我有一个欧几里德平面上的顶点列表，我希望找到列表中不相邻的两个顶点，这样
它们在x和y方向上的差异都低于一个特定的阈值（我在图中看到1%的轴范围，在这里我是LasSoin）。
列表中位于它们之间的顶点的数量最大化。
如果没有这样的对，套索将被完全丢弃。
朴素的方法是O(n^2)，其中n是列表的长度：对于每个顶点ccc >，检查每对顶点恰好1 ≤ i ≤ n - 2索引分开，对于最高的i存在合适的对，选择找到的第一对。
这可能甚至是可以容忍的复杂性明智的，因为一些基本测试表明，拉索将很少超过500个顶点，超过大约1000可能完全排除。不过，在我看来，我应该能做得更好。
是否存在一个小于O（n ^ 2）的算法，如果存在的话，找到期望的对的索引？
最佳答案
可以测试线交点
这是O(n^2)幼稚的方法，如果你把线分割成片段，那么复杂度会变得更好。
Implementing Hoey Shamos algorithm with C#
对于这个和其他方法更好的复杂性，那么O(n^2)
你可以利用循环的周期性
闭合环类似于圆，所以x轴同样穿过两个点和y轴。所以记住通过所有的线开始x,y循环，当x或y接近起点（只有一个轴，而不是第一个展位），然后停止。
这是O(n)现在只需测试从起点到某个树顶距离的停车线和前进线的交叉点。如果没有找到交叉点，则再次使用另一个轴停止点。测试仍然是o（m^2），但这次m<<n
你可以整合这个角度
将中心计算为平均点，从起点开始循环穿过直线，然后计算其在套索圆（从中心）中的覆盖角，将其相加，得到某个变量，当达到360度时停止。从头到尾也一样。
现在你已经选择了环的内部部分，所以只测试从停止点到套索开始/停止的线
[Edit1]今天有点时间/心情，所以这里有更详细的子弹2
计算套索的包围盒
需要O(n)的min,max坐标让我们调用它们x,y这很容易通过x0<=x1,y0<=y1中的单for循环完成
按坐标分配和计算行计数器
如果将浮动坐标截断为某个网格/比例，则需要2个数组O(n)。不要忘记将值清除为零。对于套索的任何渲染int cntx[x1-x0+1],cnty[y1-y0+1]来说，计算都很容易。
递增计数器pixel(x,y)在端点上不递增（以避免重复递增）。这也是cntx[x-x0]++; cnty[y-y0]++;
从开始处查找每个坐标有两条以上直线的第一条直线
让它O(n)
在其后面找到下一行，该行的行数小于或等于每个坐标的行数2
让它i0
从末尾执行同样的操作并调用索引i1
找到交叉点
现在您需要检查j0,j1中任意一条线与<i0,i1>中任意一条线之间的交集这是<j0,j1>
这里有一个例子：
手绘套索在我的svg编辑器（不幸的是，不支持svg图像）在左侧，您可以看到蓝色的线（线计数>2），在两侧，有O(n^2)内容的图形。右边是红色的计算选择cntx,cnty。
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;
(i0,i1),(j0,j1)是保存每个顶点的laso坐标和标志的mine动态数组pnt[pnt.num]最后，
pnt[0]=x(0),pnt[1]=y(0),pnt[2]=flag(0),pnt[3]=x(1),...包含可修剪的点/线选择，因此它是至少有3条平行线存在的部分，并且从刚开始和结束时选择的平行线。希望现在足够清楚了。关于algorithm - 修剪包含闭环的套索，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30686055/