Digital Plane Preimage Computation


preimage is a simple program to recognize digital plane. It computes the preimage associated to a set of voxels. This code uses the lrs library to compute the intersection of a set of inequations. It returns the preimage vertex coordinates.

Just an example, if you have a set of voxels stored in an text file example.pt3d. The first line of this file contains the number of points and then we have the grid points (x y z coordinates) : 
6                                             
0 0 0                                             
1 1 1                                             
2 1 1                                             
2 2 1                                             
3 2 1                                             
2 3 1

If you send this file to the standard input of preimage : 
 cat example.pt3d | preimage

You will obtain : 
Preimage:

V-representation
begin
***** 4 rational
 1  1/5  1/5  1
 1  1/3  1/3  1/3
 1  1/2  0  1/2
 1  1/3  0  1
 1  0  0  1
 1  0  1/3  1
 1  0  1/2  1/2
end
*Totals: vertices=7 rays=0 bases=16lrslib v.4.1, 2001.6.26(32bit,lrsmp.h)
3
7
0.200000 0.200000 1.000000
0.333333 0.333333 0.333333
0.500000 0.000000 0.500000
0.333333 0.000000 1.000000
0.000000 0.000000 1.000000
0.000000 0.333333 1.000000
0.000000 0.500000 0.500000

The standard output can be sent to qhull to obtain a complete polyhedral representation of the digital plane preimage. The final goal is to produce a Geomview file. 
 cat example.pt3d | preimage | qhull G TO polyhedron.geom

Hence we obtain, in Geomview, the polyhedron :

There exists a tool to add axis using the same structure :
 cat example.pt3d | preimage | qhull G | preimage_axis > polyhedron.geom

In Geomview we obtain:

Note: Axis are labelled X Y and Z but the polyhedron is defined in the parameter space of digital planes.

We can aslo use preimage to decide if a set of voxels belongs to a digital plane (in that case the polyhedron is not empty). If we consider voxels that do not belong to a digital plane (file example_not_DP.pt3d): 
6                                             
0 0 0                                             
1 1 1                                             
2 1 1                                             
2 2 1                                             
3 2 1                                             
2 3 6
preimage returns: 
cat example_not.pt3d | preimage
Preimage:

V-representation
begin
***** 4 rational
No feasible solutionbasis failes
lrslib v.4.1, 2001.6.26(32bit,lrsmp.h)
dcoeurjo
Last modified: Tue Feb 4 17:42:27 MET 2003