Eva*_*ons 3 c# algorithm arcgis shapefile polygons
我最初实现了Hoey-Shamos算法,但它对于将来的可维护性来说太复杂了(我在这里没有说法),并且没有正确报告,因此我将使用优化的强力算法.
我的问题是:如何优化此代码才能使用？
就目前而言,我的代码包含一个嵌套的for循环,两次迭代相同的列表.
编辑:将线条转换为HashSet并使用两个foreach循环...扫描10,000个约45秒.这还不够.
foreach (Line2D g in lines)
{
foreach (Line2D h in lines)
{
if (g.intersectsLine(h))
{
return false;
}
}
} // end 'lines' for each loop
如果我强制我的"intersectsLine()"方法返回false(出于测试目的),扫描10,000条记录仍然需要8秒(我有700,000条记录).这太长了,所以我需要优化这段代码.
我尝试在将其与所有其他线路进行比较后从列表中删除线路,但是存在准确性问题(不明白为什么)并且速度增加几乎不可察觉.
这是我的intersectsLine方法.我在这里找到了另一种方法,但看起来所有的方法调用和诸如此类的东西都会变慢.在我看来,计算坡度似乎并不需要太多计算(如果我错了,请纠正我？)
public bool intersectsLine(Line2D comparedLine)
{
//tweakLine(comparedLine);
if (this.Equals(comparedLine) ||
P2.Equals(comparedLine.P1) ||
P1.Equals(comparedLine.P2))
{
return false;
}
double firstLineSlopeX, firstLineSlopeY, secondLineSlopeX, secondLineSlopeY;
firstLineSlopeX = X2 - X1;
firstLineSlopeY = Y2 - Y1;
secondLineSlopeX = comparedLine.X2 - comparedLine.X1;
secondLineSlopeY = comparedLine.Y2 - comparedLine.Y1;
double s, t;
s = (-firstLineSlopeY * (X1 - comparedLine.X1) + firstLineSlopeX * (Y1 - comparedLine.Y1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
t = (secondLineSlopeX * (Y1 - comparedLine.Y1) - secondLineSlopeY * (X1 - comparedLine.X1)) / (-secondLineSlopeX * firstLineSlopeY + firstLineSlopeX * secondLineSlopeY);
if (s >= 0 && s <= 1 && t >= 0 && t <= 1)
{
//console.WriteLine("s = {0}, t = {1}", s, t);
//console.WriteLine("this: " + this);
//console.WriteLine("other: " + comparedLine);
return true;
}
return false; // No collision */
}
编辑:主要的瓶颈是大多边形!我排除了运行超过100行的多边形,它在5:10中运行了所有700,000多个多边形.哪个在可接受的范围内!当然有一种方法可以在运行此代码之前查看多边形是否值得计算？如果有帮助,我可以访问XMin,Xmax,YMin和YMax属性吗？
进行另一项测试,将多边形限制在1000行以下.花了一个多小时.
我删除了多边形的所有限制,它现在已经运行了36个小时......仍然没有结果.
我有几个想法:
- 当我生成我的行hashset时,让另一个hashset/List具有候选交集.如果有交叉的机会,我只会在此列表中添加行.但是如何消除/增加可能性？如果只有三条线可能与其他线相交,我将比较4000线而不是4000线.仅此一点就可以产生巨大的差异.
- 如果相同的点出现两次,除了第一个和最后一个点,省略运行嵌套的for循环.
编辑:
有关多边形的信息:总计700,000
有超过四千个多边形,分数为1,000或更多
有2个多边形,有70,000或更多点
我认为有可能通过一点创造力将其降低到十五分钟左右.
您当前的Brute-Force算法是O(n ^ 2).对于你的两个70,000个线多边形来说,这几乎是100亿次操作的因素,更不用说700,000个其他多边形了.显然,没有多少纯粹的代码优化就足够了,所以你需要一些可以降低O(n ^ 2)而不会过度复杂的算法优化.
O(n ^ 2)来自蛮力算法中的嵌套循环,每个循环都受到限制n,使其成为O(n*n).最简单的方法是找到一些方法来减少内部循环,使其不受约束或依赖n.因此,我们需要找到的是一些方法来订购或重新排序内部行列表以检查外部线,以便只需要扫描完整列表的一部分.
我采用的方法利用了如果两个线段相交的事实,那么它们的X值的范围必须彼此重叠.你要知道,这并不意味着他们不相交,但如果他们的X范围没有重叠,那么他们可以不被交叉所以世界上没有其他需要检查他们反目成仇.(Y值范围也是如此,但您一次只能利用一个维度).
这种方法的优点是这些X范围可用于对线的端点进行排序,这些端点又可以用作起点和终点,以检查线的交叉点.
具体而言,我们所做的是定义一个自定义类(endpointEntry),它表示该行的两个点的高或低X值.这些端点都放在相同的List结构中,然后根据它们的X值进行排序.
然后我们实现一个外部循环,我们扫描整个列表就像在暴力算法中一样.然而,我们的内循环是相当不同的.我们不是重新扫描整个列表中的行以检查交集,而是从外部循环线的高X值端点开始扫描排序的端点列表,并在我们通过同一行的低X值端点下方时结束它.这样,我们只检查X值范围与外环线重叠的线.
好的,这是ac#class演示我的方法:
class CheckPolygon2
{
// internal supporting classes
class endpointEntry
{
public double XValue;
public bool isHi;
public Line2D line;
public double hi;
public double lo;
public endpointEntry fLink;
public endpointEntry bLink;
}
class endpointSorter : IComparer<endpointEntry>
{
public int Compare(endpointEntry c1, endpointEntry c2)
{
// sort values on XValue, descending
if (c1.XValue > c2.XValue) { return -1; }
else if (c1.XValue < c2.XValue) { return 1; }
else // must be equal, make sure hi's sort before lo's
if (c1.isHi && !c2.isHi) { return -1; }
else if (!c1.isHi && c2.isHi) { return 1; }
else { return 0; }
}
}
public bool CheckForCrossing(List<Line2D> lines)
{
List<endpointEntry> pts = new List<endpointEntry>(2 * lines.Count);
// Make endpoint objects from the lines so that we can sort all of the
// lines endpoints.
foreach (Line2D lin in lines)
{
// make the endpoint objects for this line
endpointEntry hi, lo;
if (lin.P1.X < lin.P2.X)
{
hi = new endpointEntry() { XValue = lin.P2.X, isHi = true, line = lin, hi = lin.P2.X, lo = lin.P1.X };
lo = new endpointEntry() { XValue = lin.P1.X, isHi = false, line = lin, hi = lin.P1.X, lo = lin.P2.X };
}
else
{
hi = new endpointEntry() { XValue = lin.P1.X, isHi = true, line = lin, hi = lin.P1.X, lo = lin.P2.X };
lo = new endpointEntry() { XValue = lin.P2.X, isHi = false, line = lin, hi = lin.P2.X, lo = lin.P1.X };
}
// add them to the sort-list
pts.Add(hi);
pts.Add(lo);
}
// sort the list
pts.Sort(new endpointSorter());
// sort the endpoint forward and backward links
endpointEntry prev = null;
foreach (endpointEntry pt in pts)
{
if (prev != null)
{
pt.bLink = prev;
prev.fLink = pt;
}
prev = pt;
}
// NOW, we are ready to look for intersecting lines
foreach (endpointEntry pt in pts)
{
// for every Hi endpoint ...
if (pt.isHi)
{
// check every other line whose X-range is either wholly
// contained within our own, or that overlaps the high
// part of ours. The other two cases of overlap (overlaps
// our low end, or wholly contains us) is covered by hi
// points above that scan down to check us.
// scan down for each lo-endpoint below us checking each's
// line for intersection until we pass our own lo-X value
for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)
{
// is this a lo-endpoint?
if (!pLo.isHi)
{
// check its line for intersection
if (pt.line.intersectsLine(pLo.line))
return true;
}
}
}
}
return false;
}
}
我不确定这个算法的真正执行复杂性是什么,但我怀疑对于大多数非病理多边形,它将接近O(n*SQRT(n)),这应该足够快.
Inner Loop只是以与外部循环相同的排序顺序扫描endPoints列表.但是,这将开始从那里从其中外循环是目前在列表中(这是一些线的HIX点),和外回路将仅扫描,直到终点值下降到低于该同一行的相应LOX值扫描.
这里有些棘手的问题是,使用Enumerator(foreach(..in pts)外部循环)无法做到这一点,因为无法枚举列表的子列表,也无法根据另一个枚举当前位置启动枚举.所以我所做的就是使用前向和后向链接(fLink和bLink)属性来创建一个双向链表结构,该结构保留列表的排序顺序,但是我可以在不枚举列表的情况下逐步扫描:
for (endpointEntry pLo = pt.fLink; (pLo != null) && (pLo.XValue >= pt.lo); pLo = pLo.fLink)
打破这种情况,旧式for循环说明符有三个部分:初始化,条件和递增 - 递减.初始化表达式,使用列表中当前点的前向链接进行endpointEntry pLo = pt.fLink;初始化pLo.也就是说,列表中的下一个点,按降序排序.
然后执行内循环的主体.然后pLo = pLo.fLink应用递增 - 递减,它pLo使用它的forward-link(pLo.fLink)简单地将内部循环的当前point()设置为下一个较低点,从而推进循环.
最后,它在测试循环条件后(pLo != null) && (pLo.XValue >= pt.lo)循环,只要新点不为空(这意味着我们位于列表的末尾)并且只要新点XValue仍然大于或等于外环当前点的低X值.第二个条件确保内部循环仅查看与外部循环端点的线重叠的线.
现在更清楚的是,通过将endPoints List视为一个数组,我可能已经解决了整个fLink-bLink的笨拙:
i)而不是foreach枚举器j),从i下面传递开始和结束pt.Lo.我认为这会简单得多.如果你愿意,我可以发布这样的简化版本.
| 归档时间： |
|
| 查看次数： |
2678 次 |
| 最近记录： |