1 /**
2 * \file livarot/float-line.cpp
3 *
4 * Implementation of coverage with floating-point values.
5 *
6 * \author Fred
7 *
8 * public domain
9 *
10 */
12 #ifdef faster_flatten
13 # include <cmath> // std::abs(float)
14 #endif
15 #include "livarot/float-line.h"
16 #include "livarot/int-line.h"
18 FloatLigne::FloatLigne()
19 {
20 s_first = s_last = -1;
21 }
24 FloatLigne::~FloatLigne()
25 {
27 }
29 /// Reset the line to empty (boundaries and runs).
30 void FloatLigne::Reset()
31 {
32 bords.clear();
33 runs.clear();
34 s_first = s_last = -1;
35 }
37 /**
38 * Add a coverage portion.
39 *
40 * \param guess Position from where we should try to insert the first
41 * boundary, or -1 if we don't have a clue.
42 */
43 int FloatLigne::AddBord(float spos, float sval, float epos, float eval, int guess)
44 {
45 // if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
46 if ( spos >= epos ) {
47 return -1;
48 }
50 float pente = (eval - sval) / (epos - spos);
52 #ifdef faster_flatten
53 if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
54 return -1;
55 epos = spos;
56 pente = 0;
57 }
58 #endif
60 if ( guess >= int(bords.size()) ) {
61 guess = -1;
62 }
64 // add the left boundary
65 float_ligne_bord b;
66 int n = bords.size();
67 b.pos = spos;
68 b.val = sval;
69 b.start = true;
70 b.other = n + 1;
71 b.pente = pente;
72 b.s_prev = b.s_next = -1;
73 bords.push_back(b);
75 // insert it in the doubly-linked list
76 InsertBord(n, spos, guess);
78 // add the right boundary
79 n = bords.size();
80 b.pos = epos;
81 b.val = eval;
82 b.start = false;
83 b.other = n-1;
84 b.pente = pente;
85 b.s_prev = b.s_next = -1;
86 bords.push_back(b);
88 // insert it in the doubly-linked list, knowing that boundary at index n-1 is not too far before me
89 InsertBord(n, epos, n - 1);
91 return n;
92 }
94 /**
95 * Add a coverage portion.
96 *
97 * \param guess Position from where we should try to insert the first
98 * boundary, or -1 if we don't have a clue.
99 */
100 int FloatLigne::AddBord(float spos, float sval, float epos, float eval, float pente, int guess)
101 {
102 // if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
103 if ( spos >= epos ) {
104 return -1;
105 }
107 #ifdef faster_flatten
108 if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
109 return -1;
110 epos = spos;
111 pente = 0;
112 }
113 #endif
115 if ( guess >= int(bords.size()) ) {
116 guess=-1;
117 }
119 float_ligne_bord b;
120 int n = bords.size();
121 b.pos = spos;
122 b.val = sval;
123 b.start = true;
124 b.other = n + 1;
125 b.pente = pente;
126 b.s_prev = b.s_next = -1;
127 bords.push_back(b);
129 n = bords.size();
130 b.pos = epos;
131 b.val = eval;
132 b.start = false;
133 b.other = n - 1;
134 b.pente = pente;
135 b.s_prev = b.s_next = -1;
136 bords.push_back(b);
138 InsertBord(n - 1, spos, guess);
139 InsertBord(n, epos, n - 1);
140 /* if ( bords[n-1].s_next < 0 ) {
141 bords[n].s_next=-1;
142 s_last=n;
144 bords[n].s_prev=n-1;
145 bords[n-1].s_next=n;
146 } else if ( bords[bords[n-1].s_next].pos >= epos ) {
147 bords[n].s_next=bords[n-1].s_next;
148 bords[bords[n].s_next].s_prev=n;
150 bords[n].s_prev=n-1;
151 bords[n-1].s_next=n;
152 } else {
153 int c=bords[bords[n-1].s_next].s_next;
154 while ( c >= 0 && bords[c].pos < epos ) c=bords[c].s_next;
155 if ( c < 0 ) {
156 bords[n].s_prev=s_last;
157 bords[s_last].s_next=n;
158 s_last=n;
159 } else {
160 bords[n].s_prev=bords[c].s_prev;
161 bords[bords[n].s_prev].s_next=n;
163 bords[n].s_next=c;
164 bords[c].s_prev=n;
165 }
167 }*/
168 return n;
169 }
171 /**
172 * Add a coverage portion.
173 *
174 * \param guess Position from where we should try to insert the last
175 * boundary, or -1 if we don't have a clue.
176 */
177 int FloatLigne::AddBordR(float spos, float sval, float epos, float eval, float pente, int guess)
178 {
179 // if ( showCopy ) printf("br= %f %f -> %f %f \n",spos,sval,epos,eval);
180 // return AddBord(spos,sval,epos,eval,pente,guess);
181 if ( spos >= epos ){
182 return -1;
183 }
185 #ifdef faster_flatten
186 if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
187 return -1;
188 epos = spos;
189 pente = 0;
190 }
191 #endif
193 if ( guess >= int(bords.size()) ) {
194 guess=-1;
195 }
197 float_ligne_bord b;
198 int n = bords.size();
199 b.pos = spos;
200 b.val = sval;
201 b.start = true;
202 b.other = n + 1;
203 b.pente = pente;
204 b.s_prev = b.s_next = -1;
205 bords.push_back(b);
207 n = bords.size();
208 b.pos = epos;
209 b.val = eval;
210 b.start = false;
211 b.other = n - 1;
212 b.pente = pente;
213 b.s_prev = b.s_next = -1;
214 bords.push_back(b);
216 InsertBord(n, epos, guess);
217 InsertBord(n - 1, spos, n);
219 /* if ( bords[n].s_prev < 0 ) {
220 bords[n-1].s_prev=-1;
221 s_first=n-1;
223 bords[n-1].s_next=n;
224 bords[n].s_prev=n-1;
225 } else if ( bords[bords[n].s_prev].pos <= spos ) {
226 bords[n-1].s_prev=bords[n].s_prev;
227 bords[bords[n-1].s_prev].s_next=n-1;
229 bords[n-1].s_next=n;
230 bords[n].s_prev=n-1;
231 } else {
232 int c=bords[bords[n].s_prev].s_prev;
233 while ( c >= 0 && bords[c].pos > spos ) c=bords[c].s_prev;
234 if ( c < 0 ) {
235 bords[n-1].s_next=s_first;
236 bords[s_first].s_prev=n-1;
237 s_first=n-1;
238 } else {
239 bords[n-1].s_next=bords[c].s_next;
240 bords[bords[n-1].s_next].s_prev=n-1;
242 bords[n-1].s_prev=c;
243 bords[c].s_next=n-1;
244 }
246 }*/
247 return n - 1;
248 }
250 /**
251 * Add a coverage portion by appending boundaries at the end of the list.
252 *
253 * This works because we know they are on the right.
254 */
255 int FloatLigne::AppendBord(float spos, float sval, float epos, float eval, float pente)
256 {
257 // if ( showCopy ) printf("b= %f %f -> %f %f \n",spos,sval,epos,eval);
258 // return AddBord(spos,sval,epos,eval,pente,s_last);
259 if ( spos >= epos ) {
260 return -1;
261 }
263 #ifdef faster_flatten
264 if ( std::abs(epos - spos) < 0.001 || std::abs(pente) > 1000 ) {
265 return -1;
266 epos = spos;
267 pente = 0;
268 }
269 #endif
271 int n = bords.size();
272 float_ligne_bord b;
273 b.pos = spos;
274 b.val = sval;
275 b.start = true;
276 b.other = n + 1;
277 b.pente = pente;
278 b.s_prev = s_last;
279 b.s_next = n + 1;
280 bords.push_back(b);
282 if ( s_last >= 0 ) {
283 bords[s_last].s_next = n;
284 }
286 if ( s_first < 0 ) {
287 s_first = n;
288 }
290 n = bords.size();
291 b.pos = epos;
292 b.val = eval;
293 b.start = false;
294 b.other = n - 1;
295 b.pente = pente;
296 b.s_prev = n - 1;
297 b.s_next = -1;
298 bords.push_back(b);
300 s_last = n;
302 return n;
303 }
307 // insertion in a boubly-linked list. nothing interesting here
308 void FloatLigne::InsertBord(int no, float p, int guess)
309 {
310 if ( no < 0 || no >= int(bords.size()) ) {
311 return;
312 }
314 if ( s_first < 0 ) {
315 s_first = s_last = no;
316 bords[no].s_prev = -1;
317 bords[no].s_next = -1;
318 return;
319 }
321 if ( guess < 0 || guess >= int(bords.size()) ) {
322 int c = s_first;
323 while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) < 0 ) {
324 c = bords[c].s_next;
325 }
327 if ( c < 0 || c >= int(bords.size()) ) {
328 bords[no].s_prev = s_last;
329 bords[s_last].s_next = no;
330 s_last = no;
331 } else {
332 bords[no].s_prev = bords[c].s_prev;
333 if ( bords[no].s_prev >= 0 ) {
334 bords[bords[no].s_prev].s_next = no;
335 } else {
336 s_first = no;
337 }
338 bords[no].s_next = c;
339 bords[c].s_prev = no;
340 }
341 } else {
342 int c = guess;
343 int stTst = CmpBord(bords[c], bords[no]);
345 if ( stTst == 0 ) {
347 bords[no].s_prev = bords[c].s_prev;
348 if ( bords[no].s_prev >= 0 ) {
349 bords[bords[no].s_prev].s_next = no;
350 } else {
351 s_first = no;
352 }
353 bords[no].s_next = c;
354 bords[c].s_prev = no;
356 } else if ( stTst > 0 ) {
358 while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) > 0 ) {
359 c = bords[c].s_prev;
360 }
362 if ( c < 0 || c >= int(bords.size()) ) {
363 bords[no].s_next = s_first;
364 bords[s_first].s_prev =no; // s_first != -1
365 s_first = no;
366 } else {
367 bords[no].s_next = bords[c].s_next;
368 if ( bords[no].s_next >= 0 ) {
369 bords[bords[no].s_next].s_prev = no;
370 } else {
371 s_last = no;
372 }
373 bords[no].s_prev = c;
374 bords[c].s_next = no;
375 }
377 } else {
379 while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c],bords[no]) < 0 ) {
380 c = bords[c].s_next;
381 }
383 if ( c < 0 || c >= int(bords.size()) ) {
384 bords[no].s_prev = s_last;
385 bords[s_last].s_next = no;
386 s_last = no;
387 } else {
388 bords[no].s_prev = bords[c].s_prev;
389 if ( bords[no].s_prev >= 0 ) {
390 bords[bords[no].s_prev].s_next = no;
391 } else {
392 s_first = no;
393 }
394 bords[no].s_next = c;
395 bords[c].s_prev = no;
396 }
397 }
398 }
399 }
401 /**
402 * Computes the sum of the coverages of the runs currently being scanned,
403 * of which there are "pending".
404 */
405 float FloatLigne::RemainingValAt(float at, int pending)
406 {
407 float sum = 0;
408 /* int no=firstAc;
409 while ( no >= 0 && no < bords.size() ) {
410 int nn=bords[no].other;
411 sum+=bords[nn].val+(at-bords[nn].pos)*bords[nn].pente;
412 // sum+=((at-bords[nn].pos)*bords[no].val+(bords[no].pos-at)*bords[nn].val)/(bords[no].pos-bords[nn].pos);
413 // sum+=ValAt(at,bords[nn].pos,bords[no].pos,bords[nn].val,bords[no].val);
414 no=bords[no].next;
415 }*/
416 // for each portion being scanned, compute coverage at position "at" and sum.
417 // we could simply compute the sum of portion coverages as a "f(x)=ux+y" and evaluate it at "x=at",
418 // but there are numerical problems with this approach, and it produces ugly lines of incorrectly
419 // computed alpha values, so i reverted to this "safe but slow" version
421 for (int i=0; i < pending; i++) {
422 int const nn = bords[i].pend_ind;
423 sum += bords[nn].val + (at - bords[nn].pos) * bords[nn].pente;
424 }
426 return sum;
427 }
430 /**
431 * Extract a set of non-overlapping runs from the boundaries.
432 *
433 * We scan the boundaries left to right, maintaining a set of coverage
434 * portions currently being scanned. For each such portion, the function
435 * will add the index of its first boundary in an array; but instead of
436 * allocating another array, it uses a field in float_ligne_bord: pend_ind.
437 * The outcome is that an array of float_ligne_run is produced.
438 */
439 void FloatLigne::Flatten()
440 {
441 if ( int(bords.size()) <= 1 ) {
442 Reset();
443 return;
444 }
446 runs.clear();
448 // qsort(bords,bords.size(),sizeof(float_ligne_bord),FloatLigne::CmpBord);
449 // SortBords(0,bords.size()-1);
451 float totPente = 0;
452 float totStart = 0;
453 float totX = bords[0].pos;
455 bool startExists = false;
456 float lastStart = 0;
457 float lastVal = 0;
458 int pending = 0;
460 // for (int i=0;i<bords.size();) {
461 // read the list from left to right, adding a run for each boundary crossed, minus runs with alpha=0
462 for (int i=/*0*/s_first; i>=0 && i < int(bords.size()) ;) {
464 float cur = bords[i].pos; // position of the current boundary (there may be several boundaries at this position)
465 float leftV = 0; // deltas in coverage value at this position
466 float rightV = 0;
467 float leftP = 0; // deltas in coverage increase per unit length at this position
468 float rightP = 0;
470 // more precisely, leftV is the sum of decreases of coverage value,
471 // while rightV is the sum of increases, so that leftV+rightV is the delta.
472 // idem for leftP and rightP
474 // start by scanning all boundaries that end a portion at this position
475 while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == false ) {
476 leftV += bords[i].val;
477 leftP += bords[i].pente;
479 #ifndef faster_flatten
480 // we need to remove the boundary that started this coverage portion for the pending list
481 if ( bords[i].other >= 0 && bords[i].other < int(bords.size()) ) {
482 // so we use the pend_inv "array"
483 int const k = bords[bords[i].other].pend_inv;
484 if ( k >= 0 && k < pending ) {
485 // and update the pend_ind array and its inverse pend_inv
486 bords[k].pend_ind = bords[pending - 1].pend_ind;
487 bords[bords[k].pend_ind].pend_inv = k;
488 }
489 }
490 #endif
492 // one less portion pending
493 pending--;
494 // and we move to the next boundary in the doubly linked list
495 i=bords[i].s_next;
496 //i++;
497 }
499 // then scan all boundaries that start a portion at this position
500 while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == true ) {
501 rightV += bords[i].val;
502 rightP += bords[i].pente;
503 #ifndef faster_flatten
504 bords[pending].pend_ind=i;
505 bords[i].pend_inv=pending;
506 #endif
507 pending++;
508 i = bords[i].s_next;
509 //i++;
510 }
512 // coverage value at end of the run will be "start coverage"+"delta per unit length"*"length"
513 totStart = totStart + totPente * (cur - totX);
515 if ( startExists ) {
516 // add that run
517 AddRun(lastStart, cur, lastVal, totStart, totPente);
518 }
519 // update "delta coverage per unit length"
520 totPente += rightP - leftP;
521 // not really needed here
522 totStart += rightV - leftV;
523 // update position
524 totX = cur;
525 if ( pending > 0 ) {
526 startExists = true;
528 #ifndef faster_flatten
529 // to avoid accumulation of numerical errors, we compute an accurate coverage for this position "cur"
530 totStart = RemainingValAt(cur, pending);
531 #endif
532 lastVal = totStart;
533 lastStart = cur;
534 } else {
535 startExists = false;
536 totStart = 0;
537 totPente = 0;
538 }
539 }
540 }
543 /// Debug dump of the instance.
544 void FloatLigne::Affiche()
545 {
546 printf("%lu : \n", (long unsigned int) bords.size());
547 for (int i = 0; i < int(bords.size()); i++) {
548 printf("(%f %f %f %i) ",bords[i].pos,bords[i].val,bords[i].pente,(bords[i].start?1:0)); // localization ok
549 }
551 printf("\n");
552 printf("%lu : \n", (long unsigned int) runs.size());
554 for (int i = 0; i < int(runs.size()); i++) {
555 printf("(%f %f -> %f %f / %f)",
556 runs[i].st, runs[i].vst, runs[i].en, runs[i].ven, runs[i].pente); // localization ok
557 }
559 printf("\n");
560 }
563 int FloatLigne::AddRun(float st, float en, float vst, float ven)
564 {
565 return AddRun(st, en, vst, ven, (ven - vst) / (en - st));
566 }
569 int FloatLigne::AddRun(float st, float en, float vst, float ven, float pente)
570 {
571 if ( st >= en ) {
572 return -1;
573 }
575 int const n = runs.size();
576 float_ligne_run r;
577 r.st = st;
578 r.en = en;
579 r.vst = vst;
580 r.ven = ven;
581 r.pente = pente;
582 runs.push_back(r);
584 return n;
585 }
587 void FloatLigne::Copy(FloatLigne *a)
588 {
589 if ( a->runs.empty() ) {
590 Reset();
591 return;
592 }
594 bords.clear();
595 runs = a->runs;
596 }
598 void FloatLigne::Copy(IntLigne *a)
599 {
600 if ( a->nbRun ) {
601 Reset();
602 return;
603 }
605 bords.clear();
606 runs.resize(a->nbRun);
608 for (int i = 0; i < int(runs.size()); i++) {
609 runs[i].st = a->runs[i].st;
610 runs[i].en = a->runs[i].en;
611 runs[i].vst = a->runs[i].vst;
612 runs[i].ven = a->runs[i].ven;
613 }
614 }
616 /// Cuts the parts having less than tresh coverage.
617 void FloatLigne::Min(FloatLigne *a, float tresh, bool addIt)
618 {
619 Reset();
620 if ( a->runs.empty() ) {
621 return;
622 }
624 bool startExists = false;
625 float lastStart=0;
626 float lastEnd = 0;
628 for (int i = 0; i < int(a->runs.size()); i++) {
629 float_ligne_run runA = a->runs[i];
630 if ( runA.vst <= tresh ) {
631 if ( runA.ven <= tresh ) {
632 if ( startExists ) {
633 if ( lastEnd >= runA.st - 0.00001 ) {
634 lastEnd = runA.en;
635 } else {
636 if ( addIt ) {
637 AddRun(lastStart, lastEnd, tresh, tresh);
638 }
639 lastStart = runA.st;
640 lastEnd = runA.en;
641 }
642 } else {
643 lastStart = runA.st;
644 lastEnd = runA.en;
645 }
646 startExists = true;
647 } else {
648 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
649 if ( startExists ) {
650 if ( lastEnd >= runA.st - 0.00001 ) {
651 if ( addIt ) {
652 AddRun(lastStart, cutPos, tresh, tresh);
653 }
654 AddRun(cutPos,runA.en, tresh, runA.ven);
655 } else {
656 if ( addIt ) {
657 AddRun(lastStart, lastEnd, tresh, tresh);
658 }
659 if ( addIt ) {
660 AddRun(runA.st, cutPos, tresh, tresh);
661 }
662 AddRun(cutPos, runA.en, tresh, runA.ven);
663 }
664 } else {
665 if ( addIt ) {
666 AddRun(runA.st, cutPos, tresh, tresh);
667 }
668 AddRun(cutPos, runA.en, tresh, runA.ven);
669 }
670 startExists = false;
671 }
673 } else {
675 if ( runA.ven <= tresh ) {
676 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
677 if ( startExists ) {
678 if ( addIt ) {
679 AddRun(lastStart, lastEnd, tresh, tresh);
680 }
681 }
682 AddRun(runA.st, cutPos, runA.vst, tresh);
683 startExists = true;
684 lastStart = cutPos;
685 lastEnd = runA.en;
686 } else {
687 if ( startExists ) {
688 if ( addIt ) {
689 AddRun(lastStart, lastEnd, tresh, tresh);
690 }
691 }
692 startExists = false;
693 AddRun(runA.st, runA.en, runA.vst, runA.ven);
694 }
695 }
696 }
698 if ( startExists ) {
699 if ( addIt ) {
700 AddRun(lastStart, lastEnd, tresh, tresh);
701 }
702 }
703 }
705 /**
706 * Cuts the coverage a in 2 parts.
707 *
708 * over will receive the parts where coverage > tresh, while the present
709 * FloatLigne will receive the parts where coverage <= tresh.
710 */
711 void FloatLigne::Split(FloatLigne *a, float tresh, FloatLigne *over)
712 {
713 Reset();
714 if ( a->runs.empty() ) {
715 return;
716 }
718 for (int i = 0; i < int(a->runs.size()); i++) {
719 float_ligne_run runA = a->runs[i];
720 if ( runA.vst >= tresh ) {
721 if ( runA.ven >= tresh ) {
722 if ( over ) {
723 over->AddRun(runA.st, runA.en, runA.vst, runA.ven);
724 }
725 } else {
726 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
727 if ( over ) {
728 over->AddRun(runA.st, cutPos, runA.vst, tresh);
729 }
730 AddRun(cutPos, runA.en, tresh, runA.ven);
731 }
732 } else {
733 if ( runA.ven >= tresh ) {
734 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh-runA.vst)) / (runA.ven - runA.vst);
735 AddRun(runA.st, cutPos, runA.vst, tresh);
736 if ( over ) {
737 over->AddRun(cutPos, runA.en, tresh, runA.ven);
738 }
739 } else {
740 AddRun(runA.st, runA.en, runA.vst, runA.ven);
741 }
742 }
743 }
744 }
746 /**
747 * Clips the coverage runs to tresh.
748 *
749 * If addIt == false, it only leaves the parts that are not entirely under
750 * tresh. If addIt == true, it's the coverage clamped to tresh.
751 */
752 void FloatLigne::Max(FloatLigne *a, float tresh, bool addIt)
753 {
754 Reset();
755 if ( a->runs.empty() <= 0 ) {
756 return;
757 }
759 bool startExists = false;
760 float lastStart = 0;
761 float lastEnd = 0;
762 for (int i = 0; i < int(a->runs.size()); i++) {
763 float_ligne_run runA = a->runs[i];
764 if ( runA.vst >= tresh ) {
765 if ( runA.ven >= tresh ) {
766 if ( startExists ) {
767 if ( lastEnd >= runA.st-0.00001 ) {
768 lastEnd = runA.en;
769 } else {
770 if ( addIt ) {
771 AddRun(lastStart,lastEnd,tresh,tresh);
772 }
773 lastStart = runA.st;
774 lastEnd = runA.en;
775 }
776 } else {
777 lastStart = runA.st;
778 lastEnd = runA.en;
779 }
780 startExists = true;
781 } else {
782 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
783 if ( startExists ) {
784 if ( lastEnd >= runA.st-0.00001 ) {
785 if ( addIt ) {
786 AddRun(lastStart, cutPos, tresh, tresh);
787 }
788 AddRun(cutPos, runA.en, tresh, runA.ven);
789 } else {
790 if ( addIt ) {
791 AddRun(lastStart, lastEnd, tresh, tresh);
792 }
793 if ( addIt ) {
794 AddRun(runA.st, cutPos, tresh, tresh);
795 }
796 AddRun(cutPos, runA.en, tresh, runA.ven);
797 }
798 } else {
799 if ( addIt ) {
800 AddRun(runA.st, cutPos, tresh, tresh);
801 }
802 AddRun(cutPos, runA.en, tresh, runA.ven);
803 }
804 startExists = false;
805 }
807 } else {
809 if ( runA.ven >= tresh ) {
810 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
811 if ( startExists ) {
812 if ( addIt ) {
813 AddRun(lastStart,lastEnd,tresh,tresh);
814 }
815 }
816 AddRun(runA.st, cutPos, runA.vst, tresh);
817 startExists = true;
818 lastStart = cutPos;
819 lastEnd = runA.en;
820 } else {
821 if ( startExists ) {
822 if ( addIt ) {
823 AddRun(lastStart,lastEnd,tresh,tresh);
824 }
825 }
826 startExists = false;
827 AddRun(runA.st, runA.en, runA.vst, runA.ven);
828 }
829 }
830 }
832 if ( startExists ) {
833 if ( addIt ) {
834 AddRun(lastStart, lastEnd, tresh, tresh);
835 }
836 }
837 }
839 /// Extract the parts where coverage > tresh.
840 void FloatLigne::Over(FloatLigne *a, float tresh)
841 {
842 Reset();
843 if ( a->runs.empty() ) {
844 return;
845 }
847 bool startExists = false;
848 float lastStart = 0;
849 float lastEnd = 0;
851 for (int i = 0; i < int(a->runs.size()); i++) {
852 float_ligne_run runA = a->runs[i];
853 if ( runA.vst >= tresh ) {
854 if ( runA.ven >= tresh ) {
855 if ( startExists ) {
856 if ( lastEnd >= runA.st - 0.00001 ) {
857 lastEnd = runA.en;
858 } else {
859 AddRun(lastStart, lastEnd, tresh, tresh);
860 lastStart = runA.st;
861 lastEnd = runA.en;
862 }
863 } else {
864 lastStart = runA.st;
865 lastEnd = runA.en;
866 }
867 startExists = true;
869 } else {
871 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
872 if ( startExists ) {
873 if ( lastEnd >= runA.st - 0.00001 ) {
874 AddRun(lastStart, cutPos, tresh, tresh);
875 } else {
876 AddRun(lastStart, lastEnd, tresh, tresh);
877 AddRun(runA.st, cutPos, tresh, tresh);
878 }
879 } else {
880 AddRun(runA.st, cutPos, tresh, tresh);
881 }
882 startExists = false;
883 }
885 } else {
886 if ( runA.ven >= tresh ) {
887 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
888 if ( startExists ) {
889 AddRun(lastStart, lastEnd, tresh, tresh);
890 }
891 startExists = true;
892 lastStart = cutPos;
893 lastEnd = runA.en;
894 } else {
895 if ( startExists ) {
896 AddRun(lastStart, lastEnd, tresh, tresh);
897 }
898 startExists = false;
899 }
900 }
901 }
903 if ( startExists ) {
904 AddRun(lastStart, lastEnd, tresh, tresh);
905 }
906 }
909 /*
910 Local Variables:
911 mode:c++
912 c-file-style:"stroustrup"
913 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
914 indent-tabs-mode:nil
915 fill-column:99
916 End:
917 */
918 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :