DGtal  1.5.beta
BoundedLatticePolytopeCounter.ih
1 /**
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.
6  *
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.
11  *
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/>.
14  *
15  **/
16 
17 /**
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
21  *
22  * @date 2022/06/17
23  *
24  * Implementation of inline methods defined in BoundedLatticePolytopeCounter.h
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 #include <cstdlib>
32 //////////////////////////////////////////////////////////////////////////////
33 
34 ///////////////////////////////////////////////////////////////////////////////
35 // IMPLEMENTATION of inline methods.
36 ///////////////////////////////////////////////////////////////////////////////
37 
38 ///////////////////////////////////////////////////////////////////////////////
39 // ----------------------- Standard services ------------------------------
40 
41 //-----------------------------------------------------------------------------
42 template <typename TSpace>
43 DGtal::BoundedLatticePolytopeCounter<TSpace>::
44 BoundedLatticePolytopeCounter
45 ( const Polytope& P )
46 {
47  init( &P );
48 }
49 
50 //-----------------------------------------------------------------------------
51 template <typename TSpace>
52 void
53 DGtal::BoundedLatticePolytopeCounter<TSpace>::
54 init
55 ( const Polytope* ptrP )
56 {
57  myPolytope = ptrP;
58  if ( ptrP == nullptr ) return;
59  myLower = ptrP->getDomain().lowerBound();
60  myUpper = ptrP->getDomain().upperBound();
61 }
62 
63 
64 //-----------------------------------------------------------------------------
65 template <typename TSpace>
66 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Interval
67 DGtal::BoundedLatticePolytopeCounter<TSpace>::
68 intersectionIntervalAlongAxis( Point p, Dimension a ) const
69 {
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;
77  Integer x = 0;
78  const Integer x_a = x_min;
79  p[ a ] = x_a;
80  bool empty = false;
81  for ( Dimension k = 2*dimension; k < A.size(); k++ )
82  {
83  const Integer c = A[ k ].dot( p );
84  const Integer n = A[ k ][ a ];
85  const Integer b = B[ k ];
86  if ( n == 0 )
87  { // constraint is // to the specified axis.
88  empty = ! ( I[ k ] ? ( c <= b ) : c < b );
89  }
90  else if ( n > 0 )
91  {
92  Integer d = b - c;
93  if ( d < 0 ) empty = true;
94  else
95  {
96  x = I[ k ] ? ( d / n + 1 ) : ( (d+n-1) / n ) ;
97  x_max = std::min( x_max, x_a + x );
98  }
99  }
100  else // ( n < 0 )
101  {
102  Integer d = c - b;
103  if ( d >= 0 )
104  {
105  x = I[ k ] ? ( (d-n-1) / -n ) : ( d / -n + 1 );
106  x_min = std::max( x_min, x_a + x );
107  }
108  // otherwise the constraint is true
109  }
110  if ( empty || ( x_max <= x_min ) ) return Interval( 0, 0 );
111  }
112  return Interval( x_min, x_max );
113 }
114 
115 //-----------------------------------------------------------------------------
116 template <typename TSpace>
117 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Interval
118 DGtal::BoundedLatticePolytopeCounter<TSpace>::
119 interiorIntersectionIntervalAlongAxis( Point p, Dimension a ) const
120 {
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;
127  Integer x = 0;
128  const Integer x_a = x_min;
129  p[ a ] = x_a;
130  bool empty = false;
131  // We must take into account also bounding box constraints for interior points.
132  for ( Dimension k = 0; k < A.size(); k++ )
133  {
134  const Integer c = A[ k ].dot( p );
135  const Integer n = A[ k ][ a ];
136  const Integer b = B[ k ];
137  if ( n == 0 )
138  { // constraint is // to the specified axis.
139  empty = ( b <= c );
140  }
141  else if ( n > 0 )
142  {
143  Integer d = b - c;
144  if ( d < 0 ) empty = true;
145  else
146  {
147  x = (d+n-1) / n;
148  x_max = std::min( x_max, x_a + x );
149  }
150  }
151  else // ( n < 0 )
152  {
153  Integer d = c - b;
154  if ( d >= 0 )
155  {
156  x = d / -n + 1;
157  x_min = std::max( x_min, x_a + x );
158  }
159  // otherwise the constraint is true
160  }
161  // std::cout << " (" << empty << ":" << x_min << "," << x_max << ")";
162  if ( empty || ( x_max <= x_min ) ) return Interval( 0, 0 );
163  }
164  return Interval( x_min, x_max );
165 }
166 
167 //-----------------------------------------------------------------------------
168 template <typename TSpace>
169 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Integer
170 DGtal::BoundedLatticePolytopeCounter<TSpace>::
171 countAlongAxis( Dimension a ) const
172 {
173  ASSERT( myPolytope != nullptr );
174  Point lo = myLower;
175  Point hi = myUpper;
176  hi[ a ] = lo[ a ];
177  Domain D( lo, hi );
178  Integer nb = 0;
179  for ( auto&& p : D )
180  {
181  auto I = intersectionIntervalAlongAxis( p, a );
182  nb += I.second - I.first;
183  }
184  return nb;
185 }
186 
187 //-----------------------------------------------------------------------------
188 template <typename TSpace>
189 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::Integer
190 DGtal::BoundedLatticePolytopeCounter<TSpace>::
191 countInteriorAlongAxis( Dimension a ) const
192 {
193  ASSERT( myPolytope != nullptr );
194  Point lo = myLower;
195  Point hi = myUpper;
196  hi[ a ] = lo[ a ];
197  Domain D( lo, hi );
198  Integer nb = 0;
199  for ( auto&& p : D )
200  {
201  auto I = interiorIntersectionIntervalAlongAxis( p, a );
202  nb += I.second - I.first;
203  }
204  return nb;
205 }
206 
207 //-----------------------------------------------------------------------------
208 template <typename TSpace>
209 void
210 DGtal::BoundedLatticePolytopeCounter<TSpace>::
211 getPointsAlongAxis( PointRange& pts, Dimension a ) const
212 {
213  ASSERT( myPolytope != nullptr );
214  Point lo = myLower;
215  Point hi = myUpper;
216  hi[ a ] = lo[ a ];
217  Domain D( lo, hi );
218  for ( auto&& p : D )
219  {
220  auto I = intersectionIntervalAlongAxis( p, a );
221  Point q = p;
222  for ( Integer x = I.first; x != I.second; x++ )
223  {
224  q[ a ] = x;
225  pts.push_back( q );
226  }
227  }
228 }
229 
230 //-----------------------------------------------------------------------------
231 template <typename TSpace>
232 void
233 DGtal::BoundedLatticePolytopeCounter<TSpace>::
234 getInteriorPointsAlongAxis( PointRange& pts, Dimension a ) const
235 {
236  ASSERT( myPolytope != nullptr );
237  Point lo = myLower;
238  Point hi = myUpper;
239  hi[ a ] = lo[ a ];
240  Domain D( lo, hi );
241  //Integer nb = 0; not used
242  for ( auto&& p : D )
243  {
244  auto I = interiorIntersectionIntervalAlongAxis( p, a );
245  Point q = p;
246  for ( Integer x = I.first; x != I.second; x++ )
247  {
248  q[ a ] = x;
249  pts.push_back( q );
250  }
251  }
252 }
253 
254 
255 //-----------------------------------------------------------------------------
256 template <typename TSpace>
257 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::LatticeSetByInterval
258 DGtal::BoundedLatticePolytopeCounter<TSpace>::
259 getLatticeSet( Dimension a ) const
260 {
261  ASSERT( myPolytope != nullptr );
262  Point lo = myLower;
263  Point hi = myUpper;
264  hi[ a ] = 0;
265  lo[ a ] = 0;
266  Domain D( lo, hi );
267  LatticeSetByInterval L;
268  for ( auto&& p : D )
269  {
270  auto I = intersectionIntervalAlongAxis( p, a );
271  L[ p ] = I;
272  }
273 }
274 
275 //-----------------------------------------------------------------------------
276 template <typename TSpace>
277 typename DGtal::BoundedLatticePolytopeCounter<TSpace>::LatticeSetByInterval
278 DGtal::BoundedLatticePolytopeCounter<TSpace>::
279 getLatticeCells( Dimension a ) const
280 {
281  ASSERT( myPolytope != nullptr );
282  Point lo = myLower;
283  Point hi = myUpper;
284  hi[ a ] = 0;
285  lo[ a ] = 0;
286  Domain D( lo, hi );
287  LatticeSetByInterval L; //< stores the intersected cells
288  const Point One = Point::diagonal( 1 );
289  Point q;
290  for ( auto&& p : D )
291  {
292  q = 2*p - One; q[ a ] = 0;
293  const auto I = intersectionIntervalAlongAxis( p, a );
294  const auto n = I.second - I.first;
295  if ( n != 0 )
296  {
297  // Now the second bound is included
298  L[ q ] = Interval( 2 * I.first - 1, 2 * I.second - 3 );
299  }
300  }
301  // It remains to compute all the k-cells, 0 <= k < d, intersected by Cvxh( Z )
302  for ( Dimension k = 0; k < dimension; k++ )
303  {
304  if ( k == a ) continue;
305  std::vector< Point > q_computed;
306  std::vector< Interval > I_computed;
307  for ( const auto& value : L )
308  {
309  Point p = value.first;
310  Interval I = value.second;
311  Point r = p; r[ k ] += 2;
312  const auto it = L.find( r );
313  if ( it == L.end() ) continue; // neighbor is empty
314  // Otherwise compute common part.
315  Interval J = it->second;
316  auto f = std::max( I.first, J.first );
317  auto s = std::min( I.second, J.second );
318  if ( f <= s )
319  {
320  Point qq = p; qq[ k ] += 1;
321  q_computed.push_back( qq );
322  I_computed.push_back( Interval( f, s ) );
323  }
324  }
325  // Add new columns to map Point -> column
326  for ( typename Point::Index i = 0; i < q_computed.size(); ++i )
327  {
328  L[ q_computed[ i ] ] = I_computed[ i ];
329  }
330  }
331  return L;
332 }
333 
334 //-----------------------------------------------------------------------------
335 template <typename TSpace>
336 DGtal::Dimension
337 DGtal::BoundedLatticePolytopeCounter<TSpace>::
338 longestAxis( ) const
339 {
340  ASSERT( myPolytope != nullptr );
341  Dimension b = 0;
342  auto b_size = myUpper[ 0 ] - myLower[ 0 ];
343  for ( Dimension a = 1; a < dimension; a++ )
344  {
345  const auto a_size = myUpper[ a ] - myLower[ a ];
346  if ( b_size < a_size ) { b = a; b_size = a_size; }
347  }
348  return b;
349 }
350 
351 
352 // //
353 ///////////////////////////////////////////////////////////////////////////////