CODEWITHSUNDEEP
algorithm
jedierikb
jedierikb

Reputation: 13079

list of neighboring points on a numberline of line segments?

I have a numberline, 1 to 100.

Within the extents of that numberline, I can add and remove many line-segments. These line-segments can intersect and overlap each other.

For a given x1 and x2, I need an efficient algorithm for iterating through all neighboring pairs of points (including x1 and x2) providing access to a list of all of the line-segments running between the neighboring points.

enter image description here

The results from this black numberline and the colored line-segments would be something like:

[0-20] -> []
[20-30] -> [red]
[30-40] -> [red, green]
[40-50] -> [green]
[50-60] -> []
[60-80] -> [purple]
[80-100] -> []

Upvotes: 4

Views: 166

Answers (2)

Penguino
Penguino

Reputation: 2176

Create a list of boundary records, where each boundary is of the form 

bound.type = start,finish
bound.position = 0..n
bound.color = red,green,blue...

and for each line segment add two such records to the list (ine for each end). Then sort all the records by position. Now if you iterate through the list as follows:

colors=[]
write '[0'
for each bound in list
  write '-',bound.pos,'] -> [',colours,']'
  if bound.type = start then 
    add bound.color to colors
  else
    remove bound.type from colors
  write '[',bound.pos
write '-',n'] -> []'

you will have to do a little tidying up if the first line segment starts at 0 or if the last one ends at n.

Upvotes: 0

chepner
chepner

Reputation: 531055

You want to use an interval tree.

Upvotes: 3

Related Questions