# Tools for constructive solid geometry in arbitrary spaces.
# Last edited on 2021-09-23 12:11:01 by stolfi

import shape_IMP; from shape_IMP import Shape_IMP
import trafo

# 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/ {S} (in {\RX}) is defined as a pair {Int(S)} and
# {Ext(S)} of topologically open subsets of the space, such that the
# closure of their union is the whole space. The /boundary/ of {S} is
# {Bdr(S) = \RX \setminus (Int(S)\cup Ext(S)}
#
# The /union/ of two shapes {S,G} is the shape {H} that has {Int(H) =
# Int(S) \cup Int(G)} and {Ext(H) = Ext(S) \cap Ext(G)}. The
# /intersection/ is similar but with {\cup} and {\cap} swapped. The
# /complement/ of a shape {S} 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(S)} of a shape {S}
# by a trafo {T} is the shape {G} that has {Int(G) = T(Int(S))} and 
# {Ext(G) = T(Ext(S))}.
#
# 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 {S} may be represented by a
  # {Shape} object, or by a tuple {(c,T,S1,S2,...,Sn)} where {c}
  # is /complement bit/ (0 or 1), {T} is a trafo, and {S1,S2,...Sn} are
  # shapes. If {c} is 0, {S} is the shape {T(S1 \cup S2 \cup ... \cup
  # Sn)}, the result of applying {T} to the union of those shapes. If {c}
  # is 1, {S} is the Boolean complement of that, namely the shape
  # described by {(0,T,S1,S2,...,Sn)} with interior and exterior swapped.
  #
  # As explained in {trafo.py}, the trafo {T} may be {None}, representing the 
  # identity transformation.   Thus a {Shape} object {S} is the same as
  # {(0,None,S)}
  #
  # 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? ???
  pass

# 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(S):
  # This procedure returns {True} if it can determine that {S} is equivalent to the
  # vacuum; for example, if {S} is {None} or {(0,None)}.  Otherwise (if {S} is not
  # equivalent to vacuum, or the procedure cannot decide) it returns {False}.
  return shape_IMP.is_vacuum(S)
  
def is_plenum(S):
  # This procedure returns {True} if it can determine that {S} is equivalent to the
  # plenum; for example, if {S} is {(1,None)}.  Otherwise (if {S} is not
  # equivalent to plenum, or the procedure cannot decide) it returns {False}.
  return shape_IMP.is_plenum(S)
  
# BOOLEAN OPERATIONS ON SHAPES

def complement(S):
  # Returns the Boolean complement of {S}, namely {S} with interior and
  # exterior swapped.  
  #
  # In particular, if {S} is a {Shape} object, returns {(1,M)}; if {S} is
  # {None}, returns the singleton tuple {(1,)}; if {S} is the singleton
  # tuple {(1,)}, returns {None}; and if {S} is any other
  # tuple {(c,S1,S2,...,Sn)}, returns the tuple {(1-c,S1,S2,...,Sn)}.
  return shape_IMP.complement(S)
   
def union(SL):
  # The argument {SL} must be a list of zero or more shapes.
  # This procedure returns the union of all shapes, namely 
  # {(0,None) + SL} or some equivalent representation.
  return shape_IMP.union(SL)
  
def intersection(SL):
  # The argument {SL} must be a list of zero or more shapes.
  # This procedure returns the intersection of all shapes, namely 
  # {(1,None) + SL'} where {SL'} is the list of {complement(Sk)} for 
  # every element {Sk} in {SL}; or some equivalent representation.
  return shape_IMP.intersection(SL)
  
def difference(S, SL):
  # The argument {SL} must be a list of zero or more shapes.
  # This procedure returns the set difference between the shape {S}
  # and the union of the shapes in {SL}; that is,
  # {intersection(S, complement(union(SL)))}
  return shape_IMP.difference(S, SL)
  
# GEOMETRIC TRANSFORMATIONS

def transform(S,T):
  # Returns a shape that is the result of applying the transformation {T} to
  # the figure {S}; namely, {(0, T, S)} or some equivalent representation.
  #
  # However, if the procedure can determine that {T} is the identity (for
  # example, if {T} is {None}), it will return {S} itself.
  #
  # Also, if the procedure cn determine that {S} is the vacuum or plenum
  # (for example, if {S} is {None}, {(0,)}, or {(1,)}, the result may be {S}
  # itself.
  return shape_IMP.transform(S,T)
  
# UNPACKING THE REPRESENTATION
  
def unpack(S):
  # Retruns three results: a complement bit {cbit} (either 0 or 1),
  # a trafo {T}, and a list {SL} of shapes, such that 
  # {S} is equivalent to {(cbit,T) + SL}.
  # In particular if {S} is {None} returns 
  # {0,None,()}, and if {S} is a {Shape} object returns {0,None,(S,)}.
  return shape_IMP.unpack(S)

# SIMPLIFYING THE REPRESENTATION
  
def simplify(S):
  # Tries to simplify the shape representation {S} by using
  # properties of Boolean set operations.
  #
  # In particular, if {S} is a tuple {(c,T,S1,S2,...,Sn)}, each {Sk} must
  # be a {Shape} object, or a tuple {(ck,Tk,Sk1,Sk2,...,Sknk)} 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(S,k)