A Walking Method for Non-Decomposition Intersection and Union of Arbitrary Polygons and Polyhedrons

Abstract

We present a method for computing the intersection and union of non- convex polyhedrons without decomposition in O(n log n) time, where n is the total number of faces of both polyhedrons. We include an accompanying Python package which addresses many of the practical issues associated with implementation and serves as a proof of concept. The key to the method is that by considering the edges of the original ob- jects and the intersections between faces as walking routes, we can e ciently nd the boundary of the intersection of arbitrary objects using directional walks, thus handling the concave case in a natural manner. The method also easily extends to plane slicing and non-convex polyhedron unions, and both the polyhedron and its constituent faces may be non-convex.

Related Papers

• → Convex polyhedra of doubly stochastic matrices—IV(1976)52 cited
• → An optimal algorithm for intersecting three-dimensional convex polyhedra(1989)31 cited
• → The minimum sphere covering a convex polyhedron(1974)16 cited
• → An algorithm on discrimination of point-set in polyhedron based on three-dimensional convex hull(2010)2 cited
• → The Number of Three-Dimensional Convex Polyhedra(1987)17 cited