SIVIGNON
Isabelle
Chargée de Recherche CNRS
Research

Note: If no licence is specified, all these codes are freely available but without any warranty.

Here are some codes/softwares related to digital or computational geometry.

Digital surface decomposition into digital planes

Simplification of a digital curve

Fast computation of the characteristics of a Digital Straight Line Subsegment

Union of Digital Straight Segments

• Implementation of the algorithm presented in "Algorithms for Fast Digital Straight Segments Union". Isabelle Sivignon, International Conference on Discrete Geometry for Computer Imagery 2014, Springer LNCS 344-357. It computes the minimal characteristics of the digital straight line containing two given digital straight segments. The code is part of the DGtal library, as a method of the class ArithmeticalDSS.

Fraction of smallest denominator in between two irreducible fractions

(δ-ε)-ball approximation of a shape

• In "(δ,ε)-ball approximation of a shape: definition and complexity", we prove that the problem is NP-complete. The proof is made through a reduction from a variant of the vertex cover problem, with a well-defined geometric construction for any cubic planar graph. In appendix of the article, we provide a specific vertex gadget for degree-three vertices when δ=0 and claim that this gadget actually remains valid for any value of δ. We provide here a Geogebra file that gives a parameterized generic construction of this gadget for any values of δ and ε.

Efficient Distance Transformation for Path-based Metrics

• In "Efficient Distance Transformation for Path-based Metrics", we provide efficient separable algorithms to compute distance transformation for shapes in nD images and path-based metrics. In particular, we provide an algorithm for which the complexity depends on the geometry of the cut of a rational ball (ball that defines the metric) by a 2-flat. Python code used to generate rational balls from nD Farey Sequences and to study the number of vertices of the cut is available here: it uses Qhull to compute convex hulls and cuts by hyperplanes.

Average Curve of n Digital Curves

• In "Average Curve of n Digital Curves", we provide algorithms to compute the average of digital curves. Algorithms described in the paper are implemented in C++ using the DGtal library, and the code is available here. We also provide Python code used in the proof of Lemma 2 here.

Other material concerning digital geometry is available on the IAPR-TC18 webpage.

Grenoble Images Parole Signal Automatique laboratoire

UMR 5216 CNRS - Grenoble INP - Université Joseph Fourier - Université Stendhal