4
C＃でBentley-Ottmannアルゴリズムを正しく実装するには問題があります。私は擬似コードhereに従って実装しようとしています。私は以下のメインコードを掲載しました。私のBSTとPriorityQueueクラスが正しく実装されているとすれば、コードに何か問題はありますか？Bentley-Ottmannアルゴリズムの実装
エラーはありませんが、すべての交差点が見つかったわけではなく、一部のみが見つかりました。私の推測では、コードの一部にエラーがあります（現在のイベントが交差点である場合）。私は、擬似コードがBSTの2つのセグメントの位置を入れ替えることによって何を意味するのかよく分かりません。私はそれをうまくやっているのですか？結局、2人はBSTで実際に交換されていないからです。 BSTのプロパティを破る可能性があるので、私は自分の位置を変えるだけではいけません。
また、左端の座標YによってセグメントがBSTで注文されたと仮定していますか？
私が追跡できないように思われる別のエラー(0, 0)がeventListに入ることがあることがあります。交点がない場合はGeometry.Intersectsによって(0, 0)が出力されますが、その場合は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);
}
}
}
}