我正在使用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上面的线段”和“segE下面的线段”，如果扫描线（SL）为空怎么办？此外，在将I插入X时，应该用endpoint = 'intersect'标记它并将其附加到末尾，以便当循环到达此部分时进入主循环的“else”语句，还是我的整个算法都错了？
如果有人能向我展示一个Python、Ruby等简单实现的链接，那就太棒了，因为我发现很难跟随伪代码并将其与C++示例匹配。
sortxy函数中缺少then，同一函数中缺少end，使用不存在的运算符!=而不是~=）。在寻求帮助之前，你应该先学习一些 Lua 的知识。 - prapintable.getn早已被弃用。 - Alexander Gladysh