src/geo2d/ds/dcvh/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../argsort/lib.hpp" | ||
| 4 | #include "../../ds/cvh/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | // Dynamic Convex Hull | ||
| 9 | template <class FP> | ||
| 10 | class dcvh { | ||
| 11 | // Dynamic half Convex Hull | ||
| 12 | struct dhcvh { | ||
| 13 | csint sgn_; | ||
| 14 | set<point<FP>> vs; | ||
| 15 | |||
| 16 | 104 | CEXPE dhcvh(int sgn_ = 1) NE : sgn_(sgn_) {} | |
| 17 | |||
| 18 | 2565 | CEXP bool contains(point<FP> CR p) CNE { | |
| 19 | 2565 | auto it = vs.lower_bound(point<FP>{p.x, -std::numeric_limits<FP>::max()}); | |
| 20 |
2/2✓ Branch 2 taken 331 times.
✓ Branch 3 taken 2234 times.
|
2565 | if (it == end(vs)) return false; |
| 21 |
2/2✓ Branch 1 taken 639 times.
✓ Branch 2 taken 1595 times.
|
2234 | if (it->x == p.x) return sgn(p.y - it->y) * sgn_ <= 0; |
| 22 |
2/2✓ Branch 2 taken 168 times.
✓ Branch 3 taken 1427 times.
|
1595 | if (it == begin(vs)) return false; |
| 23 | 1427 | auto j = it; | |
| 24 | 1427 | return sgn_cross(*(--j), *it, p) * sgn_ <= 0; | |
| 25 | } | ||
| 26 | template <class IT> | ||
| 27 | 859 | CEXP bool erase(IT it) NE { | |
| 28 |
2/2✓ Branch 2 taken 203 times.
✓ Branch 3 taken 656 times.
|
859 | if (it == begin(vs)) return false; |
| 29 | 656 | auto j = it, k = it; | |
| 30 |
2/2✓ Branch 3 taken 189 times.
✓ Branch 4 taken 467 times.
|
656 | if (++k == end(vs)) return false; |
| 31 | 467 | bool _ = sgn_cross(*(--j), *it, *k) * sgn_ >= 0; | |
| 32 |
2/2✓ Branch 0 taken 189 times.
✓ Branch 1 taken 278 times.
|
467 | if (_) vs.erase(it); |
| 33 | 467 | return _; | |
| 34 | } | ||
| 35 | 1434 | CEXP dhcvh& insert(point<FP> CR p) NE { | |
| 36 |
2/2✓ Branch 1 taken 802 times.
✓ Branch 2 taken 632 times.
|
1434 | if (contains(p)) return *this; |
| 37 | 632 | auto _ = vs.lower_bound(point<FP>{p.x, -std::numeric_limits<FP>::max()}); | |
| 38 |
6/6✓ Branch 2 taken 362 times.
✓ Branch 3 taken 270 times.
✓ Branch 5 taken 105 times.
✓ Branch 6 taken 257 times.
✓ Branch 7 taken 105 times.
✓ Branch 8 taken 527 times.
|
632 | if (_ != end(vs) && _->x == p.x) vs.erase(_); |
| 39 | 632 | vs.insert(p); | |
| 40 | 632 | auto i = vs.find(p), j = i; | |
| 41 |
2/2✓ Branch 2 taken 363 times.
✓ Branch 3 taken 269 times.
|
632 | if (i != begin(vs)) { |
| 42 | 363 | --j; | |
| 43 |
2/2✓ Branch 3 taken 106 times.
✓ Branch 4 taken 363 times.
|
469 | while (erase(j++)) --j; |
| 44 | } | ||
| 45 |
2/2✓ Branch 3 taken 307 times.
✓ Branch 4 taken 325 times.
|
632 | if (++j != end(vs)) |
| 46 |
2/2✓ Branch 3 taken 83 times.
✓ Branch 4 taken 307 times.
|
390 | while (erase(j--)) ++j; |
| 47 | 632 | return *this; | |
| 48 | } | ||
| 49 | } hcvh_up{1}, hcvh_down{-1}; | ||
| 50 | |||
| 51 | public: | ||
| 52 |
4/4✓ Branch 1 taken 457 times.
✓ Branch 2 taken 217 times.
✓ Branch 4 taken 350 times.
✓ Branch 5 taken 107 times.
|
674 | CEXP bool contains(point<FP> CR p) CNE { return hcvh_up.contains(p) && hcvh_down.contains(p); } |
| 53 | 717 | CEXP dcvh& insert(point<FP> CR p) NE { | |
| 54 | 717 | hcvh_up.insert(p), hcvh_down.insert(p); | |
| 55 | 717 | return *this; | |
| 56 | } | ||
| 57 | CEXP cvh<FP> to_CVH() CNE { | ||
| 58 | cvh<FP> ret; | ||
| 59 | copy(hcvh_up.vs, begin(ret.vs)); | ||
| 60 | copy(hcvh_down.vs, std::back_inserter(ret.vs)); | ||
| 61 | argsort(ret.vs); | ||
| 62 | return ret; | ||
| 63 | } | ||
| 64 | }; | ||
| 65 | |||
| 66 | } // namespace tifa_libs | ||
| 67 |