4
我在C＃中正确实现Bentley-Ottmann算法时遇到了一些麻烦。我试图按照伪代码here来实现它。我在下面发布了我的主代码。假设我的BST和PriorityQueue类正确实现，您是否看到任何代码问题？实现Bentley-Ottmann算法
没有错误，但并不是所有的交点都被找到了，只有一些。我的猜测是代码中的else部分存在错误（当前事件是交叉点时）。我不确定通过交换BST中两个段的位置，伪代码意味着什么。我做得很好吗？因为最后，这两个在BST中并没有真正交换。我不能只是改变他们的立场，因为这可能会破坏BST的特性。
另外，我是否正确地假设段在BST中由Y - 它们的左端点的坐标？
我注意到，我似乎无法追查的另一个错误是，有时点(0, 0)进入eventList。如果没有交集，(0, 0)由Geometry.Intersects输出，但在这种情况下if条件应该阻止它被添加。我不知道它是如何进入的。如果在添加点后打印eventList的内容，(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<Segment, Segment>(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(s.A, s, SegmentPointType.LeftEndpoint));
eventList.Add(new SegPoint(s.B, 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);
}
}
}
}