# Tools for constructive solid geometry in arbitrary spaces. # Last edited on 2021-02-08 20:29:22 by jstolfi import shape_IMP; from shape_IMP import Shape_IMP import trafo def module_doc(): # This module is about the representation of shapes in some # unspecified geometric and topological /space/ {\RX}, such as # {n}-dimensional Cartesian or projective space, whose elements will be # called /points/. # # Abstractly, a /shape/ {F} (in {\RX}) is defined as a pair {Int(F)} and # {Ext(F)} of topologically open subsets of the space, such that the # closure of their union is the whole space. The /boundary/ of {F} is # {Bdr(F) = \RX \setminus (Int(F)\cup Ext(F)} # # The /union/ of two shapes {F,G} is the shape {H} that has {Int(H) = # Int(F) \cup Int(G)} and {Ext(H) = Ext(F) \cap Ext(G)}. The # /intersection/ is similar but with {\cup} and {\cap} swapped. The # /complement/ of a shape {F} has the interior and exterior swapped. # # Note that union, intersection, and complement form a Boolean # algebra: union and intersection are commutative, associative and # idempotent, the complement is an involution, and the three satisfy the # DeMorgan laws. # # The neutral element of union is the /vacuum/, a shape that empty # {Int} and whose exterior is the whole space. Its complement is the # /plenum/, a shape with empty exterior whose interior is the whole # space. # # A geometric transformation of /trafo/ is a bicontinuous bijection # from {\RX} to {\RX} (see {trafo.py}. The image {T(F)} of a shape {F} # by a trafo {T} is the shape {G} that has {Int(G) = T(Int(F))} and # {Ext(G) = T(Ext(F))}. # # Shapes that can be handled in the computer must have a sufficiently # sumple geometry and topology. Common restrictions are that the # boundary be contained in some finite ball and that the shape is # constructible from a finite family of simple shapes by Boolean # operations and a specific set of geometric transformations # (such as affine, projective, etc.). class Shape(Shape_IMP): # An object of this class describes a shape in some unspecified # geometric space {\RX}. Subclasses should be defined for specific # space and families of shapes. # # For the procedures in this module, a shape {F} may be represented by a # {Shape} object, or by a tuple {(c,T,F1,F2,...,Fn)} where {c} # is /complement bit/ (0 or 1), {T} is a trafo, and {F1,F2,...Fn} are # shapes. If {c} is 0, {F} is the shape {T(F1 \cup F2 \cup ... \cup # Fn)}, the result of applying {T} to the union of those shapes. If {c} # is 1, {F} is the Boolean complement of that, namely the shape # described by {(0,T,F1,F2,...,Fn)} with interior and exterior swapped. # # As explained in {trafo.py}, the trafo {T} may be {None}, representing the # identity transformation. Thus a {Shape} object {F} is the same as # {(0,None,F)} # # A shape representation may also be {None}, meaning the /vacuum/ of the space. The # union of zero shapes, {(0,T)}, for any {T}, also is defined as the vacuum. # Therefore the tuple {(1,T)}, for any {T}, represents the plenum of the space. # # There are many shape representations that are /equivalent/ in the sense that # they describe the same shape. In general, equivalence cannot be # established conclusively without knowing the nature and parameters # of the {Shape} objects. # # ??? Can we compute equivalence for any possible # choice of objects and trasnsformations? ??? # VACUUM AND PLENUM def vacuum(): # Returns a shape that describes the empty set (the set with no points of the space). return shape_IMP.vacuum() def plenum(): # Returns a shape that describes the whole space (the set of all points). return shape_IMP.plenum() def is_vacuum(F): # This procedure returns {True} if it can determine that {F} is equivalent to the # vacuum; for example, if {F} is {None} or {(0,)}. Otherwise (if {F} is not # equivalent to vacuum, or the procedure cannot decide) it returns {False}. return shape_IMP.is_vacuum(F) def is_plenum(F): # This procedure returns {True} if it can determine that {F} is equivalent to the # plenum; for example, if {F} is {(1,)}. Otherwise (if {F} is not # equivalent to plenum, or the procedure cannot decide) it returns {False}. return shape_IMP.is_plenum(F) # BOOLEAN OPERATIONS ON SHAPES def complement(F): # Returns the Boolean complement of {F}, namely {F} with interior and # exterior swapped. # # In particular, if {F} is a {Shape} object, returns {(1,M)}; if {F} is # {None}, returns the singleton tuple {(1,)}; if {F} is the singleton # tuple {(1,)}, returns {None}; and if {F} is any other # tuple {(c,F1,F2,...,Fn)}, returns the tuple {(1-c,F1,F2,...,Fn)}. return shape_IMP.complement(F) def union(FL): # The argument {FL} must be a list of zero or more shapes. # This procedure returns the union of all shapes, namely # {(0,None) + FL} or some equivalent representation. return shape_IMP.union(FL) def intersection(FL): # The argument {FL} must be a list of zero or more shapes. # This procedure returns the intersection of all shapes, namely # {(1,None) + FL'} where {FL'} is the list of {complement(Fk)} for # every element {Fk} in {FL}; or some equivalent representation. return shape_IMP.intersection(FL) def difference(F, FL): # The argument {FL} must be a list of zero or more shapes. # This procedure returns the set difference between the shape {F} # and the union of the shapes in {FL}; that is, # {intersection(F, complement(union(FL)))} return shape_IMP.difference(F, FL) # GEOMETRIC TRANSFORMATIONS def transform(F,T): # Returns a shape that is the result of applying the transformation {T} to # the figure {F}; namely, {(0, T, F)} or some equivalent representation. # # However, if the procedure can determine that {T} is the identity (for # example, if {T} is {None}), it will return {F} itself. # # Also, if the procedure cn determine that {F} is the vacuum or plenum # (for example, if {F} is {None}, {(0,)}, or {(1,)}, the result may be {F} # itself. return shape_IMP.transform(F,T) # UNPACKING THE REPRESENTATION def cbit(F): # Returns the complement bit of representation of the shape {F}. # # Specifically, {F} is {None} or a {Shape} object, returns 0. # Otherwise, {F} must be a list or tuple {(c,T,F1,F2,...,Fn)}; # in that case, returns the bit {c}. return shape_IMP.cbit(F) def trafo(F): # Returns the top-level transformation in the representation of the shape {F}. # # Specifically, {F} is {None} or a {Shape} object, returns {None} (the identity # trafo). Otherwise, {F} must be a list or tuple {(c,T,F1,F2,...,Fn)}; # in that case, returns the trafo {T}. return shape_IMP.trafo(F) def nterms(F): # Returns the number of sub-shapes in the representation of the shape {F}. # # Specifically, {F} is {None}, returns 0. If {F} is a {Shape} object, returns 1. # Otherwise, {F} must be a list or tuple {(c,T,F1,F2,...,Fn)}; in that case, # returns {len(F)-2}. return shape_IMP.nterms(F) def term(F,k): # Returns the sub-shape with index {k} in the sub-shapes of the representation {F}. # The index {k} must be in {0..n-1} where {n = nterms(F)}. # # Specifically, if {F} is a {Shape} object, {k} must be 0, and the result is {F} itself. # Otherwise, {F} must be a list or tuple {(c,T,F1,F2,...,Fn)}; in that case, # returns {F[k+2]}. If {n} is zero (for example, if {F} is {None} or {(1,T)}), # the procedure aborts with error. return shape_IMP.term(F,k) def simplify(F): # Tries to simplify the shape representation {F} by using # properties of Boolean set operations. # # In particular, if {F} is a tuple {(c,T,F1,F2,...,Fn)}, each {Fk} must # be a {Shape} object, or a tuple {(ck,Tk,Fk1,Fk2,...,Fknk)} where # either {ck != c} or {Tk != None}. Moreover, a tuple with a zero cbit # must have at least 2 terms, and a tuple with a 1 cbit must have at # least one term. return shape_IMP.simplify(F,k)