See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf
| 438 | //See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos |
| 439 | //http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf |
| 440 | int PointInPolygon(const IntPoint &pt, const Path &path) |
| 441 | { |
| 442 | //returns 0 if false, +1 if true, -1 if pt ON polygon boundary |
| 443 | int result = 0; |
| 444 | size_t cnt = path.size(); |
| 445 | if (cnt < 3) return 0; |
| 446 | IntPoint ip = path[0]; |
| 447 | for(size_t i = 1; i <= cnt; ++i) |
| 448 | { |
| 449 | IntPoint ipNext = (i == cnt ? path[0] : path[i]); |
| 450 | if (ipNext.Y == pt.Y) |
| 451 | { |
| 452 | if ((ipNext.X == pt.X) || (ip.Y == pt.Y && |
| 453 | ((ipNext.X > pt.X) == (ip.X < pt.X)))) return -1; |
| 454 | } |
| 455 | if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y)) |
| 456 | { |
| 457 | if (ip.X >= pt.X) |
| 458 | { |
| 459 | if (ipNext.X > pt.X) result = 1 - result; |
| 460 | else |
| 461 | { |
| 462 | double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) - |
| 463 | (double)(ipNext.X - pt.X) * (ip.Y - pt.Y); |
| 464 | if (!d) return -1; |
| 465 | if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result; |
| 466 | } |
| 467 | } else |
| 468 | { |
| 469 | if (ipNext.X > pt.X) |
| 470 | { |
| 471 | double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) - |
| 472 | (double)(ipNext.X - pt.X) * (ip.Y - pt.Y); |
| 473 | if (!d) return -1; |
| 474 | if ((d > 0) == (ipNext.Y > ip.Y)) result = 1 - result; |
| 475 | } |
| 476 | } |
| 477 | } |
| 478 | ip = ipNext; |
| 479 | } |
| 480 | return result; |
| 481 | } |
| 482 | //------------------------------------------------------------------------------ |
| 483 | |
| 484 | int PointInPolygon (const IntPoint &pt, OutPt *op) |
no test coverage detected