//////////////////////////////////////////////////// PIP3: An entirely different algorithm for comparison. "Optimal Reliable Point-in-Polygon Test and Differential Coding Boolean Operations on Polygons" by Jianqiang Hao et al. Symmetry 2018, 10(10), 477; https://doi.org/10.3390/sym10100477 ////////////////////////////////////////////////////
| 202 | // Symmetry 2018, 10(10), 477; https://doi.org/10.3390/sym10100477 |
| 203 | ///////////////////////////////////////////////////////// |
| 204 | static PointInPolygonResult PIP3(const Point64&pt, const Path64&path) |
| 205 | { |
| 206 | if (!path.size()) return PointInPolygonResult::IsOutside; |
| 207 | int64_t x1, y1, x2, y2; |
| 208 | int k = 0; |
| 209 | Path64::const_iterator itPrev = path.cend() - 1; |
| 210 | Path64::const_iterator itCurr = path.cbegin(); |
| 211 | for ( ; itCurr != path.cend(); ++itCurr) |
| 212 | { |
| 213 | y1 = itPrev->y - pt.y; |
| 214 | y2 = itCurr->y - pt.y; |
| 215 | if (((y1 < 0) && (y2 < 0)) || ((y1 > 0) && (y2 > 0))) |
| 216 | { |
| 217 | itPrev = itCurr; |
| 218 | continue; |
| 219 | } |
| 220 | |
| 221 | x1 = itPrev->x - pt.x; |
| 222 | x2 = itCurr->x - pt.x; |
| 223 | if ((y1 <= 0) && (y2 > 0)) |
| 224 | { |
| 225 | //double f = double(x1) * y2 - double(x2) * y1; // avoids int overflow |
| 226 | int64_t f = x1 * y2 - x2 * y1; |
| 227 | if (f > 0) ++k; |
| 228 | else if (f == 0) return PointInPolygonResult::IsOn; |
| 229 | } |
| 230 | else if ((y1 > 0) && (y2 <= 0)) |
| 231 | { |
| 232 | int64_t f = x1 * y2 - x2 * y1; |
| 233 | if (f < 0) ++k; |
| 234 | else if (f == 0) return PointInPolygonResult::IsOn; |
| 235 | } |
| 236 | else if (((y2 == 0) && (y1 < 0)) || ((y1 == 0) && (y2 < 0))) |
| 237 | { |
| 238 | int64_t f = x1 * y2 - x2 * y1; |
| 239 | if (f == 0) return PointInPolygonResult::IsOn; |
| 240 | } |
| 241 | else if ((y1 == 0) && (y2 == 0) && |
| 242 | (((x2 <= 0) && (x1 >= 0)) || ((x1 <= 0) && (x2 >= 0)))) |
| 243 | return PointInPolygonResult::IsOn; |
| 244 | itPrev = itCurr; |
| 245 | } |
| 246 | if (k % 2) return PointInPolygonResult::IsInside; |
| 247 | return PointInPolygonResult::IsOutside; |
| 248 | } |
| 249 | |
| 250 | |
| 251 | ///////////////////////////////////////////////////////// |