实现Bentley-Ottmann算法

我在C＃中正确实现Bentley-Ottmann算法时遇到了一些麻烦。 我试图根据伪代码在这里实现它。 我在下面发布了我的主要代码。 假设我的BST和PriorityQueue类正确实现，您是否看到代码有任何问题？

没有错误，但并非找到所有交叉点，只有一些。 我的猜测是代码的else部分存在错误（当前事件是交叉点时）。 我不确定伪代码是什么意思通过交换BST中两个段的位置。 我这样做的方式很好吗？ 因为最终，两者在BST中并没有真正交换。 我也不能改变他们的立场，因为这可能打破BST属性。

另外，我是否正确地假设它们的左端点的Y坐标在BST中排序？

我注意到我无法追踪的另一个错误是有时点(0, 0)进入eventList 。 (0, 0)由Geometry.Intersects输出，以防没有交集，但在这种情况下， if条件应该阻止它被添加。 我不知道它是如何进入的。如果我在添加一个点后打印eventList的内容， (0, 0)永远不会显示。 如果我在提取并弹出元素后打印内容(0, 0)有时会显示(0, 0) 。 这可能与Pop()方法搞乱引用有关，还是我的PriorityQueue实现中肯定是一个问题？

如果需要，我也可以显示我的BST和优先级队列的实现。

 static class BentleyOttman { private static void AddIntersectionEvent(PriorityQueue eventList, Segment segEv, Segment segA, SegPoint i) { i.IntersectingSegments = new Tuple(segEv, segA); i.Type = SegmentPointType.IntersectionPoint; eventList.Add(i); } public static void Solve(Panel surface, TextBox debug) { debug.Clear(); var segList = Generator.SegList; PriorityQueue eventList = new PriorityQueue(); foreach (Segment s in segList) { eventList.Add(new SegPoint(sA, s, SegmentPointType.LeftEndpoint)); eventList.Add(new SegPoint(sB, s, SegmentPointType.RightEndpoint)); } BST sweepLine = new BST(); while (!eventList.Empty) { SegPoint ev = eventList.Top(); eventList.Pop(); if (ev.Type == SegmentPointType.LeftEndpoint) { Segment segEv = ev.Segment; sweepLine.Insert(segEv); Segment segA = sweepLine.InorderPre(segEv); Segment segB = sweepLine.InorderSuc(segEv); SegPoint i = new SegPoint(); if (segA != null && Geometry.Intersects(segEv, segA, out i.Point)) { AddIntersectionEvent(eventList, segA, segEv, i); } if (segB != null && Geometry.Intersects(segEv, segB, out i.Point)) { AddIntersectionEvent(eventList, segEv, segB, i); } } else if (ev.Type == SegmentPointType.RightEndpoint) { Segment segEv = ev.Segment; Segment segA = sweepLine.InorderPre(segEv); Segment segB = sweepLine.InorderSuc(segEv); sweepLine.Remove(segEv); SegPoint i = new SegPoint(); if (segA != null && segB != null && Geometry.Intersects(segA, segB, out i.Point)) { AddIntersectionEvent(eventList, segA, segB, i); } } else { Generator.DrawPoint(ev.Point, surface, Brushes.Red); Segment seg1 = ev.IntersectingSegments.Item1; Segment seg2 = ev.IntersectingSegments.Item2; sweepLine.Remove(seg1); sweepLine.Remove(seg2); Segment t = new Segment(seg1); seg1 = new Segment(seg2); seg2 = new Segment(t); sweepLine.Insert(seg1); sweepLine.Insert(seg2); Segment segA = sweepLine.InorderPre(seg2); Segment segB = sweepLine.InorderSuc(seg1); SegPoint i = new SegPoint(); if (segA != null && Geometry.Intersects(seg2, segA, out i.Point)) AddIntersectionEvent(eventList, segA, seg2, i); if (segB != null && Geometry.Intersects(seg1, segB, out i.Point)) AddIntersectionEvent(eventList, seg1, segB, i); } } } } 

Answer 1

我真的无法理解你的代码而不知道其他类究竟做了什么，但我可以回答你的其他一些问题。

这些段在BST中按其与扫描线的交点的Y坐标排序。 因此，当我们遇到左端点时，我们使用输入段的左端点的y坐标将该段添加到树中（将其与另一个段与扫描线的交点的Y坐标进行比较）。 当我们遇到正确的端点时，我们从树中删除该段。 当我们遇到一个交叉点时，那么两个段与扫描线的交点的顺序会切换，所以我们交换了树中的两个段。 例如，考虑两个部分

  A = {(-1,1),(1,-1)} and B = {(-1,-1),(1,1)} 

当扫描线的X坐标小于0时，段A与扫描线的交点大于段B与扫描线的交点。 如果扫描线大于0，则反之亦然。 （画一张图。）

绘制一个简单的示例并逐步跟踪正在进行的操作，绘制每个事件的扫描线并在事件之间的列中标记段，然后跟踪BST并validationBST保持BST，这可能是有益的。与有效区域中的段相同的顺序。 （如果不是那么清楚，我很抱歉。）

注意：这假设您的片段处于“一般位置”，即没有片段是垂直的，在给定点处不超过两个片段相交，等等。 维基百科页面上列出了处理不在一般位置的片段