3

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 :

  • how can I get the neighbours of the segment Sj in the image.

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:

  • inserting a node in such data structure.
  • deleting a node.
  • swapping two nodes.
  • searching for neighbours' node.

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

Community
  • 1
  • 1
user3521250
  • 115
  • 3
  • 14
  • Is your question how to find the (left) neighbour of a leaf in an arbitrary binary tree? Or is the question why the quoted algorithm returns the "correct" result? – H W Apr 14 '15 at 13:32
  • my question is how to find the left and the right neighbor of a node in a balanced binary search tree, and not any binary tree , there is some standard algorithm to find the predecessor and the successor of a node , but i don't know if it's suitable for the sweep line algorithm – user3521250 Apr 14 '15 at 14:11
  • Finding the neighbours in a balanced binary search tree doesn't differ from not (necessarily) balanced, let alone between applications. (If it wasn't a search tree, I wanted a definition of `predecessor` and `successor`.) – greybeard Apr 14 '15 at 15:38

2 Answers2

0

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.

Derlin
  • 9,572
  • 2
  • 32
  • 53
0

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.

learning_cpp
  • 19
  • 5