实施宾利奥特曼算法 [英] Implementing the Bentley-Ottmann algorithm
问题描述
我有正确实施宾利奥特曼算法在C＃中一些麻烦。我想根据伪code rel="nofollow">来实现它。我已经发布低于我的主要code。假设我的 BST 和的PriorityQueue 类是正确实施，你看到的code什么问题？
有任何错误，但不是所有的交叉点被发现，只有一些。我的猜测是，有在的code（在当前情况下是一个交点）的其他部分错误。我不知道什么是伪code是指通过交换在BST两段的位置。就是这样，我这样做罚款？因为最终，两者没有真正交换在BST。我不能只改变它们的位置要么，因为这可能会破坏BST属性。
另外，我说的对的假设，段下令在BST由是 - 协调其左端点的？
我注意到，我似乎无法能够追踪到另一个错误是，有时点（0，0）进入 EVENTLIST 。 （0，0）是 Geometry.Intersects 输出的情况下，没有交集，但在这种情况下，如果的条件应该得到加阻止它。我不知道它是如何得到的，如果我打印 EVENTLIST 的内容添加一个点，（0，0）一直没有出现。如果我打印提取和弹出一个元素之后的内容，（0，0）有时会显示出来。可这有什么用 POP（）方法与参考搞乱，或者是它肯定在我的的PriorityQueue 的实施？
如果需要，我可以展示我实现了BST和优先级队列为好。
静态类BentleyOttman
{
私有静态无效AddIntersectionEvent（PriorityQueue中EVENTLIST，段塞格夫，段世嘉，SegPoint我）
{
i.IntersectingSegments =新行＆lt;段，段＆gt;（塞格夫，SEGA）;
i.Type = SegmentPointType.IntersectionPoint;
eventList.Add（ⅰ）;
}
公共静态无效的解决（面板表面，文本框调试）
{
debug.Clear（）;
VAR segList = Generator.SegList;
PriorityQueue中EVENTLIST =新的PriorityQueue（）;
的foreach（在segList段S）
{
eventList.Add（新SegPoint（SA，S，SegmentPointType.LeftEndpoint））;
eventList.Add（新SegPoint（SB，S，SegmentPointType.RightEndpoint））;
}
BST sweepLine =新BST（）;
而（！eventList.Empty）
{
SegPoint EV = eventList.Top（）;
eventList.Pop（）;
如果（ev.Type == SegmentPointType.LeftEndpoint）
{
段塞格夫= ev.Segment;
sweepLine.Insert（塞格夫）;
段SEGA = sweepLine.Inorder pre（塞格夫）;
段segB = sweepLine.InorderSuc（塞格夫）;
SegPoint I =新SegPoint（）;
如果（SEGA = NULL和放大器;！＆安培; Geometry.Intersects（塞格夫，世嘉，出i.Point））
{
AddIntersectionEvent（EVENTLIST，世嘉，塞格夫，我）;
}
如果（segB = NULL和放大器;！＆安培; Geometry.Intersects（塞格夫，segB，出i.Point））
{
AddIntersectionEvent（EVENTLIST，塞格夫，segB，我）;
}
}
否则，如果（ev.Type == SegmentPointType.RightEndpoint）
{
段塞格夫= ev.Segment;
段SEGA = sweepLine.Inorder pre（塞格夫）;
段segB = sweepLine.InorderSuc（塞格夫）;
sweepLine.Remove（塞格夫）;
SegPoint I =新SegPoint（）;
如果（SEGA = NULL和放大器;！＆安培; segB = NULL和放大器;！＆安培; Geometry.Intersects（SEGA，segB，出i.Point））
{
AddIntersectionEvent（EVENTLIST，世嘉，segB，我）;
}
}
其他
{
Generator.DrawPoint（ev.Point，面，Brushes.Red）;
段SEG1 = ev.IntersectingSegments.Item1;
段SEG2 = ev.IntersectingSegments.Item2;
sweepLine.Remove（SEG1）;
sweepLine.Remove（SEG2）;
片断t =新段（段1）;
SEG1 =新段（段2）;
SEG2 =新段（T）;
sweepLine.Insert（SEG1）;
sweepLine.Insert（SEG2）;
段SEGA = sweepLine.Inorder pre（SEG2）;
段segB = sweepLine.InorderSuc（SEG1）;
SegPoint I =新SegPoint（）;
如果（SEGA = NULL和放大器;！＆安培; Geometry.Intersects（SEG2，世嘉，出i.Point））
AddIntersectionEvent（EVENTLIST，世嘉，SEG2，我）;
如果（segB = NULL和放大器;！＆安培; Geometry.Intersects（SEG1，segB，出i.Point））
AddIntersectionEvent（EVENTLIST，SEG1，segB，我）;
}
}
}
}
我真的不明白，你的code无究竟是什么其他类的一些想法，但我可以回答你的一些其他问题。
该段被排列为BST由Y它们与扫描线交点坐标。因此，当我们遇到一个左端点我们使用的进入段的左端点的y坐标的段添加到树（它与Y比较其他段与扫描线的交叉点的坐标）。当我们遇到一个合适的终点，我们移除树段。当我们遇到的交点，则两个段与扫描线的交叉点的顺序切换，所以我们交换两个段在树中。例如，考虑两个部分
A = {（1,1），（1，-1）}和
B = {（1，-1），（1,1）}
当在X扫描线的坐标小于0，那么段A与扫描线的交叉点大于段B的与扫描线的交叉点。如果扫描线为大于0的情况正好相反。 （画图）。
有可能有益的绘制一个简单的例子，和跟踪正在发生的事情步步，绘制扫描线每个事件和事件之间标记的片段中的列，然后跟踪为BST的并验证BST保持相同的顺序在它是有效的区域中的段。 （对不起，如果不是明确的，因为它可能是。）
请注意：这里假设你的段中的基本立场，即，不段是垂直的，不超过两段相交于给定点等方面与段处理不是一般的位置列出在<一个HREF =http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm相对=nofollow>维基页面
I am having some trouble correctly implementing the Bentley-Ottmann algorithm in C#. I am trying to implement it according to the pseudocode here. I have posted my main code below. Assuming my BST and PriorityQueue classes are implemented correctly, do you see any problems with the code?
There are no errors, but not all intersection points are found, only some. My guess is that there's an error in the else part of the code (when the current event is an intersection point). I'm not sure what the pseudocode means by swapping the position of two segments in the BST. Is the way I do it fine? Because in the end, the two aren't really swapped in the BST. I can't just change their positions either, because that could break the BST properties.
Also, am I right in assuming that segments are ordered in the BST by the Y-coordinate of their left endpoint?
Another error I've noticed that I can't seem to be able to track down is that sometimes the point (0, 0) gets into eventList. (0, 0) is outputted by Geometry.Intersects in case there is no intersection, but in that case the if conditions should stop it from getting added. I have no idea how it gets in. If I print the contents of eventList after adding a point in, (0, 0) never shows up. If I print the contents after extracting and popping an element, (0, 0) sometimes shows up. Could this have anything to do with the Pop() method messing with the references, or is it definitely a problem in my PriorityQueue implementation?
If needed I can show my implementations for the BST and priority queue as well.
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);
}
}
}
}
I really cannot understand your code without some idea of what exactly the other classes do, but I can answer some of your other questions.
The segments are ordered in the BST by the Y coordinate of their intersection with the sweep line. So when we encounter a left endpoint we add the segment to the tree using the y coordinate of the left endpoint of the entering segment (comparing it with the Y coordinate of the intersection of the other segment with the sweep line). When we encounter a right endpoint we remove the segment from the tree. When we encounter an intersection, then the order of the intersections of the two segments with the sweep line switches, so we swap the two segments in the tree. For example consider the two segments
A = {(-1,1),(1,-1)} and
B = {(-1,-1),(1,1)}
When the X coordinate of the sweep line is less than 0 then the intersection of segment A with the sweep line is greater than the intersection of segment B with the sweep line. and if the sweep line is greater than 0 the reverse is true. (Draw a picture.)
It is probably instructive to draw a simple example, and trace what is going on step by step, drawing the sweep line for each event and labeling the segments in columns between the events, then keeping track of the BST and verifying that the BST keeps the same order as the segments in the region where it is valid. (I'm sorry if that is not as clear as it could be.)
Note: This assumes that your segments are in "general position", i.e. that no segment is vertical, no more than two segments intersect at a given point, etc. Dealing with segments not in general position is outlined on the wikipedia page
这篇关于实施宾利奥特曼算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
