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 BoundedLatticePolytopeCounter.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 BoundedLatticePolytopeCounter.h
26 * This file is part of the DGtal library.
30 //////////////////////////////////////////////////////////////////////////////
32 //////////////////////////////////////////////////////////////////////////////
34 ///////////////////////////////////////////////////////////////////////////////
35 // IMPLEMENTATION of inline methods.
36 ///////////////////////////////////////////////////////////////////////////////
38 ///////////////////////////////////////////////////////////////////////////////
39 // ----------------------- Standard services ------------------------------
41 //-----------------------------------------------------------------------------
42 template <typename TSpace>
43 DGtal::BoundedLatticePolytopeCounter<TSpace>::
44 BoundedLatticePolytopeCounter
50 //-----------------------------------------------------------------------------
51 template <typename TSpace>
53 DGtal::BoundedLatticePolytopeCounter<TSpace>::
55 ( const Polytope* ptrP )
58 if ( ptrP == nullptr ) return;
59 myLower = ptrP->getDomain().lowerBound();
60 myUpper = ptrP->getDomain().upperBound();
64 //-----------------------------------------------------------------------------
65 template <typename TSpace>
66 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Interval
67 DGtal::BoundedLatticePolytopeCounter<TSpace>::
68 intersectionIntervalAlongAxis( Point p, Dimension a ) const
70 ASSERT( myPolytope != nullptr );
71 const Polytope& P = *myPolytope;
72 const InequalityMatrix& A = P.getA();
73 const InequalityVector& B = P.getB();
74 const std::vector<bool>& I = P.getI();
75 Integer x_min = myLower[ a ];
76 Integer x_max = myUpper[ a ]+1;
78 const Integer x_a = x_min;
81 for ( Dimension k = 2*dimension; k < A.size(); k++ )
83 const Integer c = A[ k ].dot( p );
84 const Integer n = A[ k ][ a ];
85 const Integer b = B[ k ];
87 { // constraint is // to the specified axis.
88 empty = ! ( I[ k ] ? ( c <= b ) : c < b );
93 if ( d < 0 ) empty = true;
96 x = I[ k ] ? ( d / n + 1 ) : ( (d+n-1) / n ) ;
97 x_max = std::min( x_max, x_a + x );
105 x = I[ k ] ? ( (d-n-1) / -n ) : ( d / -n + 1 );
106 x_min = std::max( x_min, x_a + x );
108 // otherwise the constraint is true
110 if ( empty || ( x_max <= x_min ) ) return Interval( 0, 0 );
112 return Interval( x_min, x_max );
115 //-----------------------------------------------------------------------------
116 template <typename TSpace>
117 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Interval
118 DGtal::BoundedLatticePolytopeCounter<TSpace>::
119 interiorIntersectionIntervalAlongAxis( Point p, Dimension a ) const
121 ASSERT( myPolytope != nullptr );
122 const Polytope& P = *myPolytope;
123 const InequalityMatrix& A = P.getA();
124 const InequalityVector& B = P.getB();
125 Integer x_min = myLower[ a ];
126 Integer x_max = myUpper[ a ]+1;
128 const Integer x_a = x_min;
131 for ( Dimension k = 2*dimension; k < A.size(); k++ )
133 const Integer c = A[ k ].dot( p );
134 const Integer n = A[ k ][ a ];
135 const Integer b = B[ k ];
137 { // constraint is // to the specified axis.
143 if ( d < 0 ) empty = true;
147 x_max = std::min( x_max, x_a + x );
156 x_min = std::max( x_min, x_a + x );
158 // otherwise the constraint is true
160 // std::cout << " (" << empty << ":" << x_min << "," << x_max << ")";
161 if ( empty || ( x_max <= x_min ) ) return Interval( 0, 0 );
163 return Interval( x_min, x_max );
166 //-----------------------------------------------------------------------------
167 template <typename TSpace>
168 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Integer
169 DGtal::BoundedLatticePolytopeCounter<TSpace>::
170 countAlongAxis( Dimension a ) const
172 ASSERT( myPolytope != nullptr );
180 auto I = intersectionIntervalAlongAxis( p, a );
181 nb += I.second - I.first;
186 //-----------------------------------------------------------------------------
187 template <typename TSpace>
188 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Integer
189 DGtal::BoundedLatticePolytopeCounter<TSpace>::
190 countInteriorAlongAxis( Dimension a ) const
192 ASSERT( myPolytope != nullptr );
200 auto I = interiorIntersectionIntervalAlongAxis( p, a );
201 nb += I.second - I.first;
206 //-----------------------------------------------------------------------------
207 template <typename TSpace>
209 DGtal::BoundedLatticePolytopeCounter<TSpace>::
210 getPointsAlongAxis( PointRange& pts, Dimension a ) const
212 ASSERT( myPolytope != nullptr );
219 auto I = intersectionIntervalAlongAxis( p, a );
221 for ( Integer x = I.first; x != I.second; x++ )
229 //-----------------------------------------------------------------------------
230 template <typename TSpace>
232 DGtal::BoundedLatticePolytopeCounter<TSpace>::
233 getInteriorPointsAlongAxis( PointRange& pts, Dimension a ) const
235 ASSERT( myPolytope != nullptr );
240 //Integer nb = 0; not used
243 auto I = interiorIntersectionIntervalAlongAxis( p, a );
245 for ( Integer x = I.first; x != I.second; x++ )
254 //-----------------------------------------------------------------------------
255 template <typename TSpace>
256 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::LatticeSetByInterval
257 DGtal::BoundedLatticePolytopeCounter<TSpace>::
258 getLatticeSet( Dimension a ) const
260 ASSERT( myPolytope != nullptr );
266 LatticeSetByInterval L;
269 auto I = intersectionIntervalAlongAxis( p, a );
274 //-----------------------------------------------------------------------------
275 template <typename TSpace>
276 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::LatticeSetByInterval
277 DGtal::BoundedLatticePolytopeCounter<TSpace>::
278 getLatticeCells( Dimension a ) const
280 ASSERT( myPolytope != nullptr );
286 LatticeSetByInterval L; //< stores the intersected cells
287 const Point One = Point::diagonal( 1 );
291 q = 2*p - One; q[ a ] = 0;
292 const auto I = intersectionIntervalAlongAxis( p, a );
293 const auto n = I.second - I.first;
296 // Now the second bound is included
297 L[ q ] = Interval( 2 * I.first - 1, 2 * I.second - 3 );
300 // It remains to compute all the k-cells, 0 <= k < d, intersected by Cvxh( Z )
301 for ( Dimension k = 0; k < dimension; k++ )
303 if ( k == a ) continue;
304 std::vector< Point > q_computed;
305 std::vector< Interval > I_computed;
306 for ( const auto& value : L )
308 Point p = value.first;
309 Interval I = value.second;
310 Point r = p; r[ k ] += 2;
311 const auto it = L.find( r );
312 if ( it == L.end() ) continue; // neighbor is empty
313 // Otherwise compute common part.
314 Interval J = it->second;
315 auto f = std::max( I.first, J.first );
316 auto s = std::min( I.second, J.second );
319 Point qq = p; qq[ k ] += 1;
320 q_computed.push_back( qq );
321 I_computed.push_back( Interval( f, s ) );
324 // Add new columns to map Point -> column
325 for ( typename Point::Index i = 0; i < q_computed.size(); ++i )
327 L[ q_computed[ i ] ] = I_computed[ i ];
333 //-----------------------------------------------------------------------------
334 template <typename TSpace>
336 DGtal::BoundedLatticePolytopeCounter<TSpace>::
339 ASSERT( myPolytope != nullptr );
341 auto b_size = myUpper[ 0 ] - myLower[ 0 ];
342 for ( Dimension a = 1; a < dimension; a++ )
344 const auto a_size = myUpper[ a ] - myLower[ a ];
345 if ( b_size < a_size ) { b = a; b_size = a_size; }
352 ///////////////////////////////////////////////////////////////////////////////