Skip to content

Primitives and PrimitiveComputers

Jump to bottom Edit New page
troussil edited this page Oct 8, 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 straight line, 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 path, 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: visibility cone (whose apex is set to the first point a_1), connected path, connected digital straight segment.
  • LeftRightOrderedDecreasing: 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 path, 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 LeftRightOrderedDecreasing. Ex: connected digital straight segment.

NB: If F is Increasing (resp. Decreasing), then, given a strict ordering < on S, F is LeftRightOrderedDecreasing. Ex: digital straight segment (points are ordered but not necessarily connected).

NB: For any T such that F(T), T is maximal iff, for all T' such that T \subset T', \neg F(T'). In addition, given a strict ordering < on S and a primitive F that is LeftRightOrderedDecreasing, any {a_i}{i=k..l} such that F({a_i}{i=k..l}) is maximal iff \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)
    1. H(T) = F(T) and G(T)
    1. H(T) = F(T) or 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 Decreasing (resp. Increasing).
  • In case 2), H is Increasing (resp. Decreasing) iff F and G are both Increasing (resp. Decreasing).
  • In case 3), idem
    Ex: given a strict ordering < on S, a connected path is LeftRightOrderedDecreasing, a digital straight segment is LeftRightOrderedDecreasing and a connected digital straight segment is thus LeftRightOrderedDecreasing.

Concept of primitive

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.

Example of primitives

  • DSL
  • DSS (there exists a containing DSL)
  • k-connected DSS. Note that the arithmetical thickness and k can be independent:
    • 0-connected and \omega = max(|a|+|b|)
    • 0-connected and \omega = max(|a|+|b|)+1 (tangent word)
    • 0-connected and threshold >= \omega >= max(|a|+|b|)+1 (blurred or thick segment)
    • idem for 1-adjacency and \omega = |a|+|b|

Objects that compute 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]) ?

  • 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 ?

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

    • This requires PrimitiveTraits::OrderedSpace

  • CForwardSegmentComputer -> CSegmentComputer

    • This requires PrimitiveTraits::RightOrderedDecreasing

Example of primitive computers

  • ArithmeticalDSS
  • ArithmeticalDSS3d
  • CombinatorialDSS
  • GeometricalDSS
  • GeometricalDCA

Objects that use primitive computers

  • For OrderedSpace
    • GreedySegmentation<ConstIterator, SegmentComputer>
      • This requires that SegmentComputer is at least a model of CForwardSegmentComputer (ie. the segment is RightOrderedDecreasing).
    • SaturatedSegmentation<ConstIterator, SegmentComputer>
      • This requires that SegmentComputer is at least a model of CForwardSegmentComputer and that the segment is LeftRightOrderedDecreasing to test the maximality.
Add a custom footer
Add a custom sidebar
Clone this wiki locally