Skip to content

Primitives and PrimitiveComputers

Jump to bottom
troussil edited this page Oct 5, 2012 · 12 revisions

What is a primitive ?

A "primitive" in discrete geometry is usually understood as some family of digital shapes with specific properties. Classical ones are digital straight lines and segments, digital planes, digital arcs, digital circles, etc. These objects can be sometimes summarized with a few coefficients. Furthermore, a lot of algorithms exist to recognize these primitives, meaning that, given a set of points, it detects if it belongs to this family and determines a correct instance.

Properties of primitives

A general approach to a primitive / shape family F is to define them as a function from subsets of a given set S to Bool. It is a function from the powerset of S to Bool, or equivalently an element of the powerset of S. In the finite case, it may also be seen as a subset of the lattice powerset.

Primitives are characterized by intra-properties. Some of this properties induces the presence of some operations, others are just semantic. Properties are tags either True or False.

  • Increasing: For any T, T' subsets of S, T \subset T' => F(T) <= F(T'). Ex: sets with more than k elements.
  • Decreasing: For any T, T' subsets of S, T \subset T' => F(T) >= F(T'). Ex: piece of digital plane (not necessarily connected)
  • PartiallyDecreasing: For any T={a_i}{i=1..n} subset of S, there is a permutation s such that for all 1<=j<=n, F({a_s(i)}{i=1..j-1}) >= F({a_s(i)}_{i=1..j}). Ex: connected piece of digital plane
  • LeftOrderedDecreasing: Given a strict ordering < on S, For any a_1 < a_2 < ... < a_n elements of S, F({a_i}{i=2..n}) >= F({a_i}{i=1..n}). Ex: connected digital straight segment.
  • RightOrderedDecreasing: Given a strict ordering < on S, For any a_1 < a_2 < ... < a_n elements of S, F({a_i}{i=1..n-1}) >= F({a_i}{i=1..n}). Ex: connected digital straight segment.
  • OrderedDecreasing: Given a strict ordering < on S, For any a_1 < ... < a_k < ... < a_l < ... < a_n elements of S, F({a_i}{i=k..l}) >= F({a_i}{i=1..n}). Ex: connected digital straight segment.
  • HasBottom: F(\emptyset) is true.
  • HasTop: F(S) is true.
  • OrderedSpace: S has a strict ordering (what about cyclic ordering ?)

NB: A primitive F that is both LeftOrderedDecreasing and RightOrderedDecreasing is OrderedDecreasing.

NB: For any T, T', T \subset T', T is maximal iff F(T) and \neg F(T'). In addition, given a strict ordering < on S and a primitive F that is OrderedDecreasing, for any a_1 < ... < a_k < ... < a_l < ... < a_n elements of S, {a_i}{i=k..l} is maximal iff F({a_i}{i=k..l}) and \neg F({a_i}{i=(k-1)..(l)}) and \neg F({a_i}{i=(k)..(l+1)}).

Some are instance-properties (and implies operations).

  • Enumerable: given a domain D, T such that F(T), then D \cap T is iterable (enumerate( Domain ): Range)
  • Iterable: given T such that F(T), the elements of T can be visited with begin(), end()
  • Bounded: any T such that F(T) has a bounding box. (lowerBound(): Point and upperBound(): Point

Some could be inter-properties (with another primitive G)

  • Inclusion: for any T, F(T) <= G(T). Ex: connected digital straight segments are included in arbitrary digital straight segment. Naive planes are included in unconnected planes Connected digital straight segments are included in connected digital circular arcs.
  • IsConvertible: Given any T with F(T), a T' with G(T') is computable.

Algebra

Let a primitive H be defined as, given any T:

  1. H(T) = \neg F(T)

  2. H(T) = F(T) \cap G(T)

  3. H(T) = F(T) \cup G(T)

Knowing the properties of F (and G), what are the properties of H ?

  • In case 1., H is Increasing (resp. Decreasing) iff F is Increasing (resp. Decreasing).
  • In case 2.
  • In case 3.

The concept of primitive is thus very light:

  • CPrimitive: Inner types
    • Space: the type of S
    • Element: the type of each element of S
    • should be Assignable, CopyConstructible.
    • should be DefaultConstructible iff HasBottom.

Objects that computes primitives

Objects that determines if T satisfies F(T) might use properties of F. They may also offer a variety of services to check F(T): offline, incremental, dynamic, etc. These objects are called PrimitiveComputers.

  • CPrimitiveComputer: Any PrimitiveComputer has a current state (which is a set T such that F(T)). It must also be able to provide the corresponding primitive instance. It has inner types:

    • Primitive: the type of each primitive
    • Element: the type Primitive::Element
    • Methods:
      • primitive() const: Primitive. Returns T.

  • CFinitePrimitiveComputer -> CPrimitiveComputer: The set T is finite. The object is also a CConstRange.

    • This requires PrimitiveTraits::Iterable
    • Do we need to force a method template create( ElementIt it, ElementIt itE ) : bool that creates F([it,itE]) ?

  • CSegmentComputer -> CFinitePrimitiveComputer: A variant where S has a strict ordering.

    • This requires PrimitiveTraits::OrderedSpace

  • CIncrementalPrimitiveComputer -> CFinitePrimitiveComputer: From T and F(T), this object can determine if F(T \cup t) for t \in S.

    • extend( Element ) : bool
    • isExtendable( Element ) const : bool
    • This requires PrimitiveTraits::PartiallyDecreasing ?

  • CAdditivePrimitiveComputer -> CIncrementalPrimitiveComputer: From T and F(T), this object can determine if F(T \cup [it,itE]).

    • extend( it, itE ) : bool
    • isExtendable( it, itE ) const : bool
    • This requires PrimitiveTraits::PartiallyDecreasing ?
Clone this wiki locally