java - Adding/cumulating "line chart components" -

i can imagine there algorithmic problem describes problem not find any. want is:

let's say, have data structure object of type line contains 2 (or more, in case 2 enough) objects of type point(x, y).

a line represents line in line chart 1 point a(x, y) point b(x, y).

now have list of such lines. note, may overlap in x-coordinates. example have line (0, 0) (3, 1) , line (2, 0) (3, 2). want "cumulate" list of lines , have list of points result (to draw line chart later).

for above example mean want {(0, 0); (2, 0,67); (3, 2)}. here beautiful image makes issue more clear:

background: programming blood alcohol content level calculator. have several drinks attributes like: volume, percent, start time, end time.

i want assume linear rise of blood alcohol content level start time end time minus alcohol reduction during time period. in thoughts, easy calculate single "lines" of each drinks, full line chart representing blood alcohol content level on whole time, have "add"/"cumulate" "lines" together.

at least thoughts , approach, if have different approaches/suggestions, please let me know well.

main idea of algorithm:

1. split x axis intervals. points defining intervals correspond 'x' attribute of each point of each line.

2. summation of lines contained in intervals. generate new line per interval. line summation of lines contained in interval.

3. in order able sum 2 lines, transform both lines functions (slope y-intercept form), perform sum , create new line.

the slope intercept form equation of straight line given by:

y = mx + b 

where:

1. m slope of line
2. b y-intercept of line

the slope m of line through 2 points (x1, y1) , (x2, y2) given by:

the y-intercept b of line value of y @ point line crosses y axis. since point (x1, y1) have y1 = mx1 + b, y-intercept b can calculated by:

b = y1 - mx1 

the 'x' values of points of new line limits of interval, 'y' values result of applying function 'x' value.

the code: (note: getters/setters ommited)

linefunction:

public class linefunction {      private final double m, b;      public linefunction(line l) {         /**          * y= ((y_b-y_a)/(x_b-x_a))*(x-x_a) + y_a          *           * ((y_b-y_a)/(x_b-x_a))==> m          *           * y = m *(x-x_a)+y_a          *           * y= m*x -m*x_a +y_a          *           * -m*x_a +y_a -> b          *           * y = m*x + b          */         double y_a, y_b, x_a, x_b;         x_a = l.getp1().getx();         y_a = l.getp1().gety();         x_b = l.getp2().getx();         y_b = l.getp2().gety();         m = (y_b - y_a) / (x_b - x_a);         b = -m * x_a + y_a;      }      private linefunction(double m, double b) {         this.m = m;         this.b = b;     }      public double computefor(double xvalue) {         return this.m * xvalue + this.b;     }      public linefunction sum(linefunction other) {         return new linefunction(this.m + other.m, this.b + other.b);     }      @override     public string tostring() {         return "y = " + m + "x + " + b;     } } 

this class represent simple function of type y = mx + b . basically, takes line , transforms function.

line:

public class line {      private final point p1, p2;     private final linefunction linefunction;      public line(point p1, point p2) {         this.p1 = p1;         this.p2 = p2;         this.linefunction = new linefunction(this);     }     public line(line o) {         this.p1 = o.p1;         this.p2 = o.p2;         this.linefunction = new linefunction(this);     }     public line sum(line other,point p1,point p2) {         linefunction s= this.linefunction.sum(other.linefunction);         return new line(new point(p1.getx(),s.computefor(p1.getx())),new point(p2.getx(),s.computefor(p2.getx())));     }     public boolean isininterval(point p) {         return p.getx() >= this.p1.getx() && p.getx() < this.p2.getx();     }      @override     public string tostring() {         return "{"+p1+","+p2+"}";     }  } 

a line defined 2 points, , line can function defines it. has methods checking if x value of point between starting , ending x of line.

in order accomplish point 1 of algorithm, need know points of every line:

public static arraylist<point> getallpoints(arraylist<line> lines) {         hashset<point> points = new hashset<point>();         (line line : lines)         {             points.add(line.getp1());             points.add(line.getp2());         }         arraylist<point> res = new arraylist<point>(points);         collections.sort(res);         return res;     } 

this method returns points defining intervals. points must ordered, so

public class point implements comparable<point>{     private long x;     private double y;      @override     public int compareto(point o) {         int cmp1=long.compare(this.x, o.x);         return  cmp1 != 0 ? cmp1 : double.compare(this.y, o.y) ;     }      @override     public string tostring() {         return "(" + x + "," + y + ")";     }      @override     public int hashcode() {         final int prime = 31;         int result = 1;         result = prime * result + (int) (x ^ (x >>> 32));         long temp;         temp = double.doubletolongbits(y);         result = prime * result + (int) (temp ^ (temp >>> 32));         return result;     }      @override     public boolean equals(object obj) {         if (this == obj)             return true;         if (obj == null)             return false;         if (getclass() != obj.getclass())             return false;         point other = (point) obj;         if (x != other.x)             return false;         if (double.doubletolongbits(y) != double.doubletolongbits(other.y))             return false;         return true;     }  } 

for second step of algorithm, need know wich lines belong given interval:

public static arraylist<line> filter(point p, arraylist<line> lines) {         arraylist<line> filtered = new arraylist<line>();         (line line : lines)             if (line.isininterval(p))                 filtered.add(line);          return filtered;     } 

the thing left summation of groups of lines:

public static arraylist<line> sumall(arraylist<line> lines) {         arraylist<point> points = getallpoints(lines);         arraylist<line> result = new arraylist<>();          (int = 0; < points.size() - 1; i++)         {             point current = points.get(i);             point next = points.get(i + 1);             arraylist<line> filtered = filter(current, lines);             line acc = new line(new point(current.getx(), 0), new point(                     next.getx(), 0));              (line lf : filtered)             {                 acc = acc.sum(lf, current, next);             }              result.add(acc);         }         return result;     } 

a simple example:

public static void main(string[] args) {         line l1 = new line(new point(0, 0), new point(3, 1));         line l2 = new line(new point(2, 0), new point(3, 1));          line l3 = new line(new point(4, 7), new point(8, 2));         line l4 = new line(new point(5, 4), new point(6, 1));          line l5 = new line(new point(9, 6), new point(10, 1));         arraylist<line> lines = new arraylist<line>();         lines.add(l1);         lines.add(l2);         lines.add(l3);         lines.add(l4);         lines.add(l5);         arraylist<line> res = sumall(lines);         (line line : res)         {             system.out.println(line);         }       } 

output:

{(0,0.0),(2,0.6666666666666666)} {(2,0.666666666666667),(3,2.0)} {(3,0.0),(4,0.0)} ----> there's no line in interval. {(4,7.0),(5,5.75)} {(5,9.75),(6,5.5)} {(6,4.5),(8,2.0)} {(8,0.0),(9,0.0)} {(9,6.0),(10,1.0)} 

if i'm missing anything, don't hesitate lo leave comment.