Coverage for bim2sim/tasks/common/inner_loop_remover.py: 38%
386 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-03-12 17:09 +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) -> Tuple[
144 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 return inside, outside
174def _get_jump_map(cut_edges: List[Edge], out_edges: List[Edge], plane: Plane) \
175 -> Mapping[Vertex, List[Vertex]]:
176 """
177 Constructs a jump map based on a list on cut edges, so that for every edge
178 (a,b), map[a] contains b and map[b] contains a.
180 Things get complicated when we have more than one entry for a vertex, which
181 is the case when more than one edge in the spanning tree are incident to a
182 vertex. Then we have to order the entries in clockwise order so that the
183 polygon reconstruction builds a valid polygon that does not self-intersect.
184 This is ALSO complicated by the fact that we are in 3 dimensions (which we
185 could ignore until now), but at least we can assume that all input points
186 lie in a common plane. Ordering the entries is done in _order_points_cw.
187 """
188 out_dest = dict()
189 for edge in out_edges:
190 out_dest[edge[0]] = edge[1]
192 jump_map = defaultdict(list)
193 for edge in cut_edges:
194 jump_map[edge[0]].append(edge[1])
195 jump_map[edge[1]].append(edge[0])
197 for key, values in jump_map.items():
198 if len(values) <= 1:
199 continue
200 jump_map[key] = _order_points_cw(plane, key, out_dest[key], values)
201 return jump_map
204def _order_points_cw(plane: Plane, mid: Vector, control: Vector,
205 vertices: List[Vertex]) -> List[Vertex]:
206 """
207 Based on:
208 https://stackoverflow.com/questions/47949485/sorting-a-list-of-3d-points-in-clockwise-order
210 To sort points laying in a plane in 3D space in clockwise order around a
211 given origin m, we have to
213 1. find the normal vector n of this plane
214 2. find vectors p, q in our plane such that n, p, q are perpendicular
215 to each other and form a right-handed system.
216 3. Calculate for every vertex v the triple products u = n * ((v-m) x p)
217 and t = n * ((v-m) x q) to obtain a sort key of atan2(u, t).
219 We take n, p and q as arguments because we just have to calculate them once.
221 We also take a control vector, which is also sorted alongside the other
222 vertices. The result is then shifted so that the control vector is the first
223 element in the result list. The control vector is not included in the
224 returned list.
225 """
226 n, p, q = plane
228 def sort_key(v: Vertex) -> float:
229 t = numpy.dot(n, numpy.cross(numpy.subtract(v, mid), p))
230 u = numpy.dot(n, numpy.cross(numpy.subtract(v, mid), q))
231 return math.atan2(u, t)
233 s = sorted([control] + vertices, key=sort_key)
234 roll = s.index(control)
235 rolled = s[roll:] + s[:roll]
236 return rolled[1:]
239def _calculate_plane_vectors(vertices: List[Vertex]) -> Plane:
240 """
241 Calculates n, p and q describing the plane the input values lie in. More
242 info see _order_points_cw.
243 """
244 a, b, c = vertices
245 d = numpy.cross(numpy.subtract(b, a), numpy.subtract(c, a))
246 n = numpy.divide(d, numpy.linalg.norm(d))
248 # We try two different unit vectors for the case that n and the first chosen unit vector are
249 # parallel.
250 p = (0, 0, 0)
251 for uvec in [(1, 0, 0), (0, 1, 0)]:
252 np = numpy.cross(uvec, n)
253 if numpy.linalg.norm(p) < numpy.linalg.norm(np):
254 p = np
255 q = numpy.cross(n, p)
257 return tuple(n), tuple(p), tuple(q)
260def _reconstruct_polygons(edges: List[Edge]) -> List[List[Vertex]]:
261 """
262 Takes a list of edges in any order and reconstructs the correctly ordered
263 vertices of the polygons formed by the given edges. It is assumed that the
264 edges in the input are reconstructable to some list of polygons.
265 """
266 result = []
267 chain = dict()
268 for edge in edges:
269 chain[edge[0]] = edge[1]
270 while len(chain) > 0:
271 start = next(
272 iter(chain)) # use any key in the chain, we don't care which.
273 polygon = []
274 key = start
275 first = True
276 while key != start or first:
277 first = False
278 polygon.append(key)
279 next_key = chain[key]
280 del chain[key]
281 key = next_key
282 result.append(polygon)
283 return result
286def _index_polygon_vertices(polygons: List[List[Vertex]]) -> Mapping[
287 Vertex, Tuple[int, int]]:
288 """
289 Build a index map where map[v] = (i,j) <=> polygons[i][j] = v.
290 """
291 index = dict()
292 for pIdx, polygon in enumerate(polygons):
293 for vIdx, vertex in enumerate(polygon):
294 index[vertex] = (pIdx, vIdx)
295 return index
298def _reconstruct_cut_polygon(out_edges: List[Edge], cut_edges: List[Edge],
299 plane: Plane) -> List[Vertex]:
300 """
301 Takes a list of outside edges and a list of cut edges and reconstructs the
302 single polygon they form.
303 """
304 polygons = _reconstruct_polygons(out_edges)
305 jump = dict(_get_jump_map(cut_edges, out_edges, plane))
306 poly_index = _index_polygon_vertices(polygons)
308 # Finds the index of the first vertex we can start on. We only start on
309 # vertices that don't have any jumps to make the exit condition of our main
310 # loop simpler. It is guaranteed that such a vertex exists (edges in a
311 # spanning tree over all polygons < 3 * vertices in all polygons).
312 def find_start_index():
313 for i1, polygon in enumerate(polygons):
314 for i2, vertex in enumerate(polygon):
315 if vertex not in jump:
316 return i1, i2
318 cut_polygon = []
319 start_index = find_start_index()
320 idx = start_index
321 last_jump_source: Optional[Vertex] = None
323 while True:
324 current = polygons[idx[0]][idx[1]]
325 cut_polygon.append(current)
326 assert len(cut_polygon) <= len(
327 out_edges) * 2, "Infinite loop detected. Arguments are not right."
329 # We find out if we have to jump to another polygon. If yes, this
330 # variable will be set to the index of the jump list of our current
331 # vertex to where we have to jump.
332 jump_list_index = None
333 if current in jump:
334 # There are jumps for the current vertex. Check if we already jumped
335 # the last time.
336 if last_jump_source is None:
337 # ... no, so just jump to the last (= first in ccw order) entry
338 # in the jump list.
339 jump_list_index = -1
340 else:
341 # ... yes, so we have to jump to the first entry BEFORE the one
342 # (= first after in ccw order)
343 # we just came from. If we already came from the first entry, we
344 # instead start to traverse
345 # the current polygon.
346 last_jump_index = jump[current].index(last_jump_source)
347 if last_jump_index > 0:
348 jump_list_index = last_jump_index - 1
350 if jump_list_index is not None:
351 jump_vertex = jump[current][jump_list_index]
352 idx = poly_index[jump_vertex]
353 last_jump_source = current
354 else:
355 last_jump_source = None
356 idx = (idx[0], (idx[1] + 1) % len(polygons[idx[0]]))
358 # Because we started on a vertex that has no jumps, the start vertex can
359 # only be visited once during polygon reconstruction. Therefore, if we
360 # arrive at our start index a second time we are done.
361 if idx == start_index:
362 break
364 return cut_polygon
367def remove_inner_loops(shape: TopoDS_Shape) -> TopoDS_Shape:
368 # Build all necessary data structures.
369 triangulation = _get_triangulation(shape)
370 in_edges, out_edges = _get_inside_outside_edges(triangulation)
371 partition = _UnionFind()
373 plane = _calculate_plane_vectors(triangulation[0])
375 # Build initial partition state. After that, every loop (either the main
376 # polygon or a hole)
377 # is in its own disjoint set.
378 for edge in out_edges:
379 partition.union(edge[0], edge[1])
381 # We now find a spanning tree by applying Kruskal's algorithm to the
382 # triangulation graph. Note that in an unweighted graph, every spanning
383 # tree is a minimal spanning tree, so it doesn't actually matter which
384 # spanning tree we are calculating here. Edges that are part of the
385 # spanning tree are pushed into cut_edges.
386 cut_edges = []
387 for edge in in_edges:
388 if partition.find(edge[0]) != partition.find(edge[1]):
389 cut_edges.append(edge)
390 partition.union(edge[0], edge[1])
392 cut_polygon = _reconstruct_cut_polygon(out_edges, cut_edges, plane)
393 new_shape = PyOCCTools.make_faces_from_pnts(cut_polygon)
395 # Copy over shape location
396 # shape_loc = TopoDS_Iterator(shape).Value().Location()
397 # new_shape.Move(shape_loc)
399 return new_shape
402def _cross(a: Vertex, b: Vertex) -> Vertex:
403 return a[1] * b[2] - a[2] * b[1], a[2] * b[0] - a[0] * b[2], a[0] * b[1] - \
404 a[1] * b[0]
407def _dot(a: Vertex, b: Vertex) -> float:
408 return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
411def _minus(a: Vertex, b: Vertex) -> Vertex:
412 return a[0] - b[0], a[1] - b[1], a[2] - b[2]
415def _is_convex_angle(p1: Vertex, p2: Vertex, p3: Vertex,
416 normal: Vertex) -> bool:
417 cross = _cross(_minus(p2, p1), _minus(p3, p1))
418 return _dot(cross, normal) >= -1e-6
421def fuse_pieces(pieces: List[List[Vertex]],
422 shapes_to_consider: List[TopoDS_Shape] = []) -> List[
423 List[Vertex]]:
424 normal, _, _ = _calculate_plane_vectors(pieces[0])
425 consider_polygons = False
427 if len(shapes_to_consider) > 0:
428 consider_polygons = True
429 edges = []
430 for shape in shapes_to_consider:
431 list_pnts = PyOCCTools.get_points_of_face(shape)
432 for i, p in enumerate(list_pnts[:-1]):
433 edges.append(BRepBuilderAPI_MakeEdge(list_pnts[i],
434 list_pnts[i + 1]).Shape())
435 edges.append(
436 BRepBuilderAPI_MakeEdge(list_pnts[-1], list_pnts[0]).Shape())
438 i1 = 0
439 while i1 < len(pieces) - 1:
440 piece_a = pieces[i1]
441 i1 += 1
442 for piece_a_idx in range(0, len(piece_a)):
443 a1 = piece_a[piece_a_idx]
444 a2 = piece_a[(piece_a_idx + 1) % len(piece_a)]
446 is_inner_edge = False
447 piece_b = None
448 piece_b_idx = None
449 for i2 in range(i1, len(pieces)):
450 piece_b = pieces[i2]
451 for triangle_b_check_idx in range(0, len(piece_b)):
452 if a2 != piece_b[triangle_b_check_idx]:
453 continue
454 if a1 != piece_b[(triangle_b_check_idx + 1) % len(piece_b)]:
455 continue
456 piece_b_idx = triangle_b_check_idx
457 is_inner_edge = True
458 break
459 if is_inner_edge:
460 break
461 if not is_inner_edge:
462 continue
464 # piece_a and piece_b are two triangles with a common edge (piece_a
465 # and piece_b)
466 # common edge is spanned between a1 and a2
467 p1 = piece_a[(piece_a_idx - 1) % len(piece_a)]
468 p2 = a1
469 p3 = piece_b[(piece_b_idx + 2) % len(piece_b)]
471 if not consider_polygons:
472 # if no polygons need to be considered, shapes are fused
473 # unless resulting shape is non-convex
474 if not _is_convex_angle(p1, p2, p3, normal):
475 continue
476 else:
477 # if an edge from triangulation cuts the edge of a polygon
478 # which needs to be considered (e.g. from an opening boundary
479 # within a boundary of a wall), then those shapes have to be
480 # fused regardless of the resulting angle
481 # this may lead to non-convex shapes in some cases
482 a1_edge = BRepBuilderAPI_MakeEdge(gp_Pnt(*a1),
483 gp_Pnt(*a2)).Shape()
484 continue_flag = True
485 for edge in edges:
486 if BRepExtrema_DistShapeShape(
487 edge, a1_edge, Extrema_ExtFlag_MIN).Value() < 1e-3:
488 continue_flag = False
489 else:
490 pass
491 if continue_flag:
492 continue
494 # procedure is repeated for common edge of neighboring shape
495 p1 = piece_b[(piece_b_idx - 1) % len(piece_b)]
496 p2 = a2
497 p3 = piece_a[(piece_a_idx + 2) % len(piece_a)]
498 if not consider_polygons:
499 if not _is_convex_angle(p1, p2, p3, normal):
500 continue
501 else:
502 a2_edge = BRepBuilderAPI_MakeEdge(gp_Pnt(*a2),
503 gp_Pnt(*a1)).Shape()
504 continue_flag = True
505 for edge in edges:
506 if BRepExtrema_DistShapeShape(
507 edge, a2_edge, Extrema_ExtFlag_MIN).Value() < 1e-3:
508 continue_flag = False
509 else:
510 pass
511 if continue_flag:
512 continue
513 # fuse triangles (if angle is convex or opening-polygon is cut by
514 # this edge
515 fused_piece = []
516 i = (piece_a_idx + 1) % len(piece_a)
517 while i != piece_a_idx:
518 fused_piece.append(piece_a[i])
519 i = (i + 1) % len(piece_a)
520 i = (piece_b_idx + 1) % len(piece_b)
521 while i != piece_b_idx:
522 fused_piece.append(piece_b[i])
523 i = (i + 1) % len(piece_b)
525 i1 -= 1
526 pieces.remove(piece_a)
527 pieces.remove(piece_b)
528 pieces.insert(i1, fused_piece)
529 piece_a = fused_piece
530 break
531 return pieces
534def convex_decomposition_base(shape: TopoDS_Shape,
535 opening_shapes: List[TopoDS_Shape] = []) -> List[
536 List[Vertex]]:
537 """Convex decomposition base: removes common edges of triangles unless a
538 non-convex shape is created.
539 In case of openings: In a first round, remove all cutting triangle edges
540 with the opening polygons regardless of non-convex shapes.
541 Then, check for resulting angles. This may lead to non-convex shapes,
542 but should work in most cases.
543 """
544 pieces = _get_triangulation(shape)
545 if len(opening_shapes) > 0:
546 pieces = fuse_pieces(pieces, opening_shapes)
547 pieces = fuse_pieces(pieces)
549 return pieces
552def convex_decomposition(shape: TopoDS_Shape,
553 opening_shapes: List[TopoDS_Shape] = []) -> List[
554 TopoDS_Shape]:
555 pieces = convex_decomposition_base(shape, opening_shapes)
556 pieces_area = 0
557 new_area = 0
558 new_pieces = []
559 for p in pieces:
560 pieces_area += PyOCCTools.get_shape_area(
561 PyOCCTools.make_faces_from_pnts(p))
562 pnt_list_new = PyOCCTools.remove_coincident_vertices(
563 [gp_XYZ(pnt[0], pnt[1], pnt[2]) for pnt in p])
564 pnt_list_new = PyOCCTools.remove_collinear_vertices2(pnt_list_new)
565 if pnt_list_new != p and len(pnt_list_new) > 3:
566 pnt_list_new = [n.Coord() for n in pnt_list_new]
567 p = pnt_list_new
568 new_pieces.append(p)
569 new_area += PyOCCTools.get_shape_area(
570 PyOCCTools.make_faces_from_pnts(p))
571 if abs(pieces_area - new_area) > 1e-3:
572 new_pieces = pieces
573 new_shapes = list(
574 map(lambda p: PyOCCTools.make_faces_from_pnts(p), new_pieces))
575 oriented_shapes = []
576 org_normal = PyOCCTools.simple_face_normal(shape)
577 for new_shape in new_shapes:
578 new_normal = PyOCCTools.simple_face_normal(new_shape)
579 if all([abs(i) < 1e-3 for i in ((new_normal - org_normal).Coord())]):
580 oriented_shapes.append(new_shape)
581 else:
582 new_shape = PyOCCTools.flip_orientation_of_face(new_shape)
583 new_normal = PyOCCTools.simple_face_normal(new_shape)
584 if all([abs(i) < 1e-3 for i in
585 ((new_normal - org_normal).Coord())]):
586 oriented_shapes.append(new_shape)
587 else:
588 logger = logging.getLogger(__name__)
589 logger.error(
590 "Convex decomposition produces a gap in new space boundary")
591 # check if decomposed shape has same area as original shape
592 oriented_area = 0
593 org_area = PyOCCTools.get_shape_area(shape)
594 for face in oriented_shapes:
595 oriented_area += PyOCCTools.get_shape_area(face)
596 cut_count = 0
597 while abs(org_area - oriented_area) > 5e-3:
598 cut_count += 1
599 cut_shape = shape
600 for bound in oriented_shapes:
601 cut_shape = BRepAlgoAPI_Cut(cut_shape, bound).Shape()
602 list_cut_shapes = PyOCCTools.get_faces_from_shape(cut_shape)
603 add_cut_shapes = []
604 for cs in list_cut_shapes:
605 new_normal = PyOCCTools.simple_face_normal(cs)
606 if not all([abs(i) < 1e-3 for i in
607 ((new_normal - org_normal).Coord())]):
608 cs = PyOCCTools.flip_orientation_of_face(cs)
609 cut_area = PyOCCTools.get_shape_area(cs)
610 if cut_area < 5e-4:
611 continue
612 cs = PyOCCTools.remove_coincident_and_collinear_points_from_face(cs)
613 oriented_area += cut_area
614 add_cut_shapes.append(cs)
615 if cut_count > 3:
616 logger = logging.getLogger(__name__)
617 logger.error(
618 "Convex decomposition produces a gap in new space boundary")
619 break
620 else:
621 oriented_shapes.extend(add_cut_shapes)
622 return oriented_shapes
625def is_convex_slow(shape: TopoDS_Shape) -> bool:
626 """
627 Computational expensive check if a TopoDS_Shape is convex.
628 Args:
629 shape: TopoDS_Shape
631 Returns:
632 bool, True if shape is convex.
633 """
634 return len(convex_decomposition_base(shape)) == 1
637def is_convex_no_holes(shape: TopoDS_Shape) -> bool:
638 """check if TopoDS_Shape is convex. Returns False if shape is non-convex"""
639 gp_pnts = PyOCCTools.get_points_of_face(shape)
640 pnts = list(map(lambda p: _gp_pnt_to_coord_tuple(p), gp_pnts))
641 z = 0
642 for i in range(0, len(pnts)):
643 p0 = pnts[i]
644 p1 = pnts[(i + 1) % len(pnts)]
645 p2 = pnts[(i + 2) % len(pnts)]
646 cross = _cross(_minus(p1, p0), _minus(p2, p1))[2]
647 if z != 0 and abs(cross) >= 1e-6 and numpy.sign(cross) != numpy.sign(z):
648 return False
649 else:
650 z = cross
651 return True
654def is_polygon_convex_no_holes(pnts: List[Tuple[float, float, float]]) -> bool:
655 """check if polygon made from tuples of floats is convex.
656 Returns False if shape is non-convex"""
657 z = 0
658 for i in range(0, len(pnts)):
659 p0 = pnts[i]
660 p1 = pnts[(i + 1) % len(pnts)]
661 p2 = pnts[(i + 2) % len(pnts)]
662 cross = _cross(_minus(p1, p0), _minus(p2, p1))[2]
663 if z != 0 and abs(cross) >= 1e-6 and numpy.sign(cross) != numpy.sign(z):
664 return False
665 else:
666 z = cross
667 return True