2 * This program is free software: you can redistribute it and/or modify
3 * it under the terms of the GNU Lesser General Public License as
4 * published by the Free Software Foundation, either version 3 of the
5 * License, or (at your option) any later version.
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <http://www.gnu.org/licenses/>.
18 * @file DigitalConvexity.ih
19 * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20 * Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
24 * Implementation of inline methods defined in DigitalConvexity.h
26 * This file is part of the DGtal library.
30 //////////////////////////////////////////////////////////////////////////////
32 //////////////////////////////////////////////////////////////////////////////
34 //-----------------------------------------------------------------------------
35 template <typename TKSpace>
36 DGtal::DigitalConvexity<TKSpace>::
37 DigitalConvexity( Clone<KSpace> K )
41 //-----------------------------------------------------------------------------
42 template <typename TKSpace>
43 DGtal::DigitalConvexity<TKSpace>::
44 DigitalConvexity( Point lo, Point hi )
46 myK.init( lo, hi, true );
49 //-----------------------------------------------------------------------------
50 template <typename TKSpace>
52 DGtal::DigitalConvexity<TKSpace>::
58 //-----------------------------------------------------------------------------
59 template <typename TKSpace>
60 template <typename PointIterator>
61 typename DGtal::DigitalConvexity<TKSpace>::LatticePolytope
62 DGtal::DigitalConvexity<TKSpace>::
63 makeSimplex( PointIterator itB, PointIterator itE )
65 return LatticePolytope( itB, itE );
68 //-----------------------------------------------------------------------------
69 template <typename TKSpace>
70 typename DGtal::DigitalConvexity<TKSpace>::LatticePolytope
71 DGtal::DigitalConvexity<TKSpace>::
72 makeSimplex( std::initializer_list<Point> l )
74 return LatticePolytope( l );
77 //-----------------------------------------------------------------------------
78 template <typename TKSpace>
79 template <typename PointIterator>
80 typename DGtal::DigitalConvexity<TKSpace>::RationalPolytope
81 DGtal::DigitalConvexity<TKSpace>::
82 makeRationalSimplex( Integer d, PointIterator itB, PointIterator itE )
84 return RationalPolytope( d, itB, itE );
87 //-----------------------------------------------------------------------------
88 template <typename TKSpace>
89 typename DGtal::DigitalConvexity<TKSpace>::RationalPolytope
90 DGtal::DigitalConvexity<TKSpace>::
91 makeRationalSimplex( std::initializer_list<Point> l )
93 return RationalPolytope( l );
96 //-----------------------------------------------------------------------------
97 template <typename TKSpace>
98 template <typename PointIterator>
100 DGtal::DigitalConvexity<TKSpace>::
101 isSimplexFullDimensional( PointIterator itB, PointIterator itE )
103 typedef SimpleMatrix<Integer,dimension,dimension> Matrix;
104 const Dimension d = KSpace::dimension;
105 std::vector<Point> pts( d+1 );
107 for ( ; itB != itE && k <= d; ++itB, ++k ) pts[ k ] = *itB;
108 // A simplex has exactly d+1 vertices.
109 if ( k != d+1 ) return false;
111 for ( Dimension i = 0; i < d; ++i )
112 for ( Dimension j = 0; j < d; ++j )
113 M.setComponent( i, j, pts[ i ][ j ] - pts[ d ][ j ] );
114 // A simplex has its vectors linearly independent.
115 return M.determinant() != 0;
118 //-----------------------------------------------------------------------------
119 template <typename TKSpace>
121 DGtal::DigitalConvexity<TKSpace>::
122 isSimplexFullDimensional( std::initializer_list<Point> l )
124 return isSimplexFullDimensional( l.begin(), l.end() );
127 //-----------------------------------------------------------------------------
128 template <typename TKSpace>
129 template <typename PointIterator>
130 typename DGtal::DigitalConvexity<TKSpace>::SimplexType
131 DGtal::DigitalConvexity<TKSpace>::
132 simplexType( PointIterator itB, PointIterator itE )
134 typedef SimpleMatrix<Integer,dimension,dimension> Matrix;
135 const Dimension d = KSpace::dimension;
136 std::vector<Point> pts( d+1 );
138 for ( ; itB != itE && k <= d; ++itB, ++k ) pts[ k ] = *itB;
139 // A simplex has exactly d+1 vertices.
140 if ( k != d+1 ) return SimplexType::INVALID;
142 for ( Dimension i = 0; i < d; ++i )
143 for ( Dimension j = 0; j < d; ++j )
144 M.setComponent( i, j, pts[ i ][ j ] - pts[ d ][ j ] );
145 // A simplex has its vectors linearly independent.
146 auto V = M.determinant();
147 return (V == 0) ? SimplexType::DEGENERATED
148 : ( ((V == 1) || (V==-1)) ? SimplexType::UNITARY : SimplexType::COMMON );
151 //-----------------------------------------------------------------------------
152 template <typename TKSpace>
154 DGtal::DigitalConvexity<TKSpace>::
155 displaySimplex( std::ostream& out, std::initializer_list<Point> l )
157 displaySimplex( out, l.begin(), l.end() );
160 //-----------------------------------------------------------------------------
161 template <typename TKSpace>
162 template <typename PointIterator>
164 DGtal::DigitalConvexity<TKSpace>::
165 displaySimplex( std::ostream& out, PointIterator itB, PointIterator itE )
167 typedef SimpleMatrix<Integer,dimension,dimension> Matrix;
168 const Dimension d = KSpace::dimension;
169 std::vector<Point> pts( d+1 );
171 for ( ; itB != itE && k <= d; ++itB, ++k ) pts[ k ] = *itB;
172 // A simplex has exactly d+1 vertices.
173 if ( k != d+1 ) { out << "[SPLX INVALID]"; return; }
175 for ( Dimension i = 0; i < d; ++i )
176 for ( Dimension k = 0; k < d; ++k )
177 M.setComponent( i, k, pts[ i ][ k ] - pts[ d ][ k ] );
178 // A simplex has its vectors linearly independent.
179 auto V = M.determinant();
180 out << "[SPLX V=" << V;
181 for ( Dimension i = 0; i < d; ++i ) {
183 for ( Dimension j = 0; j < d; ++j )
184 out << " " << M( i, j );
190 //-----------------------------------------------------------------------------
191 template <typename TKSpace>
192 typename DGtal::DigitalConvexity<TKSpace>::SimplexType
193 DGtal::DigitalConvexity<TKSpace>::
194 simplexType( std::initializer_list<Point> l )
196 return simplexType( l.begin(), l.end() );
200 //-----------------------------------------------------------------------------
201 template <typename TKSpace>
202 typename DGtal::DigitalConvexity<TKSpace>::PointRange
203 DGtal::DigitalConvexity<TKSpace>::
204 insidePoints( const LatticePolytope& polytope )
207 polytope.getPoints( pts );
210 //-----------------------------------------------------------------------------
211 template <typename TKSpace>
212 typename DGtal::DigitalConvexity<TKSpace>::PointRange
213 DGtal::DigitalConvexity<TKSpace>::
214 interiorPoints( const LatticePolytope& polytope )
217 polytope.getInteriorPoints( pts );
221 //-----------------------------------------------------------------------------
222 template <typename TKSpace>
223 typename DGtal::DigitalConvexity<TKSpace>::PointRange
224 DGtal::DigitalConvexity<TKSpace>::
225 insidePoints( const RationalPolytope& polytope )
228 polytope.getPoints( pts );
231 //-----------------------------------------------------------------------------
232 template <typename TKSpace>
233 typename DGtal::DigitalConvexity<TKSpace>::PointRange
234 DGtal::DigitalConvexity<TKSpace>::
235 interiorPoints( const RationalPolytope& polytope )
238 polytope.getInteriorPoints( pts );
242 //-----------------------------------------------------------------------------
243 template <typename TKSpace>
244 template <typename PointIterator>
245 typename DGtal::DigitalConvexity<TKSpace>::CellGeometry
246 DGtal::DigitalConvexity<TKSpace>::
247 makeCellCover( PointIterator itB, PointIterator itE,
248 Dimension i, Dimension k ) const
252 ASSERT( k <= KSpace::dimension );
253 CellGeometry cgeom( myK, i, k, false );
254 cgeom.addCellsTouchingPoints( itB, itE );
258 //-----------------------------------------------------------------------------
259 template <typename TKSpace>
260 typename DGtal::DigitalConvexity<TKSpace>::CellGeometry
261 DGtal::DigitalConvexity<TKSpace>::
262 makeCellCover( const LatticePolytope& P,
263 Dimension i, Dimension k ) const
267 ASSERT( k <= KSpace::dimension );
268 CellGeometry cgeom( myK, i, k, false );
269 cgeom.addCellsTouchingPolytope( P );
273 //-----------------------------------------------------------------------------
274 template <typename TKSpace>
275 typename DGtal::DigitalConvexity<TKSpace>::CellGeometry
276 DGtal::DigitalConvexity<TKSpace>::
277 makeCellCover( const RationalPolytope& P,
278 Dimension i, Dimension k ) const
282 ASSERT( k <= KSpace::dimension );
283 CellGeometry cgeom( myK, i, k, false );
284 cgeom.addCellsTouchingPolytope( P );
288 //-----------------------------------------------------------------------------
289 template <typename TKSpace>
291 DGtal::DigitalConvexity<TKSpace>::
292 isKConvex( const LatticePolytope& P, const Dimension k ) const
294 if ( k == 0 ) return true;
295 auto S = insidePoints( P );
296 auto touched_cells = makeCellCover( S.begin(), S.end(), k, k );
297 auto intersected_cells = makeCellCover( P, k, k );
298 return intersected_cells.nbCells() == touched_cells.nbCells()
299 && intersected_cells.subset( touched_cells );
302 //-----------------------------------------------------------------------------
303 template <typename TKSpace>
305 DGtal::DigitalConvexity<TKSpace>::
306 isFullyConvex( const LatticePolytope& P ) const
308 auto S = insidePoints( P );
309 for ( Dimension k = 1; k < KSpace::dimension; ++ k )
311 auto touched_cells = makeCellCover( S.begin(), S.end(), k, k );
312 auto intersected_cells = makeCellCover( P, k, k );
313 if ( ( intersected_cells.nbCells() != touched_cells.nbCells() )
314 || ( ! intersected_cells.subset( touched_cells ) ) )
320 //-----------------------------------------------------------------------------
321 template <typename TKSpace>
323 DGtal::DigitalConvexity<TKSpace>::
324 isKSubconvex( const LatticePolytope& P, const CellGeometry& C, const Dimension k ) const
326 auto intersected_cells = makeCellCover( P, k, k );
327 return intersected_cells.subset( C );
329 //-----------------------------------------------------------------------------
330 template <typename TKSpace>
332 DGtal::DigitalConvexity<TKSpace>::
333 isFullySubconvex( const LatticePolytope& P, const CellGeometry& C ) const
335 auto intersected_cells = makeCellCover( P, C.minCellDim(), C.maxCellDim() );
336 return intersected_cells.subset( C );
339 //-----------------------------------------------------------------------------
340 template <typename TKSpace>
342 DGtal::DigitalConvexity<TKSpace>::
343 isKConvex( const RationalPolytope& P, const Dimension k ) const
345 if ( k == 0 ) return true;
346 auto S = insidePoints( P );
347 auto touched_cells = makeCellCover( S.begin(), S.end(), k, k );
348 auto intersected_cells = makeCellCover( P, k, k );
349 return intersected_cells.nbCells() == touched_cells.nbCells()
350 && intersected_cells.subset( touched_cells );
353 //-----------------------------------------------------------------------------
354 template <typename TKSpace>
356 DGtal::DigitalConvexity<TKSpace>::
357 isFullyConvex( const RationalPolytope& P ) const
359 auto S = insidePoints( P );
360 for ( Dimension k = 1; k < KSpace::dimension; ++ k )
362 auto touched_cells = makeCellCover( S.begin(), S.end(), k, k );
363 auto intersected_cells = makeCellCover( P, k, k );
364 if ( ( intersected_cells.nbCells() != touched_cells.nbCells() )
365 || ( ! intersected_cells.subset( touched_cells ) ) )
371 //-----------------------------------------------------------------------------
372 template <typename TKSpace>
374 DGtal::DigitalConvexity<TKSpace>::
375 isKSubconvex( const RationalPolytope& P, const CellGeometry& C,
376 const Dimension k ) const
378 auto intersected_cells = makeCellCover( P, k, k );
379 return intersected_cells.subset( C );
381 //-----------------------------------------------------------------------------
382 template <typename TKSpace>
384 DGtal::DigitalConvexity<TKSpace>::
385 isFullySubconvex( const RationalPolytope& P, const CellGeometry& C ) const
387 auto intersected_cells = makeCellCover( P, C.minCellDim(), C.maxCellDim() );
388 return intersected_cells.subset( C );
391 ///////////////////////////////////////////////////////////////////////////////
392 // Interface - public :
395 * Writes/Displays the object on an output stream.
396 * @param out the output stream where the object is written.
398 template <typename TKSpace>
401 DGtal::DigitalConvexity<TKSpace>::selfDisplay ( std::ostream & out ) const
403 out << "[DigitalConvexity]";
407 * Checks the validity/consistency of the object.
408 * @return 'true' if the object is valid, 'false' otherwise.
410 template <typename TKSpace>
413 DGtal::DigitalConvexity<TKSpace>::isValid() const
419 ///////////////////////////////////////////////////////////////////////////////
420 // Implementation of inline functions //
422 //-----------------------------------------------------------------------------
423 template <typename TKSpace>
426 DGtal::operator<< ( std::ostream & out,
427 const DigitalConvexity<TKSpace> & object )
429 object.selfDisplay( out );
434 ///////////////////////////////////////////////////////////////////////////////