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