Implementation of the Bentley-Ottman algorithm with AVL tree
I am having a problem implementing this method in java. I am specifically implementing the algorithm FINDINTERSECTIONS
in Computational Geometry 3rd Edition using the AVL BST tree for status. The description from the book is shown below:
The problem I am facing is doing step 5 in HANDLEEVENTPOINT
. When the event point is an intersection, the status is no longer fully ordered there because for the intersection lines, they intersect at the intersection and must be replaced in the status. Since the BST I am using is an AVLTree, the delete method fails because the rebalance method requires the correct ordering of the elements (i.e., the delete method assumes the tree is correctly ordered and performs rotations relative to the order to keep the log (n) height) ... Also, the status I am using stores data in nodes instead of leaves as shown in the picture. If I understand correctly, the book says that any tree can be used.
source to share
First, use a leafy version of a balanced tree binary search, be it red-black or AVL. I used red and black.
Get Peter Brass's book on Advanced Data Structures because you'll have trouble finding anything on these leafy trees in pretty much all standard algorithm / data structure books. I believe they are also called exogenous trees.
http://www-cs.engr.ccny.cuny.edu/~peter/
In addition, you can look at Algorithms and Data Structures: Basic Toolbox by Mehlhorn and Sanders, which is part of the Sorted Sequence data structure. They create them with only the leaves of the trees when the trees are used. These are also some of the people who developed LEDA.
Also take a look at the LEDA online bc book which has a chapter on how to implement this algorithm and how to handle ALL "problems". I think it's chapter 9 and it's a little tricky to follow, maybe because English is not the first language of the authors ... PITA !!
http://people.mpi-inf.mpg.de/~mehlhorn/LEDAbook.html
You can double-link leaf node data items together and you've created a sorted sequence with a tree as the navigation structure in the linked list of items. This is how LEDA thinks CGAL.
Duplicate items are handled differently in the event queue than the breakdown bar status structure. For an event queue, just add a linked list of items to the sheet (see Brass book). Here each sheet corresponds to an event point and has a list of all segments with a starting point, this is the same as the event point. Thus, some of them will have empty lists, such as event-intersection points and event-ending points. At least some implementations do this.
For a sweep state structure. Overlapping parallel segments are differentiated with segment IDs, for example. They don't talk about it in the book you are reading / linking to. However, the LEDA book tells you how to deal with them. Therefore, even though the sweep state metrics comparator says the two segments have the same endpoint and orientation, the comparator breaks up the link using the segment indices in the segment database, array, or whatever.
Some more important points:
Pool points! This common point pool is basic and then shards and is used in all data structures. Using a pool allows you to check for equality of points just by checking for identity! This avoids the use of a comparator, which slows down performance and can lead to errors.
The key point is that you avoid using tree comparators as much as possible.
When checking if the segments are in the same set or are members of three sets, you have a question (for example start, end or interesect and event point on the sweep line) DO NOT USE A COMPARATOR.
Instead, take advantage of the fact that segments belonging to the same set may have a specific "information property" in the list that indicates the event queue when the segment crosses the event point, or points to a successor item in the list if the segment overlaps the successor, or points to null otherwise. Thus, you will need cross-linking between an event queue with a sweepline status structure. Your kits and kits are very quick and easy to find. Go to the beginning or end of the linked list associated with the status tree and walk through item by item with a very simple test.
BOTTOM LINE. Get an ordered sequence / balanced binary tree data structure and work hard on it before implementing the rest of the Bentley-Ottmann.
This is indeed the key, and this book does not point to it at all, but unfortunately it is not, as this implementation is complex. Also note that the workbook expands the navigation tree with additional links in the internal tree nodes that point to related leaf nodes. It just makes searching a little faster, but it might not be clear if you're not familiar with tree leaves. A key in a leaf tree often appears twice, on a leaf node and elsewhere in the internal tree node of the tree.
FINALLY
Packages like LEDA / CGAL use precise arithmetic to make things work well. It took ten years for the LEDA developers to take ten years, and it was mainly due to the use of precise arithmetic. You may be fine with the basic cross-product test used for orientation, but if you want the exact version, you can find Professor Jonathan Shevchuk's exact arithmetic package on his website.
I think your book just left it all as a "reader / learner exercise". Lol.
source to share
UPDATE: In your published algorithm from this book, the swap for reversing the intersecting segment is done through deletion and then reinsertion. LEDA uses reverse_items () for these swaps. This is a more efficient way of committing subsequences of nodes and elements without using a comparator. Search for _rs_tree.c to see the LEDA source or look below.
// reverse a subsequence of items, assuming that all keys are
// in the correct order afterwards
//
void rs_tree::reverse_items( rst_item pl, rst_item pr )
{
int prio ;
register rst_item ppl = p_item(pl), // pred of pl
ppr = s_item(pr), // succ of pr
ql, qr ;
while( (pl!=pr) && (pl!=ppl) ) { // pl and pr didnt't
// met up to now
// swap all of pl and pr except the key
// swap parents
ql = parent(pl) ; qr = parent(pr) ;
if( pl==r_child(ql) )
r_child(ql) = pr ;
else
l_child(ql) = pr ;
if( pr==r_child(qr) )
r_child(qr) = pl ;
else
l_child(qr) = pl ;
parent(pl ) = qr ; parent(pr) = ql ;
// swap left children
ql = l_child(pl) ; qr = l_child(pr) ;
if( ql != qr ) { // at least one exists
l_child(pl) = qr ; parent(qr) = pl ;
l_child(pr) = ql ; parent(ql) = pr ;
}
// swap right children
ql = r_child(pl) ; qr = r_child(pr) ;
if( ql != qr ) { // at least one exists
r_child(pl) = qr ; parent(qr) = pl ;
r_child(pr) = ql ; parent(ql) = pr ;
}
// swap priorities
prio = pl->prio ; pl->prio = pr->prio ;
pr->prio = prio ;
// swap pred-succ-ptrs
s_item(ppl) = pr ; p_item(ppr) = pl ;
ql = pl ; pl = s_item(pl) ; // shift pl and pr
qr = pr ; pr = p_item(pr) ;
s_item(ql) = ppr ; p_item(qr) = ppl ;
ppl = qr ; ppr = ql ; // shift ppl and ppr
}
// correct "inner" pred-succ-ptrs
p_item(ppr) = pl ; s_item(ppl) = pr ;
if( pl==pr ) { // odd-length subseq.
p_item(pl) = ppl ; s_item(pr) = ppr ;
}
}
OPTIONAL: AVL trees, tree trees, red-black trees, markup trees, or skip lists can be used in sorted sequence data structures. The largest tree-to-tree matching used in LEDA ** was used by ab-tree with a = 2, b = 16.
** S. Naber. Comparison of data structures of the search tree in LEDA. Personal communication.
source to share