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