algorithm - Lua 中的 Bentley-Ottmann 算法

Question

我正在 Lua 中实现 Bentley-Ottmann 算法，使用位于 here 的伪代码在多边形中查找相交点.

我对实现算法还比较陌生，所以我无法理解它的所有部分。到目前为止，这是我的代码:

local function getPolygonIntersectingVertices( poly )
  -- initializing and sorting X
  local X = {}
  for i = 1, table.getn( poly ) do
    if i == 1 then
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'left' } )
    elseif i == table.getn( poly ) then
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'right' } )
    else
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'right' })
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'left' })
    end
  end

  local sortxy = function( a, b )
    if a.x < b.x then return true
    elseif a.x > b.x then return false
    elseif a.y <= b.y then return true
    else return false end
  end
  table.sort( X, sortxy )

  -- Main loop
  local SL = {}
  local L = {}
  local E
  local i = 1
  while next(X) ~= nil do
    E = { x = X[i].x, y = X[i].y, endpoint = X[i].endpoint }
    if E.endpoint == 'left' then
      -- left endpoint code here
    elseif E.endpoint == 'right' then
      -- right endpoint code here
    else
    end
    table.remove( X, i )
  end

  return L
end

我的多边形是一个使用这种结构的表格:{ { x = 1, y = 3 }, { x = 5, y = 6 }, ... }

如何确定“SL 中 segE 上方的段；”和“SL 中 segE 下方的段；”以及如果扫描线 (< strong>SL) 是空的？此外，当将 I 插入 X 时，我是否应该用 endpoint = 'intersect' 标记它并将其附加到末尾，以便当循环到达此部分时进入主循环的“else”语句或我的整个算法都错了吗？

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

Answer 1

您的引用链接在我的位置失败。我会引用 the Wikipedia article ，这是相当不错的。

How do I determine "the segment above segE in SL;" and "the segment below segE in SL;"

该算法需要一个 BST，用于当前扫描线交点，以 y 为关键字排序，即垂直排序。所以上面的部分是 BST 的后继者，下面的部分是 BST 的前身。在 BST 中查找给定节点的前驱和后继是标准操作。 key K 的前导是 K 左边最右边的节点。后继是 K 右边最左边的节点。有几种计算这些的方法。最简单的是使用父指针从 K 开始向上然后向下遍历树。基于堆栈的迭代器是另一种。

what to do if the sweep line (SL) is empty?

继续处理事件队列。空扫描线仅表示没有线段在其当前 x 位置交叉。

Also when inserting I into X, should I mark it with endpoint = 'intersect' and append it to the end ...?

事件队列必须保持按点的 x 坐标排序。插入交点时，它也必须按 x 坐标顺序。它必须标记为交叉点，因为交叉点的处理方式与端点不同。当它是 x 订单中第一个剩余的项目时，它将在适当的时候处理。

请注意，Bentley Ottman - 就像几乎所有几何算法一样 - 因浮点不准确而遭受可怕的失败而臭名昭著。此外，该算法通常给出一个“一般位置”假设，它排除了垂直边缘、点-边缘重合、边缘-边缘重叠等所有令人讨厌的情况。我最强烈的建议是使用有理算术。即便如此，获得完全健壮、正确的实现也是一项重大成就。您可以通过极少数的免费实现来证明这一点!