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 // TODO check if ignoring p is bad
312 if ( no < 0 || no >= int(bords.size()) ) {
313 return;
314 }
316 if ( s_first < 0 ) {
317 s_first = s_last = no;
318 bords[no].s_prev = -1;
319 bords[no].s_next = -1;
320 return;
321 }
323 if ( guess < 0 || guess >= int(bords.size()) ) {
324 int c = s_first;
325 while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) < 0 ) {
326 c = bords[c].s_next;
327 }
329 if ( c < 0 || c >= int(bords.size()) ) {
330 bords[no].s_prev = s_last;
331 bords[s_last].s_next = no;
332 s_last = no;
333 } else {
334 bords[no].s_prev = bords[c].s_prev;
335 if ( bords[no].s_prev >= 0 ) {
336 bords[bords[no].s_prev].s_next = no;
337 } else {
338 s_first = no;
339 }
340 bords[no].s_next = c;
341 bords[c].s_prev = no;
342 }
343 } else {
344 int c = guess;
345 int stTst = CmpBord(bords[c], bords[no]);
347 if ( stTst == 0 ) {
349 bords[no].s_prev = bords[c].s_prev;
350 if ( bords[no].s_prev >= 0 ) {
351 bords[bords[no].s_prev].s_next = no;
352 } else {
353 s_first = no;
354 }
355 bords[no].s_next = c;
356 bords[c].s_prev = no;
358 } else if ( stTst > 0 ) {
360 while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c], bords[no]) > 0 ) {
361 c = bords[c].s_prev;
362 }
364 if ( c < 0 || c >= int(bords.size()) ) {
365 bords[no].s_next = s_first;
366 bords[s_first].s_prev =no; // s_first != -1
367 s_first = no;
368 } else {
369 bords[no].s_next = bords[c].s_next;
370 if ( bords[no].s_next >= 0 ) {
371 bords[bords[no].s_next].s_prev = no;
372 } else {
373 s_last = no;
374 }
375 bords[no].s_prev = c;
376 bords[c].s_next = no;
377 }
379 } else {
381 while ( c >= 0 && c < int(bords.size()) && CmpBord(bords[c],bords[no]) < 0 ) {
382 c = bords[c].s_next;
383 }
385 if ( c < 0 || c >= int(bords.size()) ) {
386 bords[no].s_prev = s_last;
387 bords[s_last].s_next = no;
388 s_last = no;
389 } else {
390 bords[no].s_prev = bords[c].s_prev;
391 if ( bords[no].s_prev >= 0 ) {
392 bords[bords[no].s_prev].s_next = no;
393 } else {
394 s_first = no;
395 }
396 bords[no].s_next = c;
397 bords[c].s_prev = no;
398 }
399 }
400 }
401 }
403 /**
404 * Computes the sum of the coverages of the runs currently being scanned,
405 * of which there are "pending".
406 */
407 float FloatLigne::RemainingValAt(float at, int pending)
408 {
409 float sum = 0;
410 /* int no=firstAc;
411 while ( no >= 0 && no < bords.size() ) {
412 int nn=bords[no].other;
413 sum+=bords[nn].val+(at-bords[nn].pos)*bords[nn].pente;
414 // sum+=((at-bords[nn].pos)*bords[no].val+(bords[no].pos-at)*bords[nn].val)/(bords[no].pos-bords[nn].pos);
415 // sum+=ValAt(at,bords[nn].pos,bords[no].pos,bords[nn].val,bords[no].val);
416 no=bords[no].next;
417 }*/
418 // for each portion being scanned, compute coverage at position "at" and sum.
419 // we could simply compute the sum of portion coverages as a "f(x)=ux+y" and evaluate it at "x=at",
420 // but there are numerical problems with this approach, and it produces ugly lines of incorrectly
421 // computed alpha values, so i reverted to this "safe but slow" version
423 for (int i=0; i < pending; i++) {
424 int const nn = bords[i].pend_ind;
425 sum += bords[nn].val + (at - bords[nn].pos) * bords[nn].pente;
426 }
428 return sum;
429 }
432 /**
433 * Extract a set of non-overlapping runs from the boundaries.
434 *
435 * We scan the boundaries left to right, maintaining a set of coverage
436 * portions currently being scanned. For each such portion, the function
437 * will add the index of its first boundary in an array; but instead of
438 * allocating another array, it uses a field in float_ligne_bord: pend_ind.
439 * The outcome is that an array of float_ligne_run is produced.
440 */
441 void FloatLigne::Flatten()
442 {
443 if ( int(bords.size()) <= 1 ) {
444 Reset();
445 return;
446 }
448 runs.clear();
450 // qsort(bords,bords.size(),sizeof(float_ligne_bord),FloatLigne::CmpBord);
451 // SortBords(0,bords.size()-1);
453 float totPente = 0;
454 float totStart = 0;
455 float totX = bords[0].pos;
457 bool startExists = false;
458 float lastStart = 0;
459 float lastVal = 0;
460 int pending = 0;
462 // for (int i=0;i<bords.size();) {
463 // read the list from left to right, adding a run for each boundary crossed, minus runs with alpha=0
464 for (int i=/*0*/s_first; i>=0 && i < int(bords.size()) ;) {
466 float cur = bords[i].pos; // position of the current boundary (there may be several boundaries at this position)
467 float leftV = 0; // deltas in coverage value at this position
468 float rightV = 0;
469 float leftP = 0; // deltas in coverage increase per unit length at this position
470 float rightP = 0;
472 // more precisely, leftV is the sum of decreases of coverage value,
473 // while rightV is the sum of increases, so that leftV+rightV is the delta.
474 // idem for leftP and rightP
476 // start by scanning all boundaries that end a portion at this position
477 while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == false ) {
478 leftV += bords[i].val;
479 leftP += bords[i].pente;
481 #ifndef faster_flatten
482 // we need to remove the boundary that started this coverage portion for the pending list
483 if ( bords[i].other >= 0 && bords[i].other < int(bords.size()) ) {
484 // so we use the pend_inv "array"
485 int const k = bords[bords[i].other].pend_inv;
486 if ( k >= 0 && k < pending ) {
487 // and update the pend_ind array and its inverse pend_inv
488 bords[k].pend_ind = bords[pending - 1].pend_ind;
489 bords[bords[k].pend_ind].pend_inv = k;
490 }
491 }
492 #endif
494 // one less portion pending
495 pending--;
496 // and we move to the next boundary in the doubly linked list
497 i=bords[i].s_next;
498 //i++;
499 }
501 // then scan all boundaries that start a portion at this position
502 while ( i >= 0 && i < int(bords.size()) && bords[i].pos == cur && bords[i].start == true ) {
503 rightV += bords[i].val;
504 rightP += bords[i].pente;
505 #ifndef faster_flatten
506 bords[pending].pend_ind=i;
507 bords[i].pend_inv=pending;
508 #endif
509 pending++;
510 i = bords[i].s_next;
511 //i++;
512 }
514 // coverage value at end of the run will be "start coverage"+"delta per unit length"*"length"
515 totStart = totStart + totPente * (cur - totX);
517 if ( startExists ) {
518 // add that run
519 AddRun(lastStart, cur, lastVal, totStart, totPente);
520 }
521 // update "delta coverage per unit length"
522 totPente += rightP - leftP;
523 // not really needed here
524 totStart += rightV - leftV;
525 // update position
526 totX = cur;
527 if ( pending > 0 ) {
528 startExists = true;
530 #ifndef faster_flatten
531 // to avoid accumulation of numerical errors, we compute an accurate coverage for this position "cur"
532 totStart = RemainingValAt(cur, pending);
533 #endif
534 lastVal = totStart;
535 lastStart = cur;
536 } else {
537 startExists = false;
538 totStart = 0;
539 totPente = 0;
540 }
541 }
542 }
545 /// Debug dump of the instance.
546 void FloatLigne::Affiche()
547 {
548 printf("%lu : \n", (long unsigned int) bords.size());
549 for (int i = 0; i < int(bords.size()); i++) {
550 printf("(%f %f %f %i) ",bords[i].pos,bords[i].val,bords[i].pente,(bords[i].start?1:0)); // localization ok
551 }
553 printf("\n");
554 printf("%lu : \n", (long unsigned int) runs.size());
556 for (int i = 0; i < int(runs.size()); i++) {
557 printf("(%f %f -> %f %f / %f)",
558 runs[i].st, runs[i].vst, runs[i].en, runs[i].ven, runs[i].pente); // localization ok
559 }
561 printf("\n");
562 }
565 int FloatLigne::AddRun(float st, float en, float vst, float ven)
566 {
567 return AddRun(st, en, vst, ven, (ven - vst) / (en - st));
568 }
571 int FloatLigne::AddRun(float st, float en, float vst, float ven, float pente)
572 {
573 if ( st >= en ) {
574 return -1;
575 }
577 int const n = runs.size();
578 float_ligne_run r;
579 r.st = st;
580 r.en = en;
581 r.vst = vst;
582 r.ven = ven;
583 r.pente = pente;
584 runs.push_back(r);
586 return n;
587 }
589 void FloatLigne::Copy(FloatLigne *a)
590 {
591 if ( a->runs.empty() ) {
592 Reset();
593 return;
594 }
596 bords.clear();
597 runs = a->runs;
598 }
600 void FloatLigne::Copy(IntLigne *a)
601 {
602 if ( a->nbRun ) {
603 Reset();
604 return;
605 }
607 bords.clear();
608 runs.resize(a->nbRun);
610 for (int i = 0; i < int(runs.size()); i++) {
611 runs[i].st = a->runs[i].st;
612 runs[i].en = a->runs[i].en;
613 runs[i].vst = a->runs[i].vst;
614 runs[i].ven = a->runs[i].ven;
615 }
616 }
618 /// Cuts the parts having less than tresh coverage.
619 void FloatLigne::Min(FloatLigne *a, float tresh, bool addIt)
620 {
621 Reset();
622 if ( a->runs.empty() ) {
623 return;
624 }
626 bool startExists = false;
627 float lastStart=0;
628 float lastEnd = 0;
630 for (int i = 0; i < int(a->runs.size()); i++) {
631 float_ligne_run runA = a->runs[i];
632 if ( runA.vst <= tresh ) {
633 if ( runA.ven <= tresh ) {
634 if ( startExists ) {
635 if ( lastEnd >= runA.st - 0.00001 ) {
636 lastEnd = runA.en;
637 } else {
638 if ( addIt ) {
639 AddRun(lastStart, lastEnd, tresh, tresh);
640 }
641 lastStart = runA.st;
642 lastEnd = runA.en;
643 }
644 } else {
645 lastStart = runA.st;
646 lastEnd = runA.en;
647 }
648 startExists = true;
649 } else {
650 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
651 if ( startExists ) {
652 if ( lastEnd >= runA.st - 0.00001 ) {
653 if ( addIt ) {
654 AddRun(lastStart, cutPos, tresh, tresh);
655 }
656 AddRun(cutPos,runA.en, tresh, runA.ven);
657 } else {
658 if ( addIt ) {
659 AddRun(lastStart, lastEnd, tresh, tresh);
660 }
661 if ( addIt ) {
662 AddRun(runA.st, cutPos, tresh, tresh);
663 }
664 AddRun(cutPos, runA.en, tresh, runA.ven);
665 }
666 } else {
667 if ( addIt ) {
668 AddRun(runA.st, cutPos, tresh, tresh);
669 }
670 AddRun(cutPos, runA.en, tresh, runA.ven);
671 }
672 startExists = false;
673 }
675 } else {
677 if ( runA.ven <= tresh ) {
678 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
679 if ( startExists ) {
680 if ( addIt ) {
681 AddRun(lastStart, lastEnd, tresh, tresh);
682 }
683 }
684 AddRun(runA.st, cutPos, runA.vst, tresh);
685 startExists = true;
686 lastStart = cutPos;
687 lastEnd = runA.en;
688 } else {
689 if ( startExists ) {
690 if ( addIt ) {
691 AddRun(lastStart, lastEnd, tresh, tresh);
692 }
693 }
694 startExists = false;
695 AddRun(runA.st, runA.en, runA.vst, runA.ven);
696 }
697 }
698 }
700 if ( startExists ) {
701 if ( addIt ) {
702 AddRun(lastStart, lastEnd, tresh, tresh);
703 }
704 }
705 }
707 /**
708 * Cuts the coverage a in 2 parts.
709 *
710 * over will receive the parts where coverage > tresh, while the present
711 * FloatLigne will receive the parts where coverage <= tresh.
712 */
713 void FloatLigne::Split(FloatLigne *a, float tresh, FloatLigne *over)
714 {
715 Reset();
716 if ( a->runs.empty() ) {
717 return;
718 }
720 for (int i = 0; i < int(a->runs.size()); i++) {
721 float_ligne_run runA = a->runs[i];
722 if ( runA.vst >= tresh ) {
723 if ( runA.ven >= tresh ) {
724 if ( over ) {
725 over->AddRun(runA.st, runA.en, runA.vst, runA.ven);
726 }
727 } else {
728 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
729 if ( over ) {
730 over->AddRun(runA.st, cutPos, runA.vst, tresh);
731 }
732 AddRun(cutPos, runA.en, tresh, runA.ven);
733 }
734 } else {
735 if ( runA.ven >= tresh ) {
736 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh-runA.vst)) / (runA.ven - runA.vst);
737 AddRun(runA.st, cutPos, runA.vst, tresh);
738 if ( over ) {
739 over->AddRun(cutPos, runA.en, tresh, runA.ven);
740 }
741 } else {
742 AddRun(runA.st, runA.en, runA.vst, runA.ven);
743 }
744 }
745 }
746 }
748 /**
749 * Clips the coverage runs to tresh.
750 *
751 * If addIt == false, it only leaves the parts that are not entirely under
752 * tresh. If addIt == true, it's the coverage clamped to tresh.
753 */
754 void FloatLigne::Max(FloatLigne *a, float tresh, bool addIt)
755 {
756 Reset();
757 if ( a->runs.empty() <= 0 ) {
758 return;
759 }
761 bool startExists = false;
762 float lastStart = 0;
763 float lastEnd = 0;
764 for (int i = 0; i < int(a->runs.size()); i++) {
765 float_ligne_run runA = a->runs[i];
766 if ( runA.vst >= tresh ) {
767 if ( runA.ven >= tresh ) {
768 if ( startExists ) {
769 if ( lastEnd >= runA.st-0.00001 ) {
770 lastEnd = runA.en;
771 } else {
772 if ( addIt ) {
773 AddRun(lastStart,lastEnd,tresh,tresh);
774 }
775 lastStart = runA.st;
776 lastEnd = runA.en;
777 }
778 } else {
779 lastStart = runA.st;
780 lastEnd = runA.en;
781 }
782 startExists = true;
783 } else {
784 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
785 if ( startExists ) {
786 if ( lastEnd >= runA.st-0.00001 ) {
787 if ( addIt ) {
788 AddRun(lastStart, cutPos, tresh, tresh);
789 }
790 AddRun(cutPos, runA.en, tresh, runA.ven);
791 } else {
792 if ( addIt ) {
793 AddRun(lastStart, lastEnd, tresh, tresh);
794 }
795 if ( addIt ) {
796 AddRun(runA.st, cutPos, tresh, tresh);
797 }
798 AddRun(cutPos, runA.en, tresh, runA.ven);
799 }
800 } else {
801 if ( addIt ) {
802 AddRun(runA.st, cutPos, tresh, tresh);
803 }
804 AddRun(cutPos, runA.en, tresh, runA.ven);
805 }
806 startExists = false;
807 }
809 } else {
811 if ( runA.ven >= tresh ) {
812 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
813 if ( startExists ) {
814 if ( addIt ) {
815 AddRun(lastStart,lastEnd,tresh,tresh);
816 }
817 }
818 AddRun(runA.st, cutPos, runA.vst, tresh);
819 startExists = true;
820 lastStart = cutPos;
821 lastEnd = runA.en;
822 } else {
823 if ( startExists ) {
824 if ( addIt ) {
825 AddRun(lastStart,lastEnd,tresh,tresh);
826 }
827 }
828 startExists = false;
829 AddRun(runA.st, runA.en, runA.vst, runA.ven);
830 }
831 }
832 }
834 if ( startExists ) {
835 if ( addIt ) {
836 AddRun(lastStart, lastEnd, tresh, tresh);
837 }
838 }
839 }
841 /// Extract the parts where coverage > tresh.
842 void FloatLigne::Over(FloatLigne *a, float tresh)
843 {
844 Reset();
845 if ( a->runs.empty() ) {
846 return;
847 }
849 bool startExists = false;
850 float lastStart = 0;
851 float lastEnd = 0;
853 for (int i = 0; i < int(a->runs.size()); i++) {
854 float_ligne_run runA = a->runs[i];
855 if ( runA.vst >= tresh ) {
856 if ( runA.ven >= tresh ) {
857 if ( startExists ) {
858 if ( lastEnd >= runA.st - 0.00001 ) {
859 lastEnd = runA.en;
860 } else {
861 AddRun(lastStart, lastEnd, tresh, tresh);
862 lastStart = runA.st;
863 lastEnd = runA.en;
864 }
865 } else {
866 lastStart = runA.st;
867 lastEnd = runA.en;
868 }
869 startExists = true;
871 } else {
873 float cutPos = (runA.st * (tresh - runA.ven) + runA.en * (runA.vst - tresh)) / (runA.vst - runA.ven);
874 if ( startExists ) {
875 if ( lastEnd >= runA.st - 0.00001 ) {
876 AddRun(lastStart, cutPos, tresh, tresh);
877 } else {
878 AddRun(lastStart, lastEnd, tresh, tresh);
879 AddRun(runA.st, cutPos, tresh, tresh);
880 }
881 } else {
882 AddRun(runA.st, cutPos, tresh, tresh);
883 }
884 startExists = false;
885 }
887 } else {
888 if ( runA.ven >= tresh ) {
889 float cutPos = (runA.st * (runA.ven - tresh) + runA.en * (tresh - runA.vst)) / (runA.ven - runA.vst);
890 if ( startExists ) {
891 AddRun(lastStart, lastEnd, tresh, tresh);
892 }
893 startExists = true;
894 lastStart = cutPos;
895 lastEnd = runA.en;
896 } else {
897 if ( startExists ) {
898 AddRun(lastStart, lastEnd, tresh, tresh);
899 }
900 startExists = false;
901 }
902 }
903 }
905 if ( startExists ) {
906 AddRun(lastStart, lastEnd, tresh, tresh);
907 }
908 }
911 /*
912 Local Variables:
913 mode:c++
914 c-file-style:"stroustrup"
915 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
916 indent-tabs-mode:nil
917 fill-column:99
918 End:
919 */
920 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :