Geek Answers Handbook

List of neighboring points on a linear line?

I have a line number, from 1 to 100.

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

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

enter image description here

The results of this black line and color line segments will be as follows:

[0-20] -> [] [20-30] -> [red] [30-40] -> [red, green] [40-50] -> [green] [50-60] -> [] [60-80] -> [purple] [80-100] -> []
+4
source share
2 answers

You want to use the interval tree.

+3
source

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

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

and for each line segment add two such entries to the list (ine for each end). Then sort all the records by position. Now, if you iterate over 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 tidy up a bit if the first line segment starts at 0 or the last ends at n.

0
source

More articles:


All Articles