Bentley-Ottman Algorithm in Lua

Question

I am implementing the Bentley-Ottman algorithm in Lua to find intersecting points in a polygon using the pseudocode located here .

I am relatively new to the implementation of algorithms, so I could not understand all its parts. Here is my code:

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 ax < bx then return true elseif ax > bx then return false elseif ay <= by 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 

My polygon is a table using this structure: {{x = 1, y = 3}, {x = 5, y = 6}, ...}

How to define "a segment above segE in SL; " and "a segment below segE in SL; " and what if the scan line ( SL ) is empty? In addition, when I insert into X, should I mark it with endpoint = 'intersect' and attach it to the end, so when the loop falls into this part, it goes to the “else” statement of the main loop or Do I have the wrong algorithm?

It would be great if someone could show me a link with a simple implementation in Python, Ruby, etc., since it is difficult for me to follow the pseudocode and match it with a C ++ example.

Answer 1

There is no link failure with my link. I will describe a Wikipedia article which is good enough.

How to define "segment above segE in SL"; and "segment below segE in SL;"

The algorithm requires BST for current intersections of scan lines sorted by key y, that is, vertically. Thus, the segment above is the successor to BST, and the one below is the predecessor of BST. Finding the predecessor and successor of a given node in BST is standard material. The predecessor of the K key is the rightmost node to the left of K. The successor is the leftmost node to the right of K. There are several ways to calculate them. The simplest is to use parent pointers to jump back and then down the tree from K. The stack-based iterator is different.

What if the scan line (SL) is empty?

Continue to process the event queue. An empty scan line means that no segments intersect at their current location x.

Also, when I insert into X, I should mark it with the end point = 'intersect' and add it to the end ...?

The event queue must be sorted by the x-coordinate of the points. When you insert an intersection, it should also be in x-coordinate order. It must be marked as an intersection because intersections are handled differently than endpoints. It will be processed over time when it becomes the first remaining element in x order.

Please note that Bentley Ottman - just like almost all geometric algorithms - is known to suffer terrifying failures due to inaccuracies with floating point. In addition, the algorithm is usually given with the assumption of a "general position", which allows you to identify all the unpleasant cases of vertical edges, the coincidence of points and edges, etc. My strongest recommendation is to use rational arithmetic. Even then, obtaining a fully reliable and correct implementation is a significant achievement. You can say this with very few free implementations!