Finding union length of many line segments

Question

I have few bolded line segments on x-axis in form of their beginning and ending x-coordinates. Some line segments may be overlapping. How to find the union length of all the line segments.

Example, a line segment is 5,0 to 8,0 and other is 9,0 to 12,0. Both are non overlapping, so sum of length is 3 + 3 = 6.

a line segment is 5,0 to 8,0 and other is 7,0 to 12,0. But they are overlapping for range, 7,0 to 8,0. So union of length is 7.

But the x- coordinates may be floating points.

Answer 1

Java implementation

import  java.util.*;

public class HelloWorld{

static void unionLength(int a[][],int sets)
{
    TreeMap<Integer,Boolean> t=new TreeMap<>();
    
    
    for(int i=0;i<sets;i++)
    {
         t.put(a[i][0],false);
         t.put(a[i][1],true);
         
         
    }
int count=0;
int res=0;
int one=1;
Set set = t.entrySet();
Iterator it = set.iterator();

int prev=0;

while(it.hasNext()) {
    if(one==1){
          Map.Entry me = (Map.Entry)it.next();
          one=0;
          prev=(int)me.getKey();
          if((boolean)me.getValue()==false)
              count++;
          else
              count--;
    }
    
  Map.Entry me = (Map.Entry)it.next();

  if(count>0)
      res=res+((int)me.getKey()-prev);
  
  if((boolean)me.getValue()==false)
      count++;
  else
      count--;

   prev=(int)me.getKey();

} 
System.out.println(res);
}
 public static void main(String []args){
    
    int a[][]={{0, 4}, {3, 6},{8,10}};
    int b[][]={{5, 10}, {8, 12}};
    unionLength(a,3);
    unionLength(b,2);
       
 }

}

Answer 2

Represent a line segment as 2 EndPoint object. Each EndPoint object has the form <coordinate, isStartEndPoint>. Put all EndPoint objects of all the line segments together in a list endPointList.

The algorithm:

• Sort endPointList, first by coordinate in ascending order, then place the start end points in front of the tail end points (regardless of which segment, since it doesn't matter - all at the same coordinate).

• Loop through the sorted list according to this pseudocode:

  prevCoordinate = -Inf
  numSegment = 0
  unionLength = 0
  
  for (endPoint in endPointList):
      if (numSegment > 0):
          unionLength += endPoint.coordinate - prevCoordinate
  
      prevCoordinate = endPoint.coordinate
  
      if (endPoint.isStartCoordinate):
          numSegment = numSegment + 1
      else:
          numSegment = numSegment - 1
  

The numSegment variable will tell whether we are in a segment or not. When it is larger than 0, we are inside some segment, so we can include the distance to the previous end point. If it is 0, it means that the part before the current end point doesn't contain any segment.

The complexity is dominated by the sorting part, since comparison-based sorting algorithm has lower bound of Omega(n log n), while the loop is clearly O(n) at best. So the complexity of the algorithm can be said to be O(n log n) if you choose an O(n log n) comparison-based sorting algorithm.

Answer 3

Here is a solution I just wrote in Haskell and below it is an example of how it can be implemented in the interpreter command prompt. The segments must be presented in the form of a list of tuples [(a,a)]. I hope you can get a sense of the algorithm from the code.

import Data.List

unionSegments segments = 
  let (x:xs) = sort segments
      one_segment = snd x - fst x
  in if xs /= []
        then if snd x > fst (head xs) 
                then one_segment - (snd x - fst (head xs)) + unionSegments xs
                else one_segment + unionSegments xs
        else one_segment

*Main> :load "unionSegments.hs"
[1 of 1] Compiling Main ( unionSegments.hs, interpreted )
Ok, modules loaded: Main.
*Main> unionSegments [(5,8), (7,12)]
7

Answer 4

Use a range tree. A range tree is n log(n), just like the sorted begin/end points, but it has the additional advantage that overlapping ranges will reduce the number of elements (but maybe increase the cost of insertion) Snippet (untested)

struct segment {
        struct segment *ll, *rr;
        float lo, hi;
        };

struct segment * newsegment(float lo, float hi) {
struct segment * ret;
ret = malloc (sizeof *ret);
ret->lo = lo; ret->hi = hi;
ret->ll= ret->rr = NULL;
return ret;
}

struct segment * insert_range(struct segment *root, float lo, float hi)
{
if (!root) return newsegment(lo, hi);

        /* non-overlapping(or touching)  ranges can be put into the {l,r} subtrees} */
if (hi < root->lo) {
        root->ll = insert_range(root->ll, lo, hi);
        return root;
        }
if (lo > root->hi) {
        root->rr = insert_range(root->rr, lo, hi);
        return root;
        }

        /* when we get here, we must have overlap; we can extend the current node
        ** we also need to check if the broader range overlaps the child nodes
        */
if (lo < root->lo ) {
        root->lo = lo;
        while (root->ll && root->ll->hi >= root->lo) {
                struct segment *tmp;
                tmp = root->ll;
                root->lo = tmp->lo;
                root->ll = tmp->ll;
                tmp->ll = NULL;
                // freetree(tmp);
                }
        }
if (hi > root->hi ) {
        root->hi = hi;
        while (root->rr && root->rr->lo <= root->hi) {
                struct segment *tmp;
                tmp = root->rr;
                root->hi = tmp->hi;
                root->rr = tmp->rr;
                tmp->rr = NULL;
                // freetree(tmp);
                }
        }

return root;
}

float total_width(struct segment *ptr)
{
float ret;
if (!ptr) return 0.0;

ret = ptr->hi - ptr->lo;
ret += total_width(ptr->ll);
ret += total_width(ptr->rr);

return ret;
}