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
| 474 | //See "The Point in Polygon Problem for Arbitrary Polygons" by Hormann & Agathos |
| 475 | //http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf |
| 476 | int PointInPolygon(const IntPoint& pt, const Path& path) |
| 477 | { |
| 478 | //returns 0 if false, +1 if true, -1 if pt ON polygon boundary |
| 479 | int result = 0; |
| 480 | size_t cnt = path.size(); |
| 481 | if (cnt < 3) |
| 482 | return 0; |
| 483 | IntPoint ip = path[0]; |
| 484 | for (size_t i = 1; i <= cnt; ++i) { |
| 485 | const IntPoint& ipNext = (i == cnt ? path[0] : path[i]); |
| 486 | if (ipNext.Y == pt.Y) { |
| 487 | if ((ipNext.X == pt.X) || (ip.Y == pt.Y && ((ipNext.X > pt.X) == (ip.X < pt.X)))) |
| 488 | return -1; |
| 489 | } |
| 490 | if ((ip.Y < pt.Y) != (ipNext.Y < pt.Y)) { |
| 491 | if (ip.X >= pt.X) { |
| 492 | if (ipNext.X > pt.X) |
| 493 | result = 1 - result; |
| 494 | else { |
| 495 | double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) - (double)(ipNext.X - pt.X) * (ip.Y - pt.Y); |
| 496 | if (!d) |
| 497 | return -1; |
| 498 | if ((d > 0) == (ipNext.Y > ip.Y)) |
| 499 | result = 1 - result; |
| 500 | } |
| 501 | } else { |
| 502 | if (ipNext.X > pt.X) { |
| 503 | double d = (double)(ip.X - pt.X) * (ipNext.Y - pt.Y) - (double)(ipNext.X - pt.X) * (ip.Y - pt.Y); |
| 504 | if (!d) |
| 505 | return -1; |
| 506 | if ((d > 0) == (ipNext.Y > ip.Y)) |
| 507 | result = 1 - result; |
| 508 | } |
| 509 | } |
| 510 | } |
| 511 | ip = ipNext; |
| 512 | } |
| 513 | return result; |
| 514 | } |
| 515 | //------------------------------------------------------------------------------ |
| 516 | |
| 517 | int PointInPolygon(const IntPoint& pt, OutPt* op) |
no test coverage detected