| 36 | |
| 37 | template <typename Iter> |
| 38 | bool CheckPolygonSelfIntersections(Iter beg, Iter end) |
| 39 | { |
| 40 | Iter last = end; |
| 41 | --last; |
| 42 | |
| 43 | for (Iter i = beg; i != last; ++i) |
| 44 | { |
| 45 | for (Iter j = i; j != end; ++j) |
| 46 | { |
| 47 | // do not check intersection of neibour segments |
| 48 | if (std::distance(i, j) <= 1 || (i == beg && j == last)) |
| 49 | continue; |
| 50 | |
| 51 | Iter ii = base::NextIterInCycle(i, beg, end); |
| 52 | Iter jj = base::NextIterInCycle(j, beg, end); |
| 53 | PointD a = *i, b = *ii, c = *j, d = *jj; |
| 54 | |
| 55 | // check for rect intersection |
| 56 | if (std::max(a.x, b.x) < std::min(c.x, d.x) || std::min(a.x, b.x) > std::max(c.x, d.x) || |
| 57 | std::max(a.y, b.y) < std::min(c.y, d.y) || std::min(a.y, b.y) > std::max(c.y, d.y)) |
| 58 | { |
| 59 | continue; |
| 60 | } |
| 61 | |
| 62 | double const s1 = OrientedS(a, b, c); |
| 63 | double const s2 = OrientedS(a, b, d); |
| 64 | double const s3 = OrientedS(c, d, a); |
| 65 | double const s4 = OrientedS(c, d, b); |
| 66 | |
| 67 | // check if sections have any intersection |
| 68 | if (s1 * s2 > 0.0 || s3 * s4 > 0.0) |
| 69 | continue; |
| 70 | |
| 71 | // Common principle if any point lay exactly on section, check 2 variants: |
| 72 | // - only touching (><) - don't return as intersection; |
| 73 | // - 'X'-crossing - return as intersection; |
| 74 | // 'X'-crossing defines when points lay in different cones. |
| 75 | |
| 76 | if (s1 == 0.0 && IsInSection(a, b, c)) |
| 77 | { |
| 78 | PointD const prev = *base::PrevIterInCycle(j, beg, end); |
| 79 | |
| 80 | PointD test[] = {a, b}; |
| 81 | if (a == c) |
| 82 | test[0] = *base::PrevIterInCycle(i, beg, end); |
| 83 | if (b == c) |
| 84 | test[1] = *base::NextIterInCycle(ii, beg, end); |
| 85 | |
| 86 | if (IsSegmentInCone(c, test[0], prev, d) == IsSegmentInCone(c, test[1], prev, d)) |
| 87 | continue; |
| 88 | } |
| 89 | |
| 90 | if (s2 == 0.0 && IsInSection(a, b, d)) |
| 91 | { |
| 92 | PointD const next = *base::NextIterInCycle(jj, beg, end); |
| 93 | |
| 94 | PointD test[] = {a, b}; |
| 95 | if (a == d) |