Created
May 18, 2020 13:37
-
-
Save ShashkovS/7a397f640bcf0c55fa69d4114c9fe0f3 to your computer and use it in GitHub Desktop.
Проверки на пересечения отрезков и многоугольников
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from fractions import Fraction | |
| from math import atan2, pi | |
| EPS = 1e-8 | |
| MAX_X = 2 ** 20 | |
| def _box_intersect(a, b, c, d): | |
| if a > b: a, b = b, a | |
| if c > d: c, d = d, c | |
| return max(a, c) <= min(b, d) | |
| def cross_prod(ptf, ptt): | |
| """Векторное произведение | |
| >>> cross_prod((1, 1), (1, -1)) | |
| -2 | |
| >>> cross_prod((1, 1), (2, 2)) | |
| 0 | |
| """ | |
| (x0, y0) = ptf | |
| (x1, y1) = ptt | |
| res = x0 * y1 - x1 * y0 | |
| return res | |
| def dot_prod(ptf, ptt): | |
| """Скалярное произведение | |
| >>> dot_prod((1, 1), (1, -1)) | |
| 0 | |
| >>> dot_prod((1, 1), (2, 2)) | |
| 4 | |
| """ | |
| (x0, y0) = ptf | |
| (x1, y1) = ptt | |
| res = x0 * x1 + y0 * y1 | |
| return res | |
| def angle_from_v1_to_v2(v1, v2): | |
| uv1 = (-v1[0], -v1[1]) | |
| sym_atan = atan2(cross_prod(uv1, v2), dot_prod(uv1, v2)) | |
| if sym_atan < 0: | |
| sym_atan = 2 * pi + sym_atan | |
| return sym_atan | |
| def is_close(ptf, ptt): | |
| """Точки практически совпдаают | |
| >>> is_close((0, 0), (1, 1)) | |
| False | |
| >>> is_close((0, 0), (0, 0)) | |
| True | |
| >>> is_close((0, 0), (1e-100, -1e-100)) | |
| True | |
| """ | |
| (x0, y0) = ptf | |
| (x1, y1) = ptt | |
| return abs(x0 - x1) < EPS and abs(y0 - y1) < EPS | |
| def segm_to_line(ptf, ptt): | |
| """Проводим прямую ax+by+c через две точки | |
| >>> segm_to_line((0, 0), (1, 1)) | |
| (1, -1, 0) | |
| >>> segm_to_line((0, 0), (1, 0)) | |
| (0, -1, 0) | |
| >>> segm_to_line((0, 0), (0, 1)) | |
| (1, 0, 0) | |
| >>> segm_to_line((1, 0), (0, 1)) | |
| (1, 1, -1) | |
| """ | |
| (x0, y0) = ptf | |
| (x1, y1) = ptt | |
| if abs(x0 - x1) < EPS: | |
| if isinstance(x0, (int, Fraction)) and isinstance(x1, (int, Fraction)): | |
| mid = -Fraction(x0 + x1, 2) # Ху | |
| if mid.denominator == 1: | |
| mid = int(mid) | |
| else: | |
| mid = -(x0 + x1) / 2 | |
| line = (1, 0, mid) | |
| else: | |
| line = (y1 - y0, x0 - x1, y0 * x1 - y1 * x0) | |
| return line | |
| def is_point_between(pt, ptf, ptt, *, strict=True): | |
| """Проверяем, что точка pt лежит на отрезке [ptf, ppt]. | |
| Векторное произведение должно быть нулём, а скалярное — отрицательным | |
| >>> is_point_between((1, 1), (0, 0), (2, 2)) | |
| True | |
| >>> is_point_between((1, 2), (0, 0), (2, 2)) | |
| False | |
| >>> is_point_between((0, 0), (0, 0), (2, 2)) | |
| False | |
| >>> is_point_between((1, 1), (2, 0), (0, 2)) | |
| True | |
| >>> is_point_between((0, 0), (0, 0), (2, 2), strict=False) | |
| True | |
| """ | |
| v1 = (pt[0] - ptf[0], pt[1] - ptf[1]) | |
| v2 = (pt[0] - ptt[0], pt[1] - ptt[1]) | |
| cp = cross_prod(v1, v2) | |
| dp = dot_prod(v1, v2) | |
| if abs(cp) >= EPS: # Если вектроное произведение не 0, то точки не лежат на одной прямой | |
| return False | |
| elif not strict and abs(dp) < EPS: # В нестрогом режиме это означает, что точка совпадает с границей | |
| return True | |
| else: | |
| return dp <= -EPS # Скалярное произведение отрицательно, а значит угол развёрнутый | |
| def segm_intersect(s1f, s1t, s2f, s2t): | |
| """ | |
| Проверяем, пересекаются ли два отрезка. Любые касания — это тоже пересечение | |
| >>> segm_intersect((0, 0), (2, 2), (2, 0), (0, 2)) | |
| True | |
| >>> segm_intersect((1, 0), (1, 2), (0, 1), (2, 1)) | |
| True | |
| >>> segm_intersect((0, 0), (1, 1), (2, 0), (0, 2)) | |
| True | |
| >>> segm_intersect((0, 0), (1, 1), (2, 0), (0, 2)) | |
| True | |
| >>> segm_intersect((0, 0), (1, 1), (2, 2), (3, 3)) | |
| False | |
| >>> segm_intersect((0, 0), (1, 1), (2, 2), (-3, -3)) | |
| True | |
| >>> segm_intersect((0, 0), (2, 2), (1, 1), (3, 3)) | |
| True | |
| >>> segm_intersect((0, 0), (1, 1), (2, 2), (1, 1)) | |
| True | |
| >>> segm_intersect((0, 0), (1, 1), (2, 0), (0, 2)) | |
| True | |
| """ | |
| a, b, c = s1t[0] - s1f[0], s2f[0] - s2t[0], s2f[0] - s1f[0] | |
| p, q, r = s1t[1] - s1f[1], s2f[1] - s2t[1], s2f[1] - s1f[1] | |
| dd = a * q - b * p | |
| if abs(dd) > EPS: | |
| dx = c * q - b * r | |
| dy = a * r - c * p | |
| return 0 <= dx * dd <= dd * dd and 0 <= dy * dd <= dd * dd | |
| else: | |
| return abs(a * r - c * p) < EPS and abs(b * r - q * c) < EPS \ | |
| and _box_intersect(s1f[0], s1t[0], s2f[0], s2t[0]) \ | |
| and _box_intersect(s1f[1], s1t[1], s2f[1], s2t[1]) | |
| def segm_intersection_point(s1f, s1t, s2f, s2t, *, strict=True): | |
| """Находим точку пересечения отрезков. Если отрезки пересекаются по подотрезку, то не считаем это пересечением. | |
| В строгом режиме нас интересует только пересечение по внутренности отрезков | |
| >>> segm_intersection_point((0, 0), (2, 2), (2, 0), (0, 2)) | |
| (1, 1) | |
| >>> segm_intersection_point((1, 0), (1, 2), (0, 1), (2, 1)) | |
| (1, 1) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 0), (0, 2)) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 0), (0, 2), strict=False) | |
| (1, 1) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 2), (3, 3)) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 2), (-3, -3)) | |
| >>> segm_intersection_point((0, 0), (2, 2), (1, 1), (3, 3)) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 2), (1, 1), strict=False) | |
| (1, 1) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 0), (0, 2), strict=False) | |
| (1, 1) | |
| >>> segm_intersection_point((0, 0), (1, 1), (2, 0), (0, 2)) | |
| """ | |
| a1, b1, c1 = segm_to_line(s1f, s1t) | |
| a2, b2, c2 = segm_to_line(s2f, s2t) | |
| dd = a1 * b2 - a2 * b1 | |
| dx = c2 * b1 - c1 * b2 | |
| dy = a2 * c1 - a1 * c2 | |
| if abs(dd) < EPS and abs(dx) < EPS and abs(dy) < EPS: # Кейс "прямые совпадают": | |
| # Мы выдаём ответ в единственном случае: отрезки пересекаются по точке. | |
| # Это происходит в точности тогда, когда у них есть общая граница, которая лежит между другими границами | |
| if strict: # В строгом режиме нас интересует только пересечение по внутренности отрезков | |
| return None | |
| elif is_close(s1f, s2f) and not is_close(s1t, s2t) and is_point_between(s1f, s1t, s2t): | |
| return s1f | |
| elif is_close(s1f, s2t) and not is_close(s1t, s2f) and is_point_between(s1f, s1t, s2f): | |
| return s1f | |
| elif is_close(s1t, s2f) and not is_close(s1f, s2t) and is_point_between(s1t, s1f, s2t): | |
| return s1t | |
| elif is_close(s1t, s2t) and not is_close(s1f, s2f) and is_point_between(s1t, s1f, s2f): | |
| return s1t | |
| else: | |
| return None | |
| elif abs(dd) < EPS: # Кейс "прямые параллельны" (но не совпадают) | |
| return None | |
| else: # Кейс "пересекаются в одной точке" | |
| if all(isinstance(x, (int, Fraction)) for x in (dx, dd, dy)): | |
| sx = Fraction(dx, dd) | |
| sy = Fraction(dy, dd) | |
| if sx.denominator == 1: | |
| sx = int(sx) | |
| if sy.denominator == 1: | |
| sy = int(sy) | |
| else: | |
| sx = dx / dd | |
| sy = dy / dd | |
| res_pt = (sx, sy) | |
| # Теперь проверяем, что точка принадлежит каждому отрезку: | |
| if is_point_between(res_pt, s1f, s1t, strict=strict) and is_point_between(res_pt, s2f, s2t, strict=strict): | |
| return res_pt | |
| else: | |
| return None | |
| def segm_and_poly_intersection(ptf, ptt, poly): | |
| """Находим список пересечений отрезка с многоугольником. | |
| Предполагается, что если отрезок целиком лежит внутри какого-то ребра, то пересечений нет. | |
| Если отрезок содержит в себе кусок ребра, то в выборку попадают только вершины соответствующего ребра | |
| >>> segm_and_poly_intersection((-1, 1), (10, 1), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(2, 1), (4, 1), (6, 1), (0, 1)] | |
| >>> segm_and_poly_intersection((-1, -1), (10, -1), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [] | |
| >>> segm_and_poly_intersection((-1, 0), (10, 0), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(0, 0), (2, 0), (4, 0), (6, 0)] | |
| >>> segm_and_poly_intersection((-1, 5), (10, 5), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(6, 5), (0, 5)] | |
| >>> segm_and_poly_intersection((-1, 15), (10, 15), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [] | |
| >>> segm_and_poly_intersection((3, 15), (3, -15), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(3, 2), (3, 6)] | |
| >>> segm_and_poly_intersection((-1, -1), (15, 15), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(0, 0), (2, 2), (6, 6)] | |
| >>> segm_and_poly_intersection((-1, 3), (3, 3), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(0, 3)] | |
| >>> segm_and_poly_intersection((-1, 1), (3, 1), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(2, 1), (0, 1)] | |
| >>> segm_and_poly_intersection((3, 2), (4, 1), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(3, 2), (4, 1)] | |
| >>> segm_and_poly_intersection((-1, 6), (4, 1), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(3, 2), (4, 1), (0, 5)] | |
| >>> segm_and_poly_intersection((-1, 6), (3.5, 1.5), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(3.0, 2.0), (-0.0, 5.0)] | |
| >>> segm_and_poly_intersection((-1, 6), (6, -1), [(0, 0), (2, 0), (2, 2), (4, 2), (4, 0), (6, 0), (6, 6), (0, 6), (0, 0)]) | |
| [(3, 2), (4, 1), (5, 0), (0, 5)] | |
| """ | |
| inters = [] | |
| for polyf, polyt in zip(poly, poly[1:]): | |
| if is_point_between(polyf, ptf, ptt, strict=False): | |
| inters.append(polyf) | |
| elif is_point_between(polyt, ptf, ptt, strict=False): | |
| # Этот случай почитаем потом | |
| pass | |
| else: # Итак, отрезок не проходит через вершины | |
| cur_inter = segm_intersection_point(ptf, ptt, polyf, polyt, strict=False) | |
| if cur_inter: | |
| inters.append(cur_inter) | |
| return inters | |
| def is_point_in_polygon(pt, poly, *, strict=True): | |
| """Проверяем, что точка лежит внутри многоугольника (или на границе, если strict=False) | |
| poly — это замкнутый многоугольник, первая точка совпадает с последней | |
| Тестируем на следующем многоугольнике (заданном с разных точек обхода) и следующих точках: | |
| 5 *----* * * | |
| 4 |X \X / \ / \ | |
| 3 X| X *X--*X *X X \X | |
| 2 | \ / \ | |
| 1 | * \ | |
| 0 *-------------------------* | |
| 0 45 7 1 3 5 7 9 1 4 6 | |
| >>> is_point_in_polygon((4,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| True | |
| >>> is_point_in_polygon((4,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| True | |
| >>> is_point_in_polygon((4,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| True | |
| >>> is_point_in_polygon((4,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| True | |
| >>> is_point_in_polygon((4,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| True | |
| >>> is_point_in_polygon((4,3), [(15,3), (13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| True | |
| >>> is_point_in_polygon((-4,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| False | |
| >>> is_point_in_polygon((-4,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| False | |
| >>> is_point_in_polygon((-4,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| False | |
| >>> is_point_in_polygon((-4,3), [(11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| False | |
| >>> is_point_in_polygon((-4,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| False | |
| >>> is_point_in_polygon((-4,3), [(15,3), (13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| False | |
| >>> is_point_in_polygon((12,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| False | |
| >>> is_point_in_polygon((12,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| False | |
| >>> is_point_in_polygon((12,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| False | |
| >>> is_point_in_polygon((12,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| False | |
| >>> is_point_in_polygon((12,3), [(13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| False | |
| >>> is_point_in_polygon((12,3), [(15,3), (13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| False | |
| >>> is_point_in_polygon((16,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| True | |
| >>> is_point_in_polygon((16,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| True | |
| >>> is_point_in_polygon((16,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| True | |
| >>> is_point_in_polygon((16,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| True | |
| >>> is_point_in_polygon((16,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| True | |
| >>> is_point_in_polygon((16,3), [(15,3), (13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| True | |
| >>> is_point_in_polygon((8,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)], strict=False) | |
| True | |
| >>> is_point_in_polygon((8,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)], strict=False) | |
| True | |
| >>> is_point_in_polygon((8,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)], strict=False) | |
| True | |
| >>> is_point_in_polygon((8,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)], strict=False) | |
| True | |
| >>> is_point_in_polygon((8,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)], strict=False) | |
| True | |
| >>> is_point_in_polygon((8,3), [(15,3), (13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)], strict=False) | |
| True | |
| >>> is_point_in_polygon((8,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)], strict=True) | |
| False | |
| >>> is_point_in_polygon((8,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)], strict=True) | |
| False | |
| >>> is_point_in_polygon((8,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)], strict=True) | |
| False | |
| >>> is_point_in_polygon((8,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)], strict=True) | |
| False | |
| >>> is_point_in_polygon((8,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)], strict=True) | |
| False | |
| >>> is_point_in_polygon((8,3), [(15,3), (13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)], strict=True) | |
| False | |
| >>> is_point_in_polygon((19,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)], strict=False) | |
| True | |
| >>> is_point_in_polygon((19,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)], strict=False) | |
| True | |
| >>> is_point_in_polygon((19,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)], strict=False) | |
| True | |
| >>> is_point_in_polygon((19,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)], strict=False) | |
| True | |
| >>> is_point_in_polygon((19,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)], strict=False) | |
| True | |
| >>> is_point_in_polygon((19,3), [(15,3), (13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)], strict=False) | |
| True | |
| >>> is_point_in_polygon((19,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)], strict=True) | |
| False | |
| >>> is_point_in_polygon((19,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)], strict=True) | |
| False | |
| >>> is_point_in_polygon((19,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)], strict=True) | |
| False | |
| >>> is_point_in_polygon((19,3), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)], strict=True) | |
| False | |
| >>> is_point_in_polygon((19,3), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)], strict=True) | |
| False | |
| >>> is_point_in_polygon((19,3), [(15,3), (13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)], strict=True) | |
| False | |
| >>> is_point_in_polygon((1,4), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| True | |
| >>> is_point_in_polygon((1,4), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| True | |
| >>> is_point_in_polygon((1,4), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| True | |
| >>> is_point_in_polygon((1,4), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| True | |
| >>> is_point_in_polygon((1,4), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| True | |
| >>> is_point_in_polygon((1,4), [(15,3), (13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| True | |
| >>> is_point_in_polygon((6,4), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| False | |
| >>> is_point_in_polygon((6,4), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| False | |
| >>> is_point_in_polygon((6,4), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| False | |
| >>> is_point_in_polygon((6,4), [(11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| False | |
| >>> is_point_in_polygon((6,4), [(13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| False | |
| >>> is_point_in_polygon((6,4), [(15,3), (13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| False | |
| >>> is_point_in_polygon((24,3), [(0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5), (0,5)]) | |
| False | |
| >>> is_point_in_polygon((24,3), [(5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3), (5,5)]) | |
| False | |
| >>> is_point_in_polygon((24,3), [(7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3), (7,3)]) | |
| False | |
| >>> is_point_in_polygon((24,3), [(11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1), (11,3)]) | |
| False | |
| >>> is_point_in_polygon((24,3), [(13,1), (11,3), (9,3), (8,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3), (13,1)]) | |
| False | |
| >>> is_point_in_polygon((24,3), [(15,3), (13,1), (11,3), (7,3), (5,5), (0,5), (0,0), (26,0), (21,5), (19,3), (17,5), (15,3)]) | |
| False | |
| """ | |
| # Проведём луч из pt строго направо до бесконечности и будем искать пересечения и правильно их учитывать | |
| # 5 *----* * * | |
| # 4 | \ / \ / \ | |
| # 3 | X--*=*=*---*---*---\----X | |
| # 2 | \ / \ | |
| # 1 | * \ | |
| # 0 *-------------------------* | |
| # 0 45 7 1 3 5 7 9 1 6 | |
| is_inside = False | |
| pthi = (MAX_X, pt[1]) # У нас ведь нет точек дальше MAX_X? | |
| # Пройдём по многоугольнику назад до тех пор, пока не найдём ребро не на отрезке | |
| not_on_segm_ind = -2 | |
| while is_point_between(poly[not_on_segm_ind], pt, pthi, strict=False): | |
| not_on_segm_ind -= 1 | |
| prev_not_on_segm = poly[not_on_segm_ind] | |
| is_prev_on_segm = is_point_between(poly[0], pt, pthi, strict=False) | |
| for polyf, polyt in zip(poly, poly[1:]): | |
| if is_point_between(pt, polyf, polyt, strict=False): | |
| return not strict # Если лежит на границе, то это на многоугольнике, но не в | |
| is_cur_on_segm = is_point_between(polyt, pt, pthi, strict=False) | |
| if is_cur_on_segm and is_prev_on_segm: # Ребро на отрезке. Идём дальше | |
| pass | |
| elif is_cur_on_segm: # Снаружи заползли на отрезок | |
| prev_not_on_segm = polyf | |
| elif is_prev_on_segm: # Выползли с отрезка, самое интересное | |
| if segm_intersection_point(pt, pthi, prev_not_on_segm, polyt): | |
| is_inside ^= True | |
| else: # начало и конец ребра не лежат на отрезке | |
| prev_not_on_segm = polyf | |
| if segm_intersection_point(pt, pthi, polyf, polyt): | |
| is_inside ^= True | |
| is_prev_on_segm = is_cur_on_segm | |
| return is_inside |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment