我正在 Lua 中实现 Bentley-Ottmann 算法，以使用位于此处的伪代码查找多边形中的交叉点。
我对实现算法比较陌生，所以我无法理解它的所有部分。到目前为止，这是我的代码：
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 下方的线段； ”以及如果扫描线 ( SL ) 为空怎么办？此外，当将 I 插入 X 时，我是否应该用endpoint = 'intersect'标记它并将其附加到末尾，以便当循环到达这部分时进入主循环的“else”语句，或者我已经得到了整个算法错误的？
如果有人可以向我展示一个带有 Python、Ruby 等简单实现的链接，那将是完美的，因为我发现很难遵循伪代码并将其与 C++ 示例相匹配。