//////////////////////////////////////////////////// PIP2: This is a not fully tested modification of the current Clipper2 PointInPolygon code. It's a little simpler and also marginally faster. ////////////////////////////////////////////////////
| 128 | // simpler and also marginally faster. |
| 129 | ///////////////////////////////////////////////////////// |
| 130 | inline PointInPolygonResult PIP2(const Point64& pt, const Path64& polygon) |
| 131 | { |
| 132 | if (!polygon.size()) return PointInPolygonResult::IsOutside; |
| 133 | Path64::const_iterator cend = polygon.cend(); |
| 134 | Path64::const_iterator last = cend - 1; |
| 135 | Path64::const_iterator first = polygon.cbegin(); |
| 136 | Path64::const_iterator curr = first; |
| 137 | Path64::const_iterator prev = last; |
| 138 | |
| 139 | bool is_above; |
| 140 | if (prev->y == pt.y) |
| 141 | { |
| 142 | if (pt == *prev) return PointInPolygonResult::IsOn; |
| 143 | if ((curr->y == pt.y) && ((curr->x == pt.x) || |
| 144 | ((pt.x > prev->x) == (pt.x < curr->x)))) |
| 145 | return PointInPolygonResult::IsOn; |
| 146 | Path64::const_reverse_iterator pr = polygon.crbegin() +1; |
| 147 | while (pr != polygon.crend() && pr->y == pt.y) ++pr; |
| 148 | is_above = pr == polygon.crend() || pr->y < pt.y; |
| 149 | } |
| 150 | else is_above = prev->y < pt.y; |
| 151 | |
| 152 | int val = 0; |
| 153 | while (curr != cend) |
| 154 | { |
| 155 | if (is_above) |
| 156 | { |
| 157 | while (curr != cend && curr->y < pt.y) ++curr; |
| 158 | if (curr == cend) break; |
| 159 | } |
| 160 | else |
| 161 | { |
| 162 | while (curr != cend && curr->y > pt.y) ++curr; |
| 163 | if (curr == cend) break; |
| 164 | } |
| 165 | |
| 166 | prev = (curr == first) ? last : curr - 1; |
| 167 | if (curr->y == pt.y) |
| 168 | { |
| 169 | if ((curr->x == pt.x) || ((curr->y == prev->y) && |
| 170 | ((pt.x > prev->x) == (pt.x < curr->x)))) |
| 171 | return PointInPolygonResult::IsOn; |
| 172 | ++curr; |
| 173 | continue; |
| 174 | } |
| 175 | |
| 176 | if (pt.x < curr->x && pt.x < prev->x) |
| 177 | { |
| 178 | // we're only interested in edges crossing on the left |
| 179 | } |
| 180 | else if (pt.x > prev->x && pt.x > curr->x) |
| 181 | ++val; |
| 182 | else |
| 183 | { |
| 184 | double d = CrossProduct(*prev, *curr, pt); //avoids integer overflow |
| 185 | if (d == 0) return PointInPolygonResult::IsOn; |
| 186 | if ((d < 0) == is_above) ++val; |
| 187 | } |
no test coverage detected