I am having some problems with the correct implementation of the Bentley-Ottman algorithm in C #. I am trying to implement it according to the pseudo code here . I have posted my main code below. Assuming that my classes BSTand PriorityQueueimplemented correctly, you see any problem with the code?
There are no errors, but not all intersection points were found, only some. I suppose elsethere is an error in the code part (when the current event is the intersection point). I'm not sure what pseudo code means by replacing the position of two segments in a BST. Am I doing this so well? Because, in the end, the two did not switch places in the BST. I can’t just change my position because it can violate the properties of BST.
Also, do I correctly assume that the segments are ordered in BST using the- Ycoordinate of their left endpoint?
Another mistake that I noticed that I can’t keep track of is that sometimes the point (0, 0)falls into eventList. (0, 0)is output Geometry.Intersectsif there is no intersection, but in this case the conditions ifshould prevent it from getting an addition. I have no idea how this happens. If I print the contents eventListafter adding a dot, it (0, 0)never appears. If I print out the contents after retrieving and popping the item, it sometimes appears (0, 0). Could this have anything to do with the method Pop()using the references, or is this definitely a problem in my implementation PriorityQueue?
If necessary, I can show my implementations for the BST and priority queue.
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);
}
}
}
}