CODEWITHSUNDEEP
algorithmdata-structurestreecomputational-geometryavl-tree
user3521250
user3521250

Reputation: 115

Finding the neighbours of a segment (Bentley-Ottmann algorithm )

I'm implementing the Bentley-Ottmann algorithm to find the set of segment intersection points,
unfortunately I didn't understand some things.

a segment tree, the segments and the sweep line it represents

For example :

I'm using a balanced binary search tree for the sweepLine status, but we store the segments in the leaves, after reading this wikipedia article I didn't find an explanation for this operation.

From the reference book (de Berg & al.: "Computational Geometry", ill. at p.25):

Suppose we search in T for the segment immediately to the left of some point p that lies on the sweep line. At each internal node v we test whether p lies left or right of the segment stored at v. Depending on the outcome we descend to the left or right subtree of v, eventually ending up in a leaf. Either this leaf, or the leaf immediately to the left of it, stores the segment we are searching for.

For my example if I follow this I will arrive at the leaf Sj but I will know just the leaf to the left i.e. Sk, how can I get Si?

Edit I found this discussion that looks like my problem, unfortunately there are no answers about how can I implement some operations in such data structure.

The operation are:

I know how to implement these operations in a balanced binary search tree when we store data too in internal node, but with this type of AVL I don't know if it is the same thing.

Thank you

Upvotes: 3

Views: 1111

Answers (2)

learning_cpp
learning_cpp

Reputation: 19

Same as you, I have met the same problem while reading the de Berg & al.: "Computational Geometry". But I think The C++ Standard Template Library (STL) have an implantation called "map" which can do the job.

You just need to define some personalized class for line segment and event points and their comparison functions. Then, use std::map to build the tree and access the neighboring element using map.find() to get and iterator, and use iterator to gain access to the two neighbor element.

Upvotes: 0

Derlin
Derlin

Reputation: 9881

I stumbled upon the same problem when reading Computational Geometry from DeBerg (see p. 25 for the quote and the image). My understanding is the following:

say you need the right neighbor of a segment S which is in the tree. If you store data in the nodes, the pseudo code is:

locate node S
if S has a right subtree:
   return the left-most node of the right subtree of S
else if S is in the left sub-tree of any ancestor:
   return the lowest/nearest such ancestor
else
   return not found

If you store the data in the leaves, the pseudo-code becomes:

let p the point of S currently on the sweep line
let n the segment at the root of the tree

while n != null && n is not a leaf:
   if n = S:
     n = right child of S
   else:
     determine if p is on the right or left of n
     update n accordingly (normal descent)

In the end, either n is null and it means there is no right neighbor, or n points to the proper leaf.

The same logic applies for the left neighbor.

Upvotes: 0

Related Questions