Merge all overlapping sectors on the same circle

Question

Given a set of sectors (startAngle, stopAngle) on the same circle (0-2pi), I want to reduce the set so that all sectors that overlap/intersect, are merged. Preferably, in the process, I don't want to split any sector that spans over 360deg/2pi.

Using the intersect-operation of "check if two segments on the same circle overlap / intersect" it seems straight forward to just compare each sector in a pre-sorted set (lesser startAngle first) and merge any compared two sectors that intersect. However, that approach only seem to work if sectors that span over 360deg/2pi are first split in two.

Can anyone help with a more elegant solution that does not involve splitting any sectors? (Pseudo-code, Java or Ada preferably)

Answer 1

I assume that you use (start_angle > end_angle) to flag that any segment spans across 2pi. If this is the case, then the following should work:

 Add 2pi to  end_angle of segments spanning 2pi. 
 Merge your segments (using your ordered start_angle method) over the range 0-4pi.
 If you only have one segment left, and start_angle > end_angle your segment covers the full circle.  
 Otherwise, subtract 2pi from any angle > 2pi (there will only be one of these at most).

You will end up with either a full circle, or one or more independent segments (one of which may span over 2pi).

Answer 2

This solution does involve splitting sectors, but seems simpler than the one below that doesn't:

• Split the sectors into start and end points.

• Add a start point at 0 and an end point at 2π for each interval going over this point.

• Sort points - when two points are equal, put the start point first (in order to prevent 0-size gaps).

• Go through the points, keeping a count of current overlapping intervals.

  • On a start point:

    • If the count is 0, mark the current point as the sector start.

    • Increase the count.

  • On an end point:

    • Decrease the count.

    • If the count is 0, output the sector start and the current point as an sector.

• If you have a sector starting at 0 and one ending at 2π, merge the two.

---

A solution that does not involve splitting any sectors:

• Determine a point X which has no overlapping intervals.

  • Split the sectors into start and end points.

  • Add 2π to any end point of any sector going over the "start" (0/2π), as to have it end up at the end after the sort.

  • Sort points.

  • Go through the points, keeping a count of current intervals.

    • On a start point, increase the count.

    • On an end point, decrease the count.

    • If the count is 0, stop - the current point has no overlapping intervals.

• Shift all the intervals by that point's value.

  Set every point's value to (value + X's value) % 2π.

  Resort the points - a complete sort isn't strictly necessary though - it's not too difficult to intertwine the start and end to accomplish this shift.

• Proceed to go through the points as described in the above solution.

• Shift the sectors that were output back.

  Set every sector's point's value to (2π + value - X's value) % 2π.

Answer 3

First, merge all the sectors ignoring the fact that alfa and alfa+2*pi are the same angle into a list L.

Then if the ending angle for the last sector in L is bigger than 2*pi, merge it with the sectors at the head of L until you find any that doesn't overlap.

update: and now, with some code:

#!/usr/bin/python3

from math import pi;
from random import random;
from operator import itemgetter;

def random_sector():
    start = random() * 2 * pi;
    end = start + random() * .5 * pi;
    return (start, end);

sectors = [random_sector() for i in range(10)]

sectors.sort(key=itemgetter(0))

print("all sectors: ", sectors)

out = [];
(start, end) = sectors.pop(0)
for s in sectors:
    if s[0] <= end:
        if s[1] > end:
            end = s[1]
    else:
        out.append((start, end))
        (start, end) = s

if end > 2 * pi:
    while out:
        s = out[0]
        if s[0] + 2 * pi <= end:
            out.pop(0)
            s_end = s[1] + 2 * pi
            if s_end > end:
                end = s_end
                break
        else:
            break

if end >= start + 2 * pi:
    out = [(0, 2*pi)]
else:
    out.append((start, end))

print("merged sectors: ", out)