Ask Your Question

Union of touching polyhedra

asked 2021-02-19 13:55:30 +0100

zhaiyu gravatar image

updated 2021-02-20 11:43:02 +0100

Hi, I'm trying to do a union operation over multiple touching polyhedra into one but couldn't find how to achieve this with Sage. For example, how can I merge these two cubes and dissolve the interior face (the touching face):

# two cubes touching
cube_a = Polyhedron(vertices=[(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)])
cube_b = Polyhedron(vertices=[(1,1/2,0), (1,1/2,1), (1,3/2,0), (1,3/2,1), (2,1/2,0), (2,1/2,1), (2,3/2,0), (2,3/2,1)])

# visualize
cube_a.plot() + cube_b.plot()

The polyhedra can be assumed all convex, and each touching pair share a polygon interface. I found polyhedron.intersection(other), but no polyhedron.union(other) or so. Any workaround I can do? Thanks in advance.

edit retag flag offensive close merge delete



Note that you can do:

sage: cube_b = cube_a + vector((1,1/2,0))
Sébastien gravatar imageSébastien ( 2021-02-21 15:33:53 +0100 )edit

1 Answer

Sort by » oldest newest most voted

answered 2021-02-20 09:30:06 +0100

Sébastien gravatar image

Let me first define your polyhedron over the same base ring:

sage: cube_a = Polyhedron(vertices=[(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)], base_ring=QQ) 
sage: cube_b = Polyhedron(vertices=[(1,1/2,0), (1,1/2,1), (1,3/2,0), (1,3/2,1), (2,1/2,0), (2,1/2,1), (2,3/2,0), (2,3/2,1)], base_ring=QQ)                                                          
sage: cube_a                                                                                         
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices
sage: cube_b                                                                                         
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 8 vertices

You may define this function which returns the convex hull of a list of polyhedron:

def convex_hull(list_of_polyhedron): 
    V = sum((p.vertices() for p in list_of_polyhedron), tuple()) 
    return Polyhedron(V)

In your case, you obtain:

sage: convex_hull([cube_a, cube_b])
A 3-dimensional polyhedron in QQ^3 defined as the convex hull of 12 vertices

If the union is convex, the convex hull is the union. In your case, the convex hull does not seem to be equal to the union of the two cubes. Comparing their volume, we obtain:

sage: cube_a.volume()                                                                                
sage: cube_b.volume()                                                                                
sage: convex_hull([cube_a, cube_b]).volume()                                                         

Recently, I needed to check whether the union of a list of polyhedron is convex before creating their union using convex hull. I wrote that in my package which can be installed with sage -pip install slabbe. In your case, it returns False, so the convex hull is not equal to the union of the two polyhedron:

sage: from slabbe.polyhedron_partition import is_union_convex   
sage: is_union_convex([cube_a, cube_b])                                                              
edit flag offensive delete link more


Thanks for the answer! The union in the example is intentionally not convex. What I'd like to have in the end is the outer surface of the union (doesn't have to be Sage's polyhedron which as I understand should be convex; it can be polygons3d or just the boundary representation of the mesh). I checked your slabbe package (PolyhedronPartition seems close to my needs) but couldn't find the desired function.

zhaiyu gravatar imagezhaiyu ( 2021-02-20 11:41:19 +0100 )edit

Then, maybe you want to compute the intersection of their faces:

sage: cube_a.faces(face_dimension=2)                                            
(A 2-dimensional face of a Polyhedron in QQ^3 defined as the convex hull of 4 vertices,
 A 2-dimensional face of a Polyhedron in QQ^3 defined as the convex hull of 4 vertices)

Unfortunately, those faces do not have a intersection method. So you will need to use their H-representation to compute their intersection with another face. It seems doable in few lines.

Sébastien gravatar imageSébastien ( 2021-02-21 15:41:55 +0100 )edit

That I know. I just found out the union thing can be done with (3D Boolean Operations on Nef Polyhedra). While Sage doesn't have it (seems the Nef representation does exist for lattice polytope though), CGAL has it implemented. Thanks again.

zhaiyu gravatar imagezhaiyu ( 2021-02-21 23:12:23 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2021-02-19 13:55:30 +0100

Seen: 51 times

Last updated: Feb 20