Lua中的宾利-奥特曼算法
我在Lua中实现了宾利-奥特曼算法，使用位于这里的伪代码在多边形中寻找相交点。
我对实现算法比较陌生，所以我无法理解其中的所有部分。到目前为止，这是我的代码：
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 }，…}
如何确定“ segE之上的段在SL;”和“在segE下面的段在SL;”，如果扫描线(SL)是空的，该怎么办？同样，在将I插入X中时，我是否应该用端点= 'intersect'标记它，并将其追加到末尾，以便当循环到这个部分时，进入主循环的“否则”语句，还是整个算法都弄错了？
这将是完美的，因为我发现很难遵循伪代码并将其与C++示例匹配，因此可以向我展示一个带有Python、Ruby等简单实现的链接。
回答 1
Stack Overflow用户
发布于 2013-01-25 00:02:47
从我的位置你的参考链接失败了。我将参考维基百科文章，这是相当不错的。
如何确定“SL中segE以上的段”和“SL中segE以下的段”；
该算法要求在y键上排序的当前扫描线交叉口需要一个BST，即垂直排列。所以上面的部分是BST的继承者，下面的是BST的前身。在BST中查找给定节点的前身和后继节点是一项标准工作。密钥K的前身是K的最右边节点，后继节点是K的最左边节点，K的最左边节点是K的右节点，计算方法有几种。最简单的方法是使用父指针来回遍历K中的树。另一种是基于堆栈的迭代器。
如果扫描线(SL)是空的，怎么办？
继续处理事件队列。空的扫描线只意味着在其当前的x位置没有任何段交叉。
同样，在将I插入X中时，我是否应该用端点= 'intersect‘标记它，并将其附加到末尾…？
事件队列必须在点的x坐标上保持排序。当你插入一个交集时，它也必须是x坐标顺序.必须将其标记为交点，因为交叉点的处理方式与端点不同。当它是x顺序的第一个剩余项时，它将在适当的时候被处理。
请注意，本特利奥特曼-几乎所有几何算法-是出了名的问题，因为浮点不准确的可怕的失败。此外，该算法通常是在“一般位置”假设下给出的，该假设允许所有垂直边缘、点边重合、边缘重叠等恶劣情况。我最强烈的建议是使用有理算法。即便如此，获得一个完全健壮、正确的实现也是一项重大成就。您可以通过非常少的免费实现来说明这一点！
https://stackoverflow.com/questions/12643305
复制相似问题
腾讯云开发者
