Python program to detect intersection of one-dimensional line segments

Question

I have line segments of four colors—pink, green, orange, red—as in the figure below.

As an example, the first pink segment has start and end position (5258,5422).

The coordinates are stored in this dictionary of tuples:

mycoord = { 'pink'  :[(5258,5422), (5479,5864)],
            'green' :[(5425,5450)],
            'orange':[(5266,5770)],
            'red'   :[(5258,5864)] }

What I want to do is to get all the possible intersections' start and end values as shown in this figure:

Thus, the desired answer would be:

sect1/pink-red        : 5258,5266
sect2/pink-orange-red : 5266,5422
sect3/orange-red      : 5422,5425
sect4/green-orange-red: 5425,5450
sect5/orange-red      : 5450,5479
sect6/pink-orange-red : 5479,5770
sect7/pink-red        : 5770,5864

Note that I want to preserve the color indicator for each intersection (e.g., pink-red). How can I achieve this with Python?

Answer 1

Using the brace open/close idea of Michael Laszlo above:

>>> mycoord = { 'pink'  :[(5258,5422), (5479,5864)],
            'green' :[(5425,5450)],
            'orange':[(5266,5770)],
            'red'   :[(5258,5864)] }
>>> labeled_values=[]
# make tuples of (value, brace status (open/close), color)
>>> for color,color_ranges in mycoord.items():
        for color_range in color_ranges:
            labeled_values.append((color_range[0],True,color))
            labeled_values.append((color_range[1],False,color))

    # labeled_values are now like (5258, True, 'pink'), (5422, False, 'pink') ...
>>> sects = []
# traverse the sorted values and maintain a color-set
>>> color_set_so_far=set()
>>> range_start = -1
>>> for value,range_open,color in sorted(labeled_values):   
        if not range_open or range_start != value:
            sects.append(("-".join(color_set_so_far), range_start, value))

        if range_open:          
            color_set_so_far.add(color)
        else:       
            color_set_so_far.remove(color)      

        range_start = value

>>> sects = [s for s in sects if s[0] and s[1]!=s[2]] # filter out empty ranges
>>> sects
# [('pink-red', 5258, 5266), ('pink-orange-red', 5266, 5422), ('orange-red', 5422, 5425), ('orange-green-red', 5425, 5450), ('orange-red', 5450, 5479), ('pink-orange-red', 5479, 5770), ('pink-red', 5770, 5864)]

Answer 2

I suggest that you proceed as follows.

• Sort the endpoints, remembering each one's color and whether it's a left (opening) or right (closing) endpoint.

• Iterate over the endpoints, keeping track of open spans with a hash that maps each color to the number of open spans of that color. Increment when you open a span of a given color, decrement when you close a span. Remove colors when their count reaches zero. For each distinct endpoint, put the colors of all open spans at that point into a set.

• Iterate over consecutive pairs of distinct endpoints. These form the left and right endpoints of the spans that interest you. For each endpoint, you know the colors that are active at that point. The set of colors that are active during the span is the set intersection of the colors that are active at the left end and the colors that are active at the right end.

Note: If the intersection of colors between two endpoints is empty, you've found a gap between spans, so you know that it should be skipped. You might also like to skip spans with only one color. The implementation below does not. You can easily change it to skip single-color spans by modifying this line:

  if len(colors) > 0:

so that it reads:

  if len(colors) > 1:

If you're interested in seeing the gaps between spans, you can change the threshold to -1 or remove the condition altogether.

Implementation:

mycoord = { 'pink'  :[(5258,5422), (5479,5864)],
            'green' :[(5425,5450)],
            'orange':[(5266,5770)],
            'red'   :[(5258,5864)] }

# Sort the endpoints. Remember their color and whether they open or close.
points = []
for color, spans in mycoord.items():
  for open, close in spans:
    points.append((open, 'open', color))
    points.append((close, 'close', color))
points.sort()

# Iterate over the endpoints. Keep track of open spans. Mark intersections.
active_spans = {}
intersections = []
for point, kind, color in points:
  if len(intersections) != 0 and intersections[-1][0] == point:
    intersections[-1][1].add(color)
  else:
    color_set = set([color] + list(active_spans.keys()))
    intersections.append((point, color_set))
  if kind == 'close':
    active_spans[color] -= 1
    if active_spans[color] == 0:
      del active_spans[color]
  else:
    active_spans[color] = active_spans.setdefault(color, 0) + 1

# Iterate over consecutive pairs of unique intersections. Intersect the color sets.
tab_width = sum(map(len, mycoord)) + len(mycoord) 
count = 0
for i in range(1, len(intersections)):
  a, b = intersections[i - 1], intersections[i]
  colors = sorted(a[1] & b[1])
  if len(colors) > 0:
    count += 1
    print('sect{0}/{1:<{2}}: {3},{4}'.format(count, '-'.join(colors), tab_width,
        a[0], b[0]))

Result:

sect1/pink-red              : 5258,5266
sect2/orange-pink-red       : 5266,5422
sect3/orange-red            : 5422,5425
sect4/green-orange-red      : 5425,5450
sect5/orange-red            : 5450,5479
sect6/orange-pink-red       : 5479,5770
sect7/pink-red              : 5770,5864