用Lua语言实现的Bentley-Ottmann算法

2012-9-28 19:16:23
收藏：0
阅读：132
评论：1

我正在使用Lua实现Bentley-Ottmann算法，用伪代码在此处查找多边形中相交点。

我相对较新于实现算法，所以我无法理解其中的所有部分。 这是我迄今为止的代码：

我的多边形是使用此结构的表：{ { x = 1，y = 3 }，{ x = 5，y = 6 }，... }

如何确定“SL中segE上面的线段;”和“SL中segE下面的线段;”，如果扫描线（SL）为空该怎么办？插入I到X时，我应该用**endpoint ='intersect'**标记它并将其附加到末尾，这样当循环来到这个部分时，进入主循环的“else”语句，还是我整个算法都错了？

如果有人能给我一个用Python，Ruby等简单实现的链接，那就太完美了，因为我很难跟随伪代码并将其与C ++示例配对。

点赞
用户1161878
用户1161878

你的参考链接在我的位置无法打开。我将使用 维基百科文章 作为参考，因为它相当不错。

如何确定“在 SL 中 segE 上面的线段;” 和“在 SL 中 segE 下面的线段”？

该算法需要一个按 y 轴排序的当前扫描线 BST 来存放交点。 因此，上面的线段是 BST 中的后继节点，下面的线段是 BST 中的前驱节点。查找给定节点在 BST 中的前驱和后继是标准操作。 键 K 的前驱是 K 左边的最右边的节点。后继是 K 右边的最左边的节点。计算它们有几种方法。最简单的方法是使用父节点指针从 K 开始向上和向下遍历 BST。另一种方法是使用基于堆栈的迭代器。

如果扫描线（SL）为空怎么办？

继续处理事件队列。空的扫描线只是表示没有线段在其当前 x 坐标位置相交。

在将 I 插入 X 时，是否应将其标记为端点 = '交点' 并将其附加到末尾 ...？

事件队列必须按点的 x 坐标排序。当您插入一个交点时，它必须按照 x 坐标顺序排列。因为交点与端点不同，所以必须标记交点。当它是按照 x 坐标顺序的第一个剩余项时，它将按照需要进行处理。

请注意，Bentley Ottmann - 就像几乎所有几何算法一样 - 很容易受到浮点数不准确的影响。此外，该算法通常假定所有点都处于“一般位置”，因此忽略了所有垂直边缘、点-边重合、边缘重叠等问题。 我强烈建议使用有理算法，即使使用有理算法，要获得完全健壮，正确的实现也是一个重要的成就。 从免费实现的极少数可以看出这一点！

2013-01-25 00:02:47

作者:

用户1706325

用户1706325
推荐文章