Coverage for bim2sim/tasks/common/inner_loop_remover.py: 38%
388 statements
« prev ^ index » next coverage.py v7.10.7, created at 2025-10-01 10:24 +0000
1"""
2This module contains functions which, given a TopoDS shapes with holes ("inner
3loops"), calculate an equivalent shape without holes by adding cuts along
4triangulation edges. Using the triangulation as a graph, it finds a spanning
5tree between the main polygon and its holes using Kruskal's algorithm
6and places the cuts along the edges of this spanning tree.
7"""
9import logging
10import math
11from collections import defaultdict
12from typing import Tuple, List, Mapping, TypeVar, Generic, Optional
14import numpy
15# Type aliases that are used throughout this module
16from OCC.Core.BRep import BRep_Tool
17from OCC.Core.BRepAlgoAPI import BRepAlgoAPI_Cut
18from OCC.Core.BRepBuilderAPI import BRepBuilderAPI_MakeEdge
19from OCC.Core.BRepExtrema import BRepExtrema_DistShapeShape
20from OCC.Core.BRepMesh import BRepMesh_IncrementalMesh
21from OCC.Core.Extrema import Extrema_ExtFlag_MIN
22from OCC.Core.TopAbs import TopAbs_FACE
23from OCC.Core.TopExp import TopExp_Explorer
24from OCC.Core.TopLoc import TopLoc_Location
25from OCC.Core.TopoDS import TopoDS_Iterator, TopoDS_Shape, topods_Face
26from OCC.Core.gp import gp_Pnt, gp_XYZ
28from bim2sim.utilities.pyocc_tools import PyOCCTools
30Vertex = Vector = Tuple[float, float, float]
31Edge = Tuple[Vertex, Vertex]
32Triangulation = List[List[Vertex]]
33Plane = Tuple[Vector, Vector, Vector]
34T = TypeVar('T')
37class _UnionFind(Generic[T]):
38 """
39 Implementation of a union-find data structure with union-by-size and path
40 compression.
41 """
43 def __init__(self):
44 self._parents = dict()
45 self._sizes = dict()
47 def union(self, element1: T, element2: T) -> T:
48 key1 = self.find(element1)
49 key2 = self.find(element2)
50 if key1 == key2:
51 return
52 if self._sizes[key1] < self._sizes[key2]:
53 key1, key2 = key2, key1
54 self._parents[key2] = key1
55 self._sizes[key1] += self._sizes[key2]
57 def find(self, element: T) -> T:
58 if element not in self._parents:
59 self._parents[element] = None
60 self._sizes[element] = 1
61 root = element
62 while self._parents[root] is not None:
63 root = self._parents[root]
64 while self._parents[element] is not None:
65 parent = self._parents[element]
66 self._parents[element] = root
67 element = parent
68 return element
71def _gp_pnt_to_coord_tuple(pnt: gp_Pnt) -> Vertex:
72 """
73 Converts a gp_Pnt instance (3D point class of OCC) to a 3-tuple, because
74 we need our vertex type to be comparable and hashable, which gp_Pnt is not.
75 """
76 return pnt.X(), pnt.Y(), pnt.Z()
79def _subshapes(shape):
80 it = TopoDS_Iterator(shape)
81 clist = []
82 while it.More():
83 clist.append(_subshapes(it.Value()))
84 it.Next()
85 return shape if len(clist) == 0 else shape, clist
88def _get_triangulation(face: TopoDS_Shape) -> Triangulation:
89 """
90 Calculates and extracts the triangulation of a TopoDS shape and returns it
91 as a list of triangles.
92 """
93 mesh = BRepMesh_IncrementalMesh(face, 0.01)
94 mesh.Perform()
95 ex = TopExp_Explorer(mesh.Shape(), TopAbs_FACE)
96 bt = BRep_Tool()
97 result = []
98 while ex.More():
99 L = TopLoc_Location()
100 triangulation = bt.Triangulation(topods_Face(ex.Current()), L)
101 if not triangulation:
102 triangulation = bt.Triangulation(PyOCCTools.make_faces_from_pnts(
103 PyOCCTools.get_points_of_face(topods_Face(ex.Current()))), L)
104 if not triangulation:
105 ex.Next()
106 triangles = triangulation.Triangles()
107 if hasattr(triangulation, 'Nodes'):
108 vertices = triangulation.Nodes()
109 else:
110 vertices = []
111 for i in range(1, triangulation.NbNodes() + 1):
112 vertices.append(triangulation.Node(i))
113 for i in range(1, triangulation.NbTriangles() + 1):
114 idx1, idx2, idx3 = triangles.Value(i).Get()
115 P1 = vertices[idx1-1].Transformed(L.Transformation())
116 P2 = vertices[idx2-1].Transformed(L.Transformation())
117 P3 = vertices[idx3-1].Transformed(L.Transformation())
118 result.append(
119 [_gp_pnt_to_coord_tuple(P1), _gp_pnt_to_coord_tuple(P2),
120 _gp_pnt_to_coord_tuple(P3)])
121 ex.Next()
122 return result
125def _normalize(edge: Edge) -> Edge:
126 """
127 Edges are normalized so that (a,b) and (b,a) are both returned as (a,b).
128 """
129 return (edge[0], edge[1]) if edge[0] < edge[1] else (edge[1], edge[0])
132def _iterate_edges(polygon: List[Vertex], directed: bool = False):
133 """
134 Constructs an iterator for iterating over all edge of the given polygon. If
135 directed is set to false, the returned edges are normalized.
136 """
137 for i in range(len(polygon)):
138 v1 = polygon[i]
139 v2 = polygon[(i + 1) % len(polygon)]
140 yield (v1, v2) if directed else _normalize((v1, v2))
143def _get_inside_outside_edges(triangulation: Triangulation, must_equal=False) \
144 -> Tuple[List[Edge], List[Edge]]:
145 """
146 Partitions all edges of the triangulation into two lists, edges that lay
147 "outside" and edges that lay "inside". Outside edges are part of the
148 boundaries of either the main polygon or one of its holes, while inside
149 edges were added by the triangulation step.
151 Outside edges are returned in their "correct" direction, inside edges are
152 not.
153 """
154 edge_count = defaultdict(int)
155 orientation = dict()
156 inside, outside = [], []
158 # We count how many times a particular edge is occuring in the
159 # triangulation, because every inside edge is part of two triangles,
160 # while edges laying on the polygon boundaries are only part of a
161 # single triangulation.
162 for triangle in triangulation:
163 for edge in _iterate_edges(triangle, True):
164 edge_count[_normalize(edge)] += 1
165 orientation[_normalize(edge)] = edge
166 for edge, count in edge_count.items():
167 if count == 1:
168 outside.append(orientation[edge])
169 else:
170 inside.append(edge)
171 if must_equal:
172 assert len(inside) == len(outside)
173 return inside, outside
176def _get_jump_map(cut_edges: List[Edge], out_edges: List[Edge], plane: Plane) \
177 -> Mapping[Vertex, List[Vertex]]:
178 """
179 Constructs a jump map based on a list on cut edges, so that for every edge
180 (a,b), map[a] contains b and map[b] contains a.
182 Things get complicated when we have more than one entry for a vertex, which
183 is the case when more than one edge in the spanning tree are incident to a
184 vertex. Then we have to order the entries in clockwise order so that the
185 polygon reconstruction builds a valid polygon that does not self-intersect.
186 This is ALSO complicated by the fact that we are in 3 dimensions (which we
187 could ignore until now), but at least we can assume that all input points
188 lie in a common plane. Ordering the entries is done in _order_points_cw.
189 """
190 out_dest = dict()
191 for edge in out_edges:
192 out_dest[edge[0]] = edge[1]
194 jump_map = defaultdict(list)
195 for edge in cut_edges:
196 jump_map[edge[0]].append(edge[1])
197 jump_map[edge[1]].append(edge[0])
199 for key, values in jump_map.items():
200 if len(values) <= 1:
201 continue
202 jump_map[key] = _order_points_cw(plane, key, out_dest[key], values)
203 return jump_map
206def _order_points_cw(plane: Plane, mid: Vector, control: Vector,
207 vertices: List[Vertex]) -> List[Vertex]:
208 """
209 Based on:
210 https://stackoverflow.com/questions/47949485/sorting-a-list-of-3d-points-in-clockwise-order
212 To sort points laying in a plane in 3D space in clockwise order around a
213 given origin m, we have to
215 1. find the normal vector n of this plane
216 2. find vectors p, q in our plane such that n, p, q are perpendicular
217 to each other and form a right-handed system.
218 3. Calculate for every vertex v the triple products u = n * ((v-m) x p)
219 and t = n * ((v-m) x q) to obtain a sort key of atan2(u, t).
221 We take n, p and q as arguments because we just have to calculate them once.
223 We also take a control vector, which is also sorted alongside the other
224 vertices. The result is then shifted so that the control vector is the first
225 element in the result list. The control vector is not included in the
226 returned list.
227 """
228 n, p, q = plane
230 def sort_key(v: Vertex) -> float:
231 t = numpy.dot(n, numpy.cross(numpy.subtract(v, mid), p))
232 u = numpy.dot(n, numpy.cross(numpy.subtract(v, mid), q))
233 return math.atan2(u, t)
235 s = sorted([control] + vertices, key=sort_key)
236 roll = s.index(control)
237 rolled = s[roll:] + s[:roll]
238 return rolled[1:]
241def _calculate_plane_vectors(vertices: List[Vertex]) -> Plane:
242 """
243 Calculates n, p and q describing the plane the input values lie in. More
244 info see _order_points_cw.
245 """
246 a, b, c = vertices
247 d = numpy.cross(numpy.subtract(b, a), numpy.subtract(c, a))
248 n = numpy.divide(d, numpy.linalg.norm(d))
250 # We try two different unit vectors for the case that n and the first chosen unit vector are
251 # parallel.
252 p = (0, 0, 0)
253 for uvec in [(1, 0, 0), (0, 1, 0)]:
254 np = numpy.cross(uvec, n)
255 if numpy.linalg.norm(p) < numpy.linalg.norm(np):
256 p = np
257 q = numpy.cross(n, p)
259 return tuple(n), tuple(p), tuple(q)
262def _reconstruct_polygons(edges: List[Edge]) -> List[List[Vertex]]:
263 """
264 Takes a list of edges in any order and reconstructs the correctly ordered
265 vertices of the polygons formed by the given edges. It is assumed that the
266 edges in the input are reconstructable to some list of polygons.
267 """
268 result = []
269 chain = dict()
270 for edge in edges:
271 chain[edge[0]] = edge[1]
272 while len(chain) > 0:
273 start = next(
274 iter(chain)) # use any key in the chain, we don't care which.
275 polygon = []
276 key = start
277 first = True
278 while key != start or first:
279 first = False
280 polygon.append(key)
281 next_key = chain[key]
282 del chain[key]
283 key = next_key
284 result.append(polygon)
285 return result
288def _index_polygon_vertices(polygons: List[List[Vertex]]) -> Mapping[
289 Vertex, Tuple[int, int]]:
290 """
291 Build a index map where map[v] = (i,j) <=> polygons[i][j] = v.
292 """
293 index = dict()
294 for pIdx, polygon in enumerate(polygons):
295 for vIdx, vertex in enumerate(polygon):
296 index[vertex] = (pIdx, vIdx)
297 return index
300def _reconstruct_cut_polygon(out_edges: List[Edge], cut_edges: List[Edge],
301 plane: Plane) -> List[Vertex]:
302 """
303 Takes a list of outside edges and a list of cut edges and reconstructs the
304 single polygon they form.
305 """
306 polygons = _reconstruct_polygons(out_edges)
307 jump = dict(_get_jump_map(cut_edges, out_edges, plane))
308 poly_index = _index_polygon_vertices(polygons)
310 # Finds the index of the first vertex we can start on. We only start on
311 # vertices that don't have any jumps to make the exit condition of our main
312 # loop simpler. It is guaranteed that such a vertex exists (edges in a
313 # spanning tree over all polygons < 3 * vertices in all polygons).
314 def find_start_index():
315 for i1, polygon in enumerate(polygons):
316 for i2, vertex in enumerate(polygon):
317 if vertex not in jump:
318 return i1, i2
320 cut_polygon = []
321 start_index = find_start_index()
322 idx = start_index
323 last_jump_source: Optional[Vertex] = None
325 while True:
326 current = polygons[idx[0]][idx[1]]
327 cut_polygon.append(current)
328 assert len(cut_polygon) <= len(
329 out_edges) * 2, "Infinite loop detected. Arguments are not right."
331 # We find out if we have to jump to another polygon. If yes, this
332 # variable will be set to the index of the jump list of our current
333 # vertex to where we have to jump.
334 jump_list_index = None
335 if current in jump:
336 # There are jumps for the current vertex. Check if we already jumped
337 # the last time.
338 if last_jump_source is None:
339 # ... no, so just jump to the last (= first in ccw order) entry
340 # in the jump list.
341 jump_list_index = -1
342 else:
343 # ... yes, so we have to jump to the first entry BEFORE the one
344 # (= first after in ccw order)
345 # we just came from. If we already came from the first entry, we
346 # instead start to traverse
347 # the current polygon.
348 last_jump_index = jump[current].index(last_jump_source)
349 if last_jump_index > 0:
350 jump_list_index = last_jump_index - 1
352 if jump_list_index is not None:
353 jump_vertex = jump[current][jump_list_index]
354 idx = poly_index[jump_vertex]
355 last_jump_source = current
356 else:
357 last_jump_source = None
358 idx = (idx[0], (idx[1] + 1) % len(polygons[idx[0]]))
360 # Because we started on a vertex that has no jumps, the start vertex can
361 # only be visited once during polygon reconstruction. Therefore, if we
362 # arrive at our start index a second time we are done.
363 if idx == start_index:
364 break
366 return cut_polygon
369def remove_inner_loops(shape: TopoDS_Shape) -> TopoDS_Shape:
370 # Build all necessary data structures.
371 triangulation = _get_triangulation(shape)
372 in_edges, out_edges = _get_inside_outside_edges(triangulation)
373 partition = _UnionFind()
375 plane = _calculate_plane_vectors(triangulation[0])
377 # Build initial partition state. After that, every loop (either the main
378 # polygon or a hole)
379 # is in its own disjoint set.
380 for edge in out_edges:
381 partition.union(edge[0], edge[1])
383 # We now find a spanning tree by applying Kruskal's algorithm to the
384 # triangulation graph. Note that in an unweighted graph, every spanning
385 # tree is a minimal spanning tree, so it doesn't actually matter which
386 # spanning tree we are calculating here. Edges that are part of the
387 # spanning tree are pushed into cut_edges.
388 cut_edges = []
389 for edge in in_edges:
390 if partition.find(edge[0]) != partition.find(edge[1]):
391 cut_edges.append(edge)
392 partition.union(edge[0], edge[1])
394 cut_polygon = _reconstruct_cut_polygon(out_edges, cut_edges, plane)
395 new_shape = PyOCCTools.make_faces_from_pnts(cut_polygon)
397 # Copy over shape location
398 # shape_loc = TopoDS_Iterator(shape).Value().Location()
399 # new_shape.Move(shape_loc)
401 return new_shape
404def _cross(a: Vertex, b: Vertex) -> Vertex:
405 return a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - \
406 a[1] * b[0]
409def _dot(a: Vertex, b: Vertex) -> float:
410 return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
413def _minus(a: Vertex, b: Vertex) -> Vertex:
414 return a[0] - b[0], a[1] - b[1], a[2] - b[2]
417def _is_convex_angle(p1: Vertex, p2: Vertex, p3: Vertex,
418 normal: Vertex) -> bool:
419 cross = _cross(_minus(p2, p1), _minus(p3, p1))
420 return _dot(cross, normal) >= -1e-6
423def fuse_pieces(pieces: List[List[Vertex]],
424 shapes_to_consider: List[TopoDS_Shape] = []) -> List[
425 List[Vertex]]:
426 normal, _, _ = _calculate_plane_vectors(pieces[0])
427 consider_polygons = False
429 if len(shapes_to_consider) > 0:
430 consider_polygons = True
431 edges = []
432 for shape in shapes_to_consider:
433 list_pnts = PyOCCTools.get_points_of_face(shape)
434 for i, p in enumerate(list_pnts[:-1]):
435 edges.append(BRepBuilderAPI_MakeEdge(list_pnts[i],
436 list_pnts[i + 1]).Shape())
437 edges.append(
438 BRepBuilderAPI_MakeEdge(list_pnts[-1], list_pnts[0]).Shape())
440 i1 = 0
441 while i1 < len(pieces) - 1:
442 piece_a = pieces[i1]
443 i1 += 1
444 for piece_a_idx in range(0, len(piece_a)):
445 a1 = piece_a[piece_a_idx]
446 a2 = piece_a[(piece_a_idx + 1) % len(piece_a)]
448 is_inner_edge = False
449 piece_b = None
450 piece_b_idx = None
451 for i2 in range(i1, len(pieces)):
452 piece_b = pieces[i2]
453 for triangle_b_check_idx in range(0, len(piece_b)):
454 if a2 != piece_b[triangle_b_check_idx]:
455 continue
456 if a1 != piece_b[(triangle_b_check_idx + 1) % len(piece_b)]:
457 continue
458 piece_b_idx = triangle_b_check_idx
459 is_inner_edge = True
460 break
461 if is_inner_edge:
462 break
463 if not is_inner_edge:
464 continue
466 # piece_a and piece_b are two triangles with a common edge (piece_a
467 # and piece_b)
468 # common edge is spanned between a1 and a2
469 p1 = piece_a[(piece_a_idx - 1) % len(piece_a)]
470 p2 = a1
471 p3 = piece_b[(piece_b_idx + 2) % len(piece_b)]
473 if not consider_polygons:
474 # if no polygons need to be considered, shapes are fused
475 # unless resulting shape is non-convex
476 if not _is_convex_angle(p1, p2, p3, normal):
477 continue
478 else:
479 # if an edge from triangulation cuts the edge of a polygon
480 # which needs to be considered (e.g. from an opening boundary
481 # within a boundary of a wall), then those shapes have to be
482 # fused regardless of the resulting angle
483 # this may lead to non-convex shapes in some cases
484 a1_edge = BRepBuilderAPI_MakeEdge(gp_Pnt(*a1),
485 gp_Pnt(*a2)).Shape()
486 continue_flag = True
487 for edge in edges:
488 if BRepExtrema_DistShapeShape(
489 edge, a1_edge, Extrema_ExtFlag_MIN).Value() < 1e-3:
490 continue_flag = False
491 else:
492 pass
493 if continue_flag:
494 continue
496 # procedure is repeated for common edge of neighboring shape
497 p1 = piece_b[(piece_b_idx - 1) % len(piece_b)]
498 p2 = a2
499 p3 = piece_a[(piece_a_idx + 2) % len(piece_a)]
500 if not consider_polygons:
501 if not _is_convex_angle(p1, p2, p3, normal):
502 continue
503 else:
504 a2_edge = BRepBuilderAPI_MakeEdge(gp_Pnt(*a2),
505 gp_Pnt(*a1)).Shape()
506 continue_flag = True
507 for edge in edges:
508 if BRepExtrema_DistShapeShape(
509 edge, a2_edge, Extrema_ExtFlag_MIN).Value() < 1e-3:
510 continue_flag = False
511 else:
512 pass
513 if continue_flag:
514 continue
515 # fuse triangles (if angle is convex or opening-polygon is cut by
516 # this edge
517 fused_piece = []
518 i = (piece_a_idx + 1) % len(piece_a)
519 while i != piece_a_idx:
520 fused_piece.append(piece_a[i])
521 i = (i + 1) % len(piece_a)
522 i = (piece_b_idx + 1) % len(piece_b)
523 while i != piece_b_idx:
524 fused_piece.append(piece_b[i])
525 i = (i + 1) % len(piece_b)
527 i1 -= 1
528 pieces.remove(piece_a)
529 pieces.remove(piece_b)
530 pieces.insert(i1, fused_piece)
531 piece_a = fused_piece
532 break
533 return pieces
536def convex_decomposition_base(shape: TopoDS_Shape,
537 opening_shapes: List[TopoDS_Shape] = []) -> List[
538 List[Vertex]]:
539 """Convex decomposition base: removes common edges of triangles unless a
540 non-convex shape is created.
541 In case of openings: In a first round, remove all cutting triangle edges
542 with the opening polygons regardless of non-convex shapes.
543 Then, check for resulting angles. This may lead to non-convex shapes,
544 but should work in most cases.
545 """
546 pieces = _get_triangulation(shape)
547 if len(opening_shapes) > 0:
548 pieces = fuse_pieces(pieces, opening_shapes)
549 pieces = fuse_pieces(pieces)
551 return pieces
554def convex_decomposition(shape: TopoDS_Shape,
555 opening_shapes: List[TopoDS_Shape] = []) -> List[
556 TopoDS_Shape]:
557 pieces = convex_decomposition_base(shape, opening_shapes)
558 pieces_area = 0
559 new_area = 0
560 new_pieces = []
561 for p in pieces:
562 pieces_area += PyOCCTools.get_shape_area(
563 PyOCCTools.make_faces_from_pnts(p))
564 pnt_list_new = PyOCCTools.remove_coincident_vertices(
565 [gp_XYZ(pnt[0], pnt[1], pnt[2]) for pnt in p])
566 pnt_list_new = PyOCCTools.remove_collinear_vertices2(pnt_list_new)
567 if pnt_list_new != p and len(pnt_list_new) > 3:
568 pnt_list_new = [n.Coord() for n in pnt_list_new]
569 p = pnt_list_new
570 new_pieces.append(p)
571 new_area += PyOCCTools.get_shape_area(
572 PyOCCTools.make_faces_from_pnts(p))
573 if abs(pieces_area - new_area) > 1e-3:
574 new_pieces = pieces
575 new_shapes = list(
576 map(lambda p: PyOCCTools.make_faces_from_pnts(p), new_pieces))
577 oriented_shapes = []
578 org_normal = PyOCCTools.simple_face_normal(shape)
579 for new_shape in new_shapes:
580 new_normal = PyOCCTools.simple_face_normal(new_shape)
581 if all([abs(i) < 1e-3 for i in ((new_normal - org_normal).Coord())]):
582 oriented_shapes.append(new_shape)
583 else:
584 new_shape = PyOCCTools.flip_orientation_of_face(new_shape)
585 new_normal = PyOCCTools.simple_face_normal(new_shape)
586 if all([abs(i) < 1e-3 for i in
587 ((new_normal - org_normal).Coord())]):
588 oriented_shapes.append(new_shape)
589 else:
590 logger = logging.getLogger(__name__)
591 logger.error(
592 "Convex decomposition produces a gap in new space boundary")
593 # check if decomposed shape has same area as original shape
594 oriented_area = 0
595 org_area = PyOCCTools.get_shape_area(shape)
596 for face in oriented_shapes:
597 oriented_area += PyOCCTools.get_shape_area(face)
598 cut_count = 0
599 while abs(org_area - oriented_area) > 5e-3:
600 cut_count += 1
601 cut_shape = shape
602 for bound in oriented_shapes:
603 cut_shape = BRepAlgoAPI_Cut(cut_shape, bound).Shape()
604 list_cut_shapes = PyOCCTools.get_faces_from_shape(cut_shape)
605 add_cut_shapes = []
606 for cs in list_cut_shapes:
607 new_normal = PyOCCTools.simple_face_normal(cs)
608 if not all([abs(i) < 1e-3 for i in
609 ((new_normal - org_normal).Coord())]):
610 cs = PyOCCTools.flip_orientation_of_face(cs)
611 cut_area = PyOCCTools.get_shape_area(cs)
612 if cut_area < 5e-4:
613 continue
614 cs = PyOCCTools.remove_coincident_and_collinear_points_from_face(cs)
615 oriented_area += cut_area
616 add_cut_shapes.append(cs)
617 if cut_count > 3:
618 logger = logging.getLogger(__name__)
619 logger.error(
620 "Convex decomposition produces a gap in new space boundary")
621 break
622 else:
623 oriented_shapes.extend(add_cut_shapes)
624 return oriented_shapes
627def is_convex_slow(shape: TopoDS_Shape) -> bool:
628 """
629 Computational expensive check if a TopoDS_Shape is convex.
630 Args:
631 shape: TopoDS_Shape
633 Returns:
634 bool, True if shape is convex.
635 """
636 return len(convex_decomposition_base(shape)) == 1
639def is_convex_no_holes(shape: TopoDS_Shape) -> bool:
640 """check if TopoDS_Shape is convex. Returns False if shape is non-convex"""
641 gp_pnts = PyOCCTools.get_points_of_face(shape)
642 pnts = list(map(lambda p: _gp_pnt_to_coord_tuple(p), gp_pnts))
643 z = 0
644 for i in range(0, len(pnts)):
645 p0 = pnts[i]
646 p1 = pnts[(i + 1) % len(pnts)]
647 p2 = pnts[(i + 2) % len(pnts)]
648 cross = _cross(_minus(p1, p0), _minus(p2, p1))[2]
649 if z != 0 and abs(cross) >= 1e-6 and numpy.sign(cross) != numpy.sign(z):
650 return False
651 else:
652 z = cross
653 return True
656def is_polygon_convex_no_holes(pnts: List[Tuple[float, float, float]]) -> bool:
657 """check if polygon made from tuples of floats is convex.
658 Returns False if shape is non-convex"""
659 z = 0
660 for i in range(0, len(pnts)):
661 p0 = pnts[i]
662 p1 = pnts[(i + 1) % len(pnts)]
663 p2 = pnts[(i + 2) % len(pnts)]
664 cross = _cross(_minus(p1, p0), _minus(p2, p1))[2]
665 if z != 0 and abs(cross) >= 1e-6 and numpy.sign(cross) != numpy.sign(z):
666 return False
667 else:
668 z = cross
669 return True