| import math |
| import numpy as np |
|
|
|
|
| class Segment: |
|
|
| def __init__(self, a, b): |
| self.a = (int(a[0]), int(a[1])) |
| self.b = (int(b[0]), int(b[1])) |
|
|
| for dot in [self.a, self.b]: |
| if len(dot) != 2: |
| raise Exception(f"Creating a segment with more or less than two dots: Segment({a}, {b})") |
| if type(dot[0]) != int or type(dot[1]) != int: |
| raise Exception(f"Creating a segment with non-dots: Segment({a}, {b})") |
|
|
| def __str__(self): |
| return f"({self.a}, {self.b})" |
|
|
| def __eq__(self, other): |
| return any([ |
| self.a == other.a and self.b == other.b, |
| self.a == other.b and self.b == other.a, |
| ]) |
|
|
| def dist(self): |
| return math.sqrt(self.dist_x()**2 + self.dist_y()**2) |
|
|
| def dist_x(self, keep_sign = False): |
| dist = self.b[0] - self.a[0] |
| return dist if keep_sign else abs(dist) |
|
|
| def dist_y(self, keep_sign = False): |
| dist = self.b[1] - self.a[1] |
| return dist if keep_sign else abs(dist) |
|
|
| def left(self): |
| return min(self.a[0], self.b[0]) |
|
|
| def top(self): |
| return min(self.a[1], self.b[1]) |
|
|
| def right(self): |
| return max(self.a[0], self.b[0]) |
|
|
| def bottom(self): |
| return max(self.a[1], self.b[1]) |
|
|
| def to_xyrb(self): |
| return [self.left(), self.top(), self.right(), self.bottom()] |
|
|
| def center(self): |
| return ( |
| int(self.left() + self.dist_x() / 2), |
| int(self.top() + self.dist_y() / 2), |
| ) |
|
|
| def may_contain(self, dot): |
| return all([ |
| dot[0] >= self.left(), |
| dot[0] <= self.right(), |
| dot[1] >= self.top(), |
| dot[1] <= self.bottom(), |
| ]) |
|
|
| def intersect(self, other): |
| gutter = max(self.dist(), other.dist()) * 5 / 100 |
|
|
| |
| if not self.angle_ok_with(other): |
| return None |
|
|
| |
|
|
| |
| if any( |
| [ |
| self.right() < other.left() - gutter, |
| self.left() > other.right() + gutter, |
| self.bottom() < other.top() - gutter, |
| self.top() > other.bottom() + gutter, |
| ] |
| ): |
| return None |
|
|
| projected_c = self.projected_point(other.a) |
| dist_c_to_ab = Segment(other.a, projected_c).dist() |
|
|
| projected_d = self.projected_point(other.b) |
| dist_d_to_ab = Segment(other.b, projected_d).dist() |
|
|
| |
| if (dist_c_to_ab + dist_d_to_ab) / 2 > gutter: |
| return None |
|
|
| |
| |
| |
| |
| |
| |
| sorted_dots = sorted([self.a, self.b, other.a, other.b], key = sum) |
| middle_dots = sorted_dots[1:3] |
| b, c = middle_dots |
|
|
| return Segment(b, c) |
|
|
| def union(self, other): |
| intersect = self.intersect(other) |
| if intersect is None: |
| return None |
|
|
| dots = [tuple(self.a), tuple(self.b), tuple(other.a), tuple(other.b)] |
| dots.remove(tuple(intersect.a)) |
| dots.remove(tuple(intersect.b)) |
| return Segment(dots[0], dots[1]) |
|
|
| def angle_with(self, other): |
| return math.degrees(abs(self.angle() - other.angle())) |
|
|
| def angle_ok_with(self, other): |
| angle = self.angle_with(other) |
| return angle < 10 or abs(angle - 180) < 10 |
|
|
| def angle(self): |
| return math.atan(self.dist_y() / self.dist_x()) if self.dist_x() != 0 else math.pi / 2 |
|
|
| def intersect_all(self, segments): |
| segments_match = [] |
| for segment in segments: |
| s3 = self.intersect(segment) |
| if s3 is not None: |
| segments_match.append(s3) |
|
|
| return Segment.union_all(segments_match) |
|
|
| @staticmethod |
| def along_polygon(polygon, i, j): |
| dot1 = polygon[i][0] |
| dot2 = polygon[j][0] |
| split_segment = Segment(dot1, dot2) |
|
|
| while True: |
| i = (i - 1) % len(polygon) |
| add_segment = Segment(polygon[i][0], polygon[(i + 1) % len(polygon)][0]) |
| if add_segment.angle_ok_with(split_segment): |
| split_segment = Segment(add_segment.a, split_segment.b) |
| else: |
| break |
|
|
| while True: |
| j = (j + 1) % len(polygon) |
| add_segment = Segment(polygon[(j - 1) % len(polygon)][0], polygon[j][0]) |
| if add_segment.angle_ok_with(split_segment): |
| split_segment = Segment(split_segment.a, add_segment.b) |
| else: |
| break |
|
|
| return split_segment |
|
|
| @staticmethod |
| def union_all(segments): |
| unioned_segments = True |
| while unioned_segments: |
| unioned_segments = False |
| dedup_segments = [] |
| used = [] |
| for i, s1 in enumerate(segments): |
| for s2 in segments[i + 1:]: |
| if s2 in used: |
| continue |
|
|
| s3 = s1.union(s2) |
| if s3 is not None: |
| unioned_segments = True |
| dedup_segments += [s3] |
| used.append(s1) |
| used.append(s2) |
| break |
|
|
| if s1 not in used: |
| dedup_segments += [s1] |
|
|
| segments = dedup_segments |
|
|
| return dedup_segments |
|
|
| def projected_point(self, p): |
| a = np.array(self.a) |
| b = np.array(self.b) |
| p = np.array(p) |
| ap = p - a |
| ab = b - a |
| if ab[0] == 0 and ab[1] == 0: |
| return a |
| result = a + np.dot(ap, ab) / np.dot(ab, ab) * ab |
| return (round(result[0]), round(result[1])) |
|
|
