1# Copyright (c) 2010-2021, Manfred Moitzi 2# License: MIT License 3from typing import TYPE_CHECKING, Iterable, List, Union 4 5from functools import partial 6import math 7import warnings 8from ezdxf.math import Vec3, Vec2 9from decimal import Decimal 10 11if TYPE_CHECKING: 12 from ezdxf.eztypes import Vertex 13 14TOLERANCE = 1e-10 15RADIANS_90 = math.pi / 2.0 16RADIANS_180 = math.pi 17RADIANS_270 = RADIANS_90 * 3.0 18RADIANS_360 = 2.0 * math.pi 19 20__all__ = [ 21 "is_close_points", "closest_point", "convex_hull_2d", 22 "distance_point_line_2d", "is_point_on_line_2d", "is_point_in_polygon_2d", 23 "is_point_left_of_line", "point_to_line_relation", "linspace", 24 "enclosing_angles", "reflect_angle_x_deg", "reflect_angle_y_deg", 25 "sign", "area", "circle_radius_3p" 26] 27 28 29def is_close_points(p1: 'Vertex', p2: 'Vertex', abs_tol=TOLERANCE) -> bool: 30 """ Deprecated function will be removed in v0.18! Use Vec(p1).isclose(p2). 31 """ 32 warnings.warn("Deprecated function will be removed in v0.18! " 33 "Use Vec3(p1).isclose(p2).", DeprecationWarning) 34 return Vec3(p1).isclose(p2, abs_tol=abs_tol) 35 36 37def linspace(start: float, stop: float, num: int, 38 endpoint=True) -> Iterable[float]: 39 """ Return evenly spaced numbers over a specified interval, like 40 numpy.linspace(). 41 42 Returns `num` evenly spaced samples, calculated over the interval 43 [start, stop]. The endpoint of the interval can optionally be excluded. 44 45 """ 46 if num < 0: 47 raise ValueError(f'Number of samples, {num}, must be non-negative.') 48 elif num == 0: 49 return 50 elif num == 1: 51 yield start 52 return 53 54 start = Decimal(start) 55 count = (num - 1) if endpoint else num 56 delta = (Decimal(stop) - start) / count 57 for _ in range(num): 58 yield float(start) 59 start += delta 60 61 62def sign(f: float) -> float: 63 """ Return sign of float `f` as -1 or +1, 0 returns +1 """ 64 return -1.0 if f < 0.0 else +1.0 65 66 67def reflect_angle_x_deg(a: float) -> float: 68 """ Returns reflected angle of `a` in x-direction in degrees. 69 Angles are counter clockwise orientated and +x-axis is at 0 degrees. 70 71 Args: 72 a: angle to reflect in degrees 73 74 """ 75 return (180. - (a % 360.)) % 360. 76 77 78def reflect_angle_y_deg(a: float) -> float: 79 """ Returns reflected angle of `a` in y-direction in degrees. 80 Angles are counter clockwise orientated and +y-axis is at 90 degrees. 81 82 Args: 83 a: angle to reflect in degrees 84 85 """ 86 return (360. - (a % 360.)) % 360. 87 88 89def closest_point(base: 'Vertex', points: Iterable['Vertex']) -> 'Vec3': 90 """ Returns closest point to `base`. 91 92 Args: 93 base: base point as :class:`Vec3` compatible object 94 points: iterable of points as :class:`Vec3` compatible object 95 96 """ 97 base = Vec3(base) 98 min_dist = None 99 found = None 100 for point in points: 101 p = Vec3(point) 102 dist = (base - p).magnitude 103 if (min_dist is None) or (dist < min_dist): 104 min_dist = dist 105 found = p 106 return found 107 108 109def convex_hull_2d(points: Iterable['Vertex']) -> List['Vertex']: 110 """ Returns 2D convex hull for `points`. 111 112 Args: 113 points: iterable of points as :class:`Vec3` compatible objects, 114 z-axis is ignored 115 116 """ 117 118 def _convexhull(hull): 119 while len(hull) > 2: 120 # the last three points 121 start_point, check_point, destination_point = hull[-3:] 122 # curve not turns right 123 if not is_point_left_of_line(check_point, start_point, 124 destination_point): 125 # remove the penultimate point 126 del hull[-2] 127 else: 128 break 129 return hull 130 131 points = sorted(set(Vec2.generate(points))) # remove duplicate points 132 133 if len(points) < 3: 134 raise ValueError( 135 "Convex hull calculation requires 3 or more unique points.") 136 137 upper_hull = points[:2] # first two points 138 for next_point in points[2:]: 139 upper_hull.append(next_point) 140 upper_hull = _convexhull(upper_hull) 141 lower_hull = [points[-1], points[-2]] # last two points 142 143 for next_point in reversed(points[:-2]): 144 lower_hull.append(next_point) 145 lower_hull = _convexhull(lower_hull) 146 upper_hull.extend(lower_hull[1:-1]) 147 return upper_hull 148 149 150def enclosing_angles(angle, start_angle, end_angle, ccw=True, 151 abs_tol=TOLERANCE): 152 isclose = partial(math.isclose, abs_tol=abs_tol) 153 154 s = start_angle % math.tau 155 e = end_angle % math.tau 156 a = angle % math.tau 157 if isclose(s, e): 158 return isclose(s, a) 159 160 if s < e: 161 r = s < a < e 162 else: 163 r = not (e < a < s) 164 return r if ccw else not r 165 166 167def is_point_on_line_2d(point: Vec2, start: Vec2, end: Vec2, ray=True, 168 abs_tol=TOLERANCE) -> bool: 169 """ Returns ``True`` if `point` is on `line`. 170 171 Args: 172 point: 2D point to test as :class:`Vec2` 173 start: line definition point as :class:`Vec2` 174 end: line definition point as :class:`Vec2` 175 ray: if ``True`` point has to be on the infinite ray, if ``False`` 176 point has to be on the line segment 177 abs_tol: tolerance for on line test 178 179 """ 180 point_x, point_y = point 181 start_x, start_y = start 182 end_x, end_y = end 183 on_line = math.fabs( 184 (end_y - start_y) * point_x - (end_x - start_x) * point_y + ( 185 end_x * start_y - end_y * start_x)) <= abs_tol 186 if not on_line or ray: 187 return on_line 188 else: 189 if start_x > end_x: 190 start_x, end_x = end_x, start_x 191 if not (start_x - abs_tol <= point_x <= end_x + abs_tol): 192 return False 193 if start_y > end_y: 194 start_y, end_y = end_y, start_y 195 if not (start_y - abs_tol <= point_y <= end_y + abs_tol): 196 return False 197 return True 198 199 200def point_to_line_relation(point: Vec2, start: Vec2, end: Vec2, 201 abs_tol=TOLERANCE) -> int: 202 """ Returns ``-1`` if `point` is left `line`, ``+1`` if `point` is right of 203 `line` and ``0`` if `point` is on the `line`. The `line` is defined by two 204 vertices given as arguments `start` and `end`. 205 206 Args: 207 point: 2D point to test as :class:`Vec2` 208 start: line definition point as :class:`Vec2` 209 end: line definition point as :class:`Vec2` 210 abs_tol: tolerance for minimum distance to line 211 212 """ 213 rel = (end.x - start.x) * (point.y - start.y) - (end.y - start.y) * ( 214 point.x - start.x) 215 if abs(rel) <= abs_tol: 216 return 0 217 elif rel < 0: 218 return +1 219 else: 220 return -1 221 222 223def is_point_left_of_line(point: Vec2, start: Vec2, end: Vec2, 224 colinear=False) -> bool: 225 """ Returns ``True`` if `point` is "left of line" defined by `start-` and 226 `end` point, a colinear point is also "left of line" if argument `colinear` 227 is ``True``. 228 229 Args: 230 point: 2D point to test as :class:`Vec2` 231 start: line definition point as :class:`Vec2` 232 end: line definition point as :class:`Vec2` 233 colinear: a colinear point is also "left of line" if ``True`` 234 235 """ 236 rel = point_to_line_relation(point, start, end) 237 if colinear: 238 return rel < 1 239 else: 240 return rel < 0 241 242 243def distance_point_line_2d(point: Vec2, start: Vec2, end: Vec2) -> float: 244 """ Returns the normal distance from `point` to 2D line defined by `start-` 245 and `end` point. 246 """ 247 # wikipedia: https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line. 248 if start.isclose(end): 249 raise ZeroDivisionError('Not a line.') 250 return math.fabs((start - point).det(end - point)) / (end - start).magnitude 251 252 253def is_point_in_polygon_2d(point: Union[Vec2, Vec3], polygon: Iterable[Vec2], 254 abs_tol=TOLERANCE) -> int: 255 """ Test if `point` is inside `polygon`. 256 257 Args: 258 point: 2D point to test as :class:`Vec2` 259 polygon: iterable of 2D points as :class:`Vec2` 260 abs_tol: tolerance for distance check 261 262 Returns: 263 ``+1`` for inside, ``0`` for on boundary line, ``-1`` for outside 264 265 """ 266 # Source: http://www.faqs.org/faqs/graphics/algorithms-faq/ 267 # Subject 2.03: How do I find if a point lies within a polygon? 268 polygon = list(polygon) # shallow copy, because list will be modified 269 if not polygon[0].isclose(polygon[-1]): 270 polygon.append(polygon[0]) 271 if len(polygon) < 4: # 3+1 because first point == last point 272 raise ValueError('At least 3 polygon points required.') 273 x = point.x 274 y = point.y 275 # ignore z-axis of Vec3() 276 inside = False 277 for i in range(len(polygon) - 1): 278 x1, y1 = polygon[i] 279 x2, y2 = polygon[i + 1] 280 # is point on polygon boundary line: 281 # is point in x-range of line 282 a, b = (x2, x1) if x2 < x1 else (x1, x2) 283 if a <= x <= b: 284 # is point in y-range of line 285 c, d = (y2, y1) if y2 < y1 else (y1, y2) 286 if (c <= y <= d) and math.fabs((y2 - y1) * x - (x2 - x1) * y + ( 287 x2 * y1 - y2 * x1)) <= abs_tol: 288 return 0 289 if ((y1 <= y < y2) or (y2 <= y < y1)) and ( 290 x < (x2 - x1) * (y - y1) / (y2 - y1) + x1): 291 inside = not inside 292 if inside: 293 return 1 294 else: 295 return -1 296 297 298def circle_radius_3p(a: Vec3, b: Vec3, c: Vec3) -> float: 299 ba = b - a 300 ca = c - a 301 cb = c - b 302 upper = ba.magnitude * ca.magnitude * cb.magnitude 303 lower = ba.cross(ca).magnitude * 2.0 304 return upper / lower 305 306 307def area(vertices: Iterable['Vertex']) -> float: 308 """ Returns the area of a polygon, returns the projected area in the 309 xy-plane for 3D vertices. 310 """ 311 vertices = Vec3.list(vertices) 312 if len(vertices) < 3: 313 raise ValueError('At least 3 vertices required.') 314 315 # Close polygon: 316 if not vertices[0].isclose(vertices[-1]): 317 vertices.append(vertices[0]) 318 319 return abs(sum( 320 (p1.x * p2.y - p1.y * p2.x) for p1, p2 in zip(vertices, vertices[1:]) 321 ) / 2) 322