util.cpp
Go to the documentation of this file.
1 // ========================================================================================
2 // ApproxMVBB
3 // Copyright (C) 2014 by Gabriel Nützi <nuetzig (at) imes (d0t) mavt (d0t) ethz (døt) ch>
4 //
5 // This Source Code Form is subject to the terms of the Mozilla Public
6 // License, v. 2.0. If a copy of the MPL was not distributed with this
7 // file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 // ========================================================================================
9 
10 #include <iostream>
11 #include <limits>
12 
13 #include <ApproxMVBB/Diameter/Utils/util.hpp>
14 
15 namespace ApproxMVBB{
16 namespace Diameter{
17 
18 /* partially sort a list of points
19 
20  given a "diameter", points which are 'outside'
21  the sphere with a given threshold are put at the beginning
22  of the list,
23  the returned value is the index of the last point 'outside'
24  ie
25  points from #first to #index are outside
26  " " #index+1 to #last are inside
27 
28  If there are no points outside, #first-1 is returned.
29 
30  Given a segment [AB], its centre C is (A+B)/2.
31  The dot product MA.MB is equal to MC^2 - |AB|^2 / 4
32 
33  1. Being naive, ie to test if points are outside
34  the ball of diameter [AB], yield to condition
35  MA.MB > 0
36 
37  2. Being a little smarter, ie to test if points are outside
38  the ball of center (A+B)/2 and diameter D (assume D>|AB|)
39  yield to condition
40  MA.MB > ( D^2 - |AB|^2 ) / 4
41 
42 */
43 
44 int _LastPointOutsideSphereWithDiameter( TypeSegment *theSeg,
45  const double squareDiameter,
46  const double **theList,
47  const int first,
48  int *last,
49  const int dim,
50  const int _reduction_mode_ )
51 {
52  int i;
53  int index = first - 1;
54  int l = *last;
55 
56  double mamb, am2;
57 
58  double minThreshold;
59  double medThreshold;
60  double maxThreshold;
61 
62  double ab = sqrt( theSeg->squareDiameter );
63  double ab2 = theSeg->squareDiameter;
64 
65  double R = sqrt( squareDiameter );
66  double R2 = squareDiameter;
67 
68  if ( first > *last ) return( first - 1 );
69 
70  if ( squareDiameter <= theSeg->squareDiameter ) {
71 
72  maxThreshold = medThreshold = 0.0;
73  minThreshold = -0.23205080756887729352 * theSeg->squareDiameter;
74 
75  } else {
76 
77  minThreshold = (R - .86602540378443864676*ab)
78  * (R - .86602540378443864676*ab)
79  - 0.25 * ab2;
80 
81  medThreshold = 0.5 * ab2 + 0.25 * R2
82  - .43301270189221932338 * R * sqrt( 4 * ab2 - R2 );
83 
84  maxThreshold = 0.25 * (R2 - ab2);
85  }
86 
87 
88 
89  /* 0 : no reduction
90  1 : just inside the smallest sphere
91  2 : complete reduction
92  */
93  switch ( _reduction_mode_ ) {
94 
95  case 0 :
96 
97  /* NO REDUCTION CASE
98  */
99  if ( dim == 2 ) {
100  for ( i=first; i<=l; i++ ) {
101  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
102  theList[i], theSeg->extremity2 );
103  if ( mamb > maxThreshold ) {
104  index ++;
105  _SwapPoints( theList, index, i );
106  }
107  }
108  return( index );
109  }
110 
111  if ( dim == 3 ) {
112  for ( i=first; i<=l; i++ ) {
113  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
114  theList[i], theSeg->extremity2 );
115  if ( mamb > maxThreshold ) {
116  index ++;
117  _SwapPoints( theList, index, i );
118  }
119  }
120  return( index );
121  }
122 
123  for ( i=first; i<=l; i++ ) {
124  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
125  theList[i], theSeg->extremity2, dim );
126  if ( mamb > maxThreshold ) {
127  index ++;
128  _SwapPoints( theList, index, i );
129  }
130  }
131  return( index );
132 
133  /* END
134  NO REDUCTION CASE
135  */
136  break;
137 
138  default :
139  case 1 :
140 
141  /* REDUCTION INSIDE THE SMALLEST SPHERE
142  */
143 
144  if ( dim == 2 ) {
145  for ( i=first; i<=l; i++ ) {
146  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
147  theList[i], theSeg->extremity2 );
148  if ( mamb > maxThreshold ) {
149  index ++;
150  _SwapPoints( theList, index, i );
151  }
152  else if ( mamb <= minThreshold ) {
153  _SwapPoints( theList, i, l );
154  i--; l--;
155  }
156  }
157  *last = l;
158  return( index );
159  }
160 
161  if ( dim == 3 ) {
162  for ( i=first; i<=l; i++ ) {
163  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
164  theList[i], theSeg->extremity2 );
165  if ( mamb > maxThreshold ) {
166  index ++;
167  _SwapPoints( theList, index, i );
168  }
169  else if ( mamb <= minThreshold ) {
170  _SwapPoints( theList, i, l );
171  i--; l--;
172  }
173  }
174  *last = l;
175  return( index );
176  }
177 
178  for ( i=first; i<=l; i++ ) {
179  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
180  theList[i], theSeg->extremity2, dim );
181  if ( mamb > maxThreshold ) {
182  index ++;
183  _SwapPoints( theList, index, i );
184  }
185  else if ( mamb <= minThreshold ) {
186  _SwapPoints( theList, i, l );
187  i--; l--;
188  }
189  }
190  *last = l;
191  return( index );
192 
193  /* END
194  REDUCTION INSIDE THE SMALLEST SPHERE
195  */
196  break;
197 
198  case 2 :
199 
200  /* COMPLETE REDUCTION
201 
202  On suppose implicitement
203  que l'ensemble des points est
204  compris dans l'intersection des spheres centrees
205  sur A et B et de rayon |AB|.
206  En effet, les conditions (pour un rayon dans
207  l'intervalle [min,med]) pour l'elimination ne le
208  verifient pas.
209  */
210  if ( dim == 2 ) {
211 
212  if ( squareDiameter <= theSeg->squareDiameter ) {
213 
214  for ( i=first; i<=l; i++ ) {
215  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
216  theList[i], theSeg->extremity2 );
217  if ( mamb > maxThreshold ) {
218  index ++;
219  _SwapPoints( theList, index, i );
220  }
221  else if ( mamb > minThreshold ) {
222  am2 = _SquareDistance2D( theList[i], theSeg->extremity1 );
223  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) ) - mamb*mamb < 0 ) {
224  _SwapPoints( theList, i, l );
225  i--; l--;
226  }
227  }
228  else {
229  /* if ( mamb <= minThreshold ) */
230  _SwapPoints( theList, i, l );
231  i--; l--;
232  }
233  }
234 
235  } else {
236 
237  for ( i=first; i<=l; i++ ) {
238  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
239  theList[i], theSeg->extremity2 );
240  if ( mamb > maxThreshold ) {
241  index ++;
242  _SwapPoints( theList, index, i );
243  }
244  else if ( mamb > medThreshold ) {
245  continue;
246  }
247  else if ( mamb > minThreshold ) {
248  am2 = _SquareDistance2D( theList[i], theSeg->extremity1 );
249  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
250  - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
251  _SwapPoints( theList, i, l );
252  i--; l--;
253  }
254  }
255  else {
256  /* if ( mamb <= minThreshold ) */
257  _SwapPoints( theList, i, l );
258  i--; l--;
259  }
260  }
261 
262  }
263  *last = l;
264  return( index );
265  }
266 
267  if ( dim == 3 ) {
268 
269  if ( squareDiameter <= theSeg->squareDiameter ) {
270 
271  for ( i=first; i<=l; i++ ) {
272  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
273  theList[i], theSeg->extremity2 );
274  if ( mamb > maxThreshold ) {
275  index ++;
276  _SwapPoints( theList, index, i );
277  }
278  else if ( mamb > minThreshold ) {
279  am2 = _SquareDistance3D( theList[i], theSeg->extremity1 );
280  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) ) - mamb*mamb < 0 ) {
281  _SwapPoints( theList, i, l );
282  i--; l--;
283  }
284  }
285  else {
286  /* if ( mamb <= minThreshold ) */
287  _SwapPoints( theList, i, l );
288  i--; l--;
289  }
290  }
291 
292  } else {
293 
294  for ( i=first; i<=l; i++ ) {
295  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
296  theList[i], theSeg->extremity2 );
297  if ( mamb > maxThreshold ) {
298  index ++;
299  _SwapPoints( theList, index, i );
300  }
301  else if ( mamb > medThreshold ) {
302  continue;
303  }
304  else if ( mamb > minThreshold ) {
305  am2 = _SquareDistance3D( theList[i], theSeg->extremity1 );
306  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
307  - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
308  _SwapPoints( theList, i, l );
309  i--; l--;
310  }
311  }
312  else {
313  /* if ( mamb <= minThreshold ) */
314  _SwapPoints( theList, i, l );
315  i--; l--;
316  }
317  }
318 
319  }
320  *last = l;
321  return( index );
322  }
323 
324  if ( squareDiameter <= theSeg->squareDiameter ) {
325 
326  for ( i=first; i<=l; i++ ) {
327  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
328  theList[i], theSeg->extremity2, dim );
329  if ( mamb > maxThreshold ) {
330  index ++;
331  _SwapPoints( theList, index, i );
332  }
333  else if ( mamb > minThreshold ) {
334  am2 = _SquareDistance( theList[i], theSeg->extremity1, dim );
335  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) ) - mamb*mamb < 0 ) {
336  _SwapPoints( theList, i, l );
337  i--; l--;
338  }
339  }
340  else {
341  /* if ( mamb <= minThreshold ) */
342  _SwapPoints( theList, i, l );
343  i--; l--;
344  }
345  }
346 
347  } else {
348 
349  for ( i=first; i<=l; i++ ) {
350  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
351  theList[i], theSeg->extremity2, dim );
352  if ( mamb > maxThreshold ) {
353  index ++;
354  _SwapPoints( theList, index, i );
355  }
356  else if ( mamb > medThreshold ) {
357  continue;
358  }
359  else if ( mamb > minThreshold ) {
360  am2 = _SquareDistance( theList[i], theSeg->extremity1, dim );
361  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
362  - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
363  _SwapPoints( theList, i, l );
364  i--; l--;
365  }
366  }
367  else {
368  /* if ( mamb <= minThreshold ) */
369  _SwapPoints( theList, i, l );
370  i--; l--;
371  }
372  }
373 
374  }
375  *last = l;
376  return( index );
377 
378  /* END
379  COMPLETE REDUCTION
380  */
381  }
382  return( -1 );
383 }
384 
385 
386 int _LastPointOutsideSphereAndBoundWithDiameter( TypeSegment *theSeg,
387  const double squareDiameter,
388  const double **theList,
389  const int first,
390  int *last,
391  const int dim,
392  const int _reduction_mode_,
393  double *bound )
394 {
395  int i;
396  int index = first - 1;
397  int l = *last;
398 
399  double mamb, am2;
400 
401  double minThreshold;
402  double medThreshold;
403  double maxThreshold;
404 
405  double ab = sqrt( theSeg->squareDiameter );
406  double ab2 = theSeg->squareDiameter;
407 
408  double R = sqrt( squareDiameter );
409  double R2 = squareDiameter;
410 
411  /* bound
412  c'est la plus grande valeur pour les points
413  l'interieur de la sphere
414  si squareDiameter > theSeg->squareDiameter
415  cette valeur peut etre positive
416  */
417  double b = *bound = (- theSeg->squareDiameter * 0.25);
418 
419 
420  if ( squareDiameter <= theSeg->squareDiameter ) {
421 
422  maxThreshold = medThreshold = 0.0;
423  minThreshold = -0.23205080756887729352 * theSeg->squareDiameter;
424 
425  return( _LastPointOutsideSphereWithDiameter( theSeg, squareDiameter,
426  theList, first, last, dim,
427  _reduction_mode_ ) );
428 
429  } else {
430 
431  minThreshold = (R - .86602540378443864676*ab)
432  * (R - .86602540378443864676*ab)
433  - 0.25 * ab2;
434 
435  medThreshold = 0.5 * ab2 + 0.25 * R2
436  - .43301270189221932338 * R * sqrt( 4 * ab2 - R2 );
437 
438  maxThreshold = 0.25 * (R2 - ab2);
439  }
440 
441 
442 
443  /* 0 : no reduction
444  1 : just inside the smallest sphere
445  2 : complete reduction
446  */
447  switch ( _reduction_mode_ ) {
448 
449  case 0 :
450 
451  /* NO REDUCTION CASE
452  */
453  if ( dim == 2 ) {
454  for ( i=first; i<=l; i++ ) {
455  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
456  theList[i], theSeg->extremity2 );
457  if ( mamb > maxThreshold ) {
458  index ++;
459  _SwapPoints( theList, index, i );
460  continue;
461  }
462  if ( b < mamb ) b = mamb;
463  }
464  *bound = b;
465  return( index );
466  }
467 
468  if ( dim == 3 ) {
469  for ( i=first; i<=l; i++ ) {
470  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
471  theList[i], theSeg->extremity2 );
472  if ( mamb > maxThreshold ) {
473  index ++;
474  _SwapPoints( theList, index, i );
475  continue;
476  }
477  if ( b < mamb ) b = mamb;
478  }
479  *bound = b;
480  return( index );
481  }
482 
483  for ( i=first; i<=l; i++ ) {
484  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
485  theList[i], theSeg->extremity2, dim );
486  if ( mamb > maxThreshold ) {
487  index ++;
488  _SwapPoints( theList, index, i );
489  continue;
490  }
491  if ( b < mamb ) b = mamb;
492  }
493  *bound = b;
494  return( index );
495 
496  /* END
497  NO REDUCTION CASE
498  */
499  break;
500 
501  default :
502  case 1 :
503 
504  /* REDUCTION INSIDE THE SMALLEST SPHERE
505  */
506 
507  if ( dim == 2 ) {
508  for ( i=first; i<=l; i++ ) {
509  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
510  theList[i], theSeg->extremity2 );
511  if ( mamb > maxThreshold ) {
512  index ++;
513  _SwapPoints( theList, index, i );
514  continue;
515  }
516  if ( mamb <= minThreshold ) {
517  _SwapPoints( theList, i, l );
518  i--; l--;
519  continue;
520  }
521  if ( b < mamb ) b = mamb;
522  }
523  *last = l;
524  *bound = b;
525  return( index );
526  }
527 
528  if ( dim == 3 ) {
529  for ( i=first; i<=l; i++ ) {
530  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
531  theList[i], theSeg->extremity2 );
532  if ( mamb > maxThreshold ) {
533  index ++;
534  _SwapPoints( theList, index, i );
535  continue;
536  }
537  if ( mamb <= minThreshold ) {
538  _SwapPoints( theList, i, l );
539  i--; l--;
540  continue;
541  }
542  if ( b < mamb ) b = mamb;
543  }
544  *last = l;
545  *bound = b;
546  return( index );
547  }
548 
549  for ( i=first; i<=l; i++ ) {
550  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
551  theList[i], theSeg->extremity2, dim );
552  if ( mamb > maxThreshold ) {
553  index ++;
554  _SwapPoints( theList, index, i );
555  continue;
556  }
557  if ( mamb <= minThreshold ) {
558  _SwapPoints( theList, i, l );
559  i--; l--;
560  continue;
561  }
562  if ( b < mamb ) b = mamb;
563  }
564  *last = l;
565  *bound = b;
566  return( index );
567 
568  /* END
569  REDUCTION INSIDE THE SMALLEST SPHERE
570  */
571  break;
572 
573  case 2 :
574 
575  /* COMPLETE REDUCTION
576 
577  On suppose implicitement
578  que l'ensemble des points est
579  compris dans l'intersection des spheres centrees
580  sur A et B et de rayon |AB|.
581  En effet, les conditions (pour un rayon dans
582  l'intervalle [min,med]) pour l'elimination ne le
583  verifient pas.
584  */
585  if ( dim == 2 ) {
586 
587  if ( squareDiameter <= theSeg->squareDiameter ) {
588 
589  for ( i=first; i<=l; i++ ) {
590  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
591  theList[i], theSeg->extremity2 );
592  if ( mamb > maxThreshold ) {
593  index ++;
594  _SwapPoints( theList, index, i );
595  continue;
596  }
597  if ( mamb > minThreshold ) {
598  am2 = _SquareDistance2D( theList[i], theSeg->extremity1 );
599  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) ) - mamb*mamb < 0 ) {
600  _SwapPoints( theList, i, l );
601  i--; l--;
602  continue;
603  }
604  if ( b < mamb ) b = mamb;
605  continue;
606  }
607  /* if ( mamb <= minThreshold ) */
608  _SwapPoints( theList, i, l );
609  i--; l--;
610  }
611 
612  } else {
613 
614  for ( i=first; i<=l; i++ ) {
615  mamb = _ScalarProduct2D( theList[i], theSeg->extremity1,
616  theList[i], theSeg->extremity2 );
617  if ( mamb > maxThreshold ) {
618  index ++;
619  _SwapPoints( theList, index, i );
620  continue;
621  }
622  if ( mamb > medThreshold ) {
623  if ( b < mamb ) b = mamb;
624  continue;
625  }
626  if ( mamb > minThreshold ) {
627  am2 = _SquareDistance2D( theList[i], theSeg->extremity1 );
628  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
629  - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
630  _SwapPoints( theList, i, l );
631  i--; l--;
632  continue;
633  }
634  if ( b < mamb ) b = mamb;
635  continue;
636  }
637  /* if ( mamb <= minThreshold ) */
638  _SwapPoints( theList, i, l );
639  i--; l--;
640  }
641 
642  }
643  *last = l;
644  *bound = b;
645  return( index );
646  }
647 
648  if ( dim == 3 ) {
649 
650  if ( squareDiameter <= theSeg->squareDiameter ) {
651 
652  for ( i=first; i<=l; i++ ) {
653  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
654  theList[i], theSeg->extremity2 );
655  if ( mamb > maxThreshold ) {
656  index ++;
657  _SwapPoints( theList, index, i );
658  continue;
659  }
660  if ( mamb > minThreshold ) {
661  am2 = _SquareDistance3D( theList[i], theSeg->extremity1 );
662  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) ) - mamb*mamb < 0 ) {
663  _SwapPoints( theList, i, l );
664  i--; l--;
665  continue;
666  }
667  if ( b < mamb ) b = mamb;
668  continue;
669  }
670  /* if ( mamb <= minThreshold ) */
671  _SwapPoints( theList, i, l );
672  i--; l--;
673  }
674 
675  } else {
676 
677  for ( i=first; i<=l; i++ ) {
678  mamb = _ScalarProduct3D( theList[i], theSeg->extremity1,
679  theList[i], theSeg->extremity2 );
680  if ( mamb > maxThreshold ) {
681  index ++;
682  _SwapPoints( theList, index, i );
683  continue;
684  }
685  if ( mamb > medThreshold ) {
686  if ( b < mamb ) b = mamb;
687  continue;
688  }
689  if ( mamb > minThreshold ) {
690  am2 = _SquareDistance3D( theList[i], theSeg->extremity1 );
691  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
692  - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
693  _SwapPoints( theList, i, l );
694  i--; l--;
695  continue;
696  }
697  if ( b < mamb ) b = mamb;
698  continue;
699  }
700  /* if ( mamb <= minThreshold ) */
701  _SwapPoints( theList, i, l );
702  i--; l--;
703  }
704 
705  }
706  *last = l;
707  *bound = b;
708  return( index );
709  }
710 
711  if ( squareDiameter <= theSeg->squareDiameter ) {
712 
713  for ( i=first; i<=l; i++ ) {
714  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
715  theList[i], theSeg->extremity2, dim );
716  if ( mamb > maxThreshold ) {
717  index ++;
718  _SwapPoints( theList, index, i );
719  continue;
720  }
721  if ( mamb > minThreshold ) {
722  am2 = _SquareDistance( theList[i], theSeg->extremity1, dim );
723  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) ) - mamb*mamb < 0 ) {
724  _SwapPoints( theList, i, l );
725  i--; l--;
726  continue;
727  }
728  if ( b < mamb ) b = mamb;
729  continue;
730  }
731  /* if ( mamb <= minThreshold ) */
732  _SwapPoints( theList, i, l );
733  i--; l--;
734  }
735 
736  } else {
737 
738  for ( i=first; i<=l; i++ ) {
739  mamb = _ScalarProduct( theList[i], theSeg->extremity1,
740  theList[i], theSeg->extremity2, dim );
741  if ( mamb > maxThreshold ) {
742  index ++;
743  _SwapPoints( theList, index, i );
744  continue;
745  }
746  if ( mamb > medThreshold ) {
747  if ( b < mamb ) b = mamb;
748  continue;
749  }
750  if ( mamb > minThreshold ) {
751  am2 = _SquareDistance( theList[i], theSeg->extremity1, dim );
752  if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
753  - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
754  _SwapPoints( theList, i, l );
755  i--; l--;
756  continue;
757  }
758  if ( b < mamb ) b = mamb;
759  continue;
760  }
761  /* if ( mamb <= minThreshold ) */
762  _SwapPoints( theList, i, l );
763  i--; l--;
764  }
765 
766  }
767  *last = l;
768  *bound = b;
769  return( index );
770 
771  /* END
772  COMPLETE REDUCTION
773  */
774  }
775  return( -1 );
776 }
777 
778 //void _CountPointsInSpheres( TypeSegment *theSeg,
779 // const double squareDiameter,
780 // const double **theList,
781 // const int first,
782 // const int last,
783 // const int dim )
784 //{
785 // double minThreshold;
786 // double medThreshold;
787 // double maxThreshold;
788 //
789 // double ab = sqrt( theSeg->squareDiameter );
790 // double ab2 = theSeg->squareDiameter;
791 //
792 // double R = sqrt( squareDiameter );
793 // double R2 = squareDiameter;
794 //
795 // int n[5] = {0,0,0,0,0};
796 // int i;
797 //
798 // double mamb, am2;
799 //
800 // minThreshold = (R - .86602540378443864676*ab)
801 // * (R - .86602540378443864676*ab)
802 // - 0.25 * ab2;
803 //
804 // medThreshold = 0.5 * ab2 + 0.25 * R2
805 // - .43301270189221932338 * R * sqrt( 4 * ab2 - R2 );
806 //
807 // maxThreshold = 0.25 * (R2 - ab2);
808 //
809 //
810 // for ( i=first; i<=last; i++ ) {
811 //
812 // mamb = _ScalarProduct( theList[i], theSeg->extremity1,
813 // theList[i], theSeg->extremity2, dim );
814 //
815 // if ( mamb > maxThreshold ) {
816 // n[0] ++ ;
817 // continue;
818 // }
819 //
820 // if ( mamb > medThreshold ) {
821 // n[1] ++ ;
822 // continue;
823 // }
824 //
825 // if ( mamb > minThreshold ) {
826 // am2 = _SquareDistance( theList[i], theSeg->extremity1, dim );
827 // if ( 3.0 * ( am2 * ab2 - (am2 - mamb)*(am2 - mamb) )
828 // - (R2 - ab2 - mamb)*(R2 - ab2 - mamb) < 0 ) {
829 // n[2] ++;
830 // continue;
831 // }
832 // n[3] ++;
833 // continue;
834 // }
835 //
836 // n[4] ++;
837 // }
838 //
839 // printf(" diametre courant = %g - double normale = %g\n",
840 // R, ab );
841 // printf(" %8d points dont\n", last-first+1 );
842 // printf(" - %6d : candidats extremites R=%g\n", n[0], sqrt(maxThreshold+0.25*ab2) );
843 // printf(" - %6d : rien a faire R=%g\n", n[1], sqrt(medThreshold+0.25*ab2) );
844 // printf(" - %6d : a tester \n", n[2]+n[3] );
845 // printf(" + %6d : a eliminer\n", n[2] );
846 // printf(" + %6d : a conserver\n", n[3] );
847 // printf(" - %6d : elimines directement R=%g\n", n[4], sqrt(minThreshold+0.25*ab2) );
848 // printf("----------\n" );
849 // printf(" %8d\n", n[0]+n[1]+n[2]+n[3]+n[4] );
850 //
851 //}
852 
853 
854 /* Find the farthest point from a sphere
855 
856  returned value :
857  - its index if there are some points outside the sphere
858  - else #(first index) - 1
859 
860  As the sphere diameter is an approximation of the set diameter,
861  points verifying MA.MB <= (1.5 -sqrt(3)) AB^2
862  can be removed
863 
864 */
865 
866 
867 int _FarthestPointFromSphere( TypeSegment *theSeg,
868  const double **theList,
869  const int first,
870  int *last,
871  const int dim,
872  const int _reduction_mode_ )
873 {
874  int i, l = (*last);
875  int index = first - 1;
876  double diff, maxdiff = 0.0;
877  /* threshold = 1.5 - sqrt(3)
878  */
879  double threshold = -0.23205080756887729352 * theSeg->squareDiameter;
880 
881  if ( l < first ) return( index );
882 
883 
884  switch ( _reduction_mode_ ) {
885 
886  case 0 :
887 
888  /* NO REDUCTION CASE
889  */
890 
891  if ( dim == 2 ) {
892  for ( i=first; i<=l; i++ ) {
893  diff = _ScalarProduct2D( theList[i], theSeg->extremity1,
894  theList[i], theSeg->extremity2 );
895  if ( maxdiff < diff ) {
896  index = i;
897  maxdiff = diff;
898  }
899  }
900  return( index );
901  }
902 
903  if ( dim == 3 ) {
904  for ( i=first; i<=l; i++ ) {
905  diff = _ScalarProduct3D( theList[i], theSeg->extremity1,
906  theList[i], theSeg->extremity2 );
907  if ( maxdiff < diff ) {
908  index = i;
909  maxdiff = diff;
910  }
911  }
912  return( index );
913  }
914 
915  for ( i=first; i<=l; i++ ) {
916  diff = _ScalarProduct( theList[i], theSeg->extremity1,
917  theList[i], theSeg->extremity2, dim );
918  if ( maxdiff < diff ) {
919  index = i;
920  maxdiff = diff;
921  }
922  }
923  return( index );
924 
925  /* END
926  NO REDUCTION CASE
927  */
928  break;
929 
930  default :
931  case 1 :
932 
933  /* REDUCTION INSIDE THE SMALLEST SPHERE
934  */
935 
936  /* AB = diameter extremities
937  MA.MB = (MC+CA).(MC+CB) = MC^2 + CA.CB + MC ( CB+CA )
938  = MC^2 - R^2 + 0
939  */
940  if ( dim == 2 ) {
941  for ( i=first; i<=l; i++ ) {
942  diff = _ScalarProduct2D( theList[i], theSeg->extremity1,
943  theList[i], theSeg->extremity2 );
944  if ( diff > maxdiff ) {
945  index = i;
946  maxdiff = diff;
947  }
948  else if ( diff <= threshold ) {
949  _SwapPoints( theList, i, l );
950  i --; l --;
951  continue;
952  }
953  }
954  *last = l;
955  return( index );
956  }
957 
958 
959  if ( dim == 3 ) {
960  for ( i=first; i<=l; i++ ) {
961  diff = _ScalarProduct3D( theList[i], theSeg->extremity1,
962  theList[i], theSeg->extremity2 );
963  if ( maxdiff < diff ) {
964  index = i;
965  maxdiff = diff;
966  }
967  else if ( diff <= threshold ) {
968  _SwapPoints( theList, i, l );
969  i --; l --;
970  continue;
971  }
972  }
973  *last = l;
974  return( index );
975  }
976 
977 
978  for ( i=first; i<=l; i++ ) {
979  diff = _ScalarProduct( theList[i], theSeg->extremity1,
980  theList[i], theSeg->extremity2, dim );
981  if ( maxdiff < diff ) {
982  index = i;
983  maxdiff = diff;
984  }
985  else if ( diff <= threshold ) {
986  _SwapPoints( theList, i, l );
987  i --; l --;
988  continue;
989  }
990  }
991  *last = l;
992  return( index );
993  /* END
994  REDUCTION INSIDE THE SMALLEST SPHERE
995  */
996  }
997 
998  return( -1 );
999 }
1000 
1001 double _MaximalSegmentInTwoLists( TypeSegment *theSeg,
1002  const int index1,
1003  const double **theList1,
1004  int *first1,
1005  int *last1,
1006  const double **theList2,
1007  int *first2,
1008  int *last2,
1009  int dim )
1010 {
1011 
1012  int f1=*first1;
1013  int l1=*last1;
1014 
1015  int i1 = index1;
1016 
1017  int f2=*first2;
1018  int l2=*last2;
1019 
1020  int i2;
1021 
1022  const double *ref;
1023 
1024  double d, dprevious;
1025 
1026 
1027  theSeg->extremity1 = (double*)NULL;
1028  theSeg->extremity2 = (double*)NULL;
1029  theSeg->squareDiameter = std::numeric_limits<double>::lowest();
1030 
1031 
1032  if ( *first1 < 0 || *last1 < 0 ) return( -1.0 );
1033  if ( *first1 > *last1 ) return( 0.0 );
1034  if ( *first2 < 0 || *last2 < 0 ) return( -1.0 );
1035  if ( *first2 > *last2 ) return( 0.0 );
1036  if ( *first2 > *last2 ) {
1037  l2 = *first2;
1038  f2 = *last2;
1039  }
1040  if ( index1 < f1 || index1 > l1 ) return( -1.0 );
1041 
1042 
1043  do {
1044 
1045  dprevious = theSeg->squareDiameter;
1046 
1047  /* reference point in list #1
1048  */
1049  ref = theList1[i1];
1050  /* point #i1 will be compared against all other points
1051  in list #2
1052  reject it at the beginning of the list
1053  do not consider it in the future
1054  */
1055  _SwapPoints( theList1, f1, i1 );
1056  f1 ++;
1057 
1058  /* find the furthest point from 'ref'
1059  */
1060  d = _MaximalDistanceFromPoint( &i2, ref, theList2, f2, l2, dim );
1061 
1062  /* better estimate
1063  */
1064  if ( d > theSeg->squareDiameter ) {
1065 
1066  theSeg->extremity1 = ref;
1067  theSeg->extremity2 = theList2[i2];
1068  theSeg->squareDiameter = d;
1069 
1070  if ( f1 <= l1 ) {
1071 
1072  dprevious = theSeg->squareDiameter;
1073 
1074  /* reference point in list #1
1075  */
1076  ref = theList2[i2];
1077  /* point #i2 will be compared against all other points
1078  in list #1
1079  reject it at the beginning of the list
1080  do not consider it in the future
1081  */
1082  _SwapPoints( theList2, f2, i2 );
1083  f2 ++;
1084 
1085  /* find the furthest point from 'ref'
1086  */
1087  d = _MaximalDistanceFromPoint( &i1, ref, theList1, f1, l1, dim );
1088 
1089  /* better estimate
1090  */
1091  if ( d > theSeg->squareDiameter ) {
1092 
1093  theSeg->extremity1 = theList1[i1];
1094  theSeg->extremity2 = ref;
1095  theSeg->squareDiameter = d;
1096 
1097  }
1098 
1099  }
1100 
1101  }
1102 
1103 
1104  } while( theSeg->squareDiameter > dprevious && f1 <= l1 && f2 <= l2 );
1105 
1106 
1107  *first1 = f1;
1108  *last1 = l1;
1109  *first2 = f2;
1110  *last2 = l2;
1111  return( theSeg->squareDiameter );
1112 
1113 }
1114 
1115 double _MaximalSegmentInOneList( TypeSegment *theSeg,
1116  const int index,
1117  const double **theList,
1118  int *first,
1119  int *last,
1120  const int dim )
1121 {
1122  int f=*first;
1123  int l=*last;
1124 
1125  int i = index;
1126  const double *ref;
1127 
1128  double d, dprevious;
1129 
1130  theSeg->extremity1 = (double*)NULL;
1131  theSeg->extremity2 = (double*)NULL;
1132  theSeg->squareDiameter = std::numeric_limits<double>::lowest();
1133 
1134 
1135 
1136  if ( *first < 0 || *last < 0 ) return( -1.0 );
1137  if ( *first > *last ) return( 0.0 );
1138  if ( index < f || index > l ) return( -1.0 );
1139  if ( f == l ) {
1140  theSeg->extremity1 = theList[i];
1141  theSeg->extremity2 = theList[i];
1142  return( 0.0 );
1143  }
1144 
1145 
1146 
1147  do {
1148 
1149  dprevious = theSeg->squareDiameter;
1150 
1151 
1152  ref = theList[i];
1153  /* point #i will be compared against all other points
1154  reject it at the beginning of the list
1155  do not consider it in the future
1156  */
1157  _SwapPoints( theList, f, i );
1158  f ++;
1159 
1160 
1161  /* find the furthest point from 'ref'
1162  */
1163  d = _MaximalDistanceFromPoint( &i, ref, theList, f, l, dim );
1164  if ( d > theSeg->squareDiameter ) {
1165  theSeg->extremity1 = ref;
1166  theSeg->extremity2 = theList[i];
1167  theSeg->squareDiameter = d;
1168  }
1169 
1170 
1171  } while ( theSeg->squareDiameter > dprevious && f <= l );
1172 
1173  *first = f;
1174  *last = l;
1175  return( theSeg->squareDiameter );
1176 }
1177 
1178 double _MaximalDistanceFromPoint( int *index,
1179  const double *ref,
1180  const double **theList,
1181  const int first,
1182  const int last,
1183  const int dim )
1184 {
1185  int f=first;
1186  int l=last;
1187  int i;
1188  double dmax, d;
1189 
1190  *index = -1;
1191  if ( first < 0 || last < 0 ) return( -1.0 );
1192  if ( first > last ) return( 0.0 );
1193 
1194 
1195 
1196  if ( dim == 2 ) {
1197 
1198  dmax = _SquareDistance2D( theList[f], ref );
1199  *index = f;
1200 
1201  for ( i=f+1; i<=l; i++ ) {
1202  d = _SquareDistance2D( theList[i], ref );
1203  if ( d > dmax ) {
1204  dmax = d;
1205  *index = i;
1206  }
1207  }
1208  return( dmax );
1209 
1210  }
1211 
1212  if ( dim == 3 ) {
1213 
1214  dmax = _SquareDistance3D( theList[f], ref );
1215  *index = f;
1216 
1217  for ( i=f+1; i<=l; i++ ) {
1218  d = _SquareDistance3D( theList[i], ref );
1219  if ( d > dmax ) {
1220  dmax = d;
1221  *index = i;
1222  }
1223  }
1224  return( dmax );
1225 
1226  }
1227 
1228 
1229 
1230 
1231  dmax = _SquareDistance( theList[f], ref, dim );
1232  *index = f;
1233 
1234  for ( i=f+1; i<=l; i++ ) {
1235  d = _SquareDistance( theList[i], ref, dim );
1236  if ( d > dmax ) {
1237  dmax = d;
1238  *index = i;
1239  }
1240  }
1241  return( dmax );
1242 
1243 }
1244 
1245 
1246 /* Swap two points
1247  */
1248 
1249 void _SwapPoints( const double **theList, const int i, const int j )
1250 {
1251  const double *tmp;
1252  tmp = theList[i];
1253  theList[i] = theList[j];
1254  theList[j] = tmp;
1255 }
1256 
1257 static int _base_ = 100000000;
1258 
1259 void _InitCounter( TypeCounter *c )
1260 {
1261  c->c1 = c->c2 = 0;
1262 }
1263 void _AddToCounter( TypeCounter *c, const int i )
1264 {
1265  c->c2 += i;
1266  while ( c->c2 >= _base_ ) {
1267  c->c2 -= _base_;
1268  c->c1 ++;
1269  }
1270  while ( c->c2 < 0 ) {
1271  c->c2 += _base_;
1272  c->c1 --;
1273  }
1274 }
1275 double _GetCounterAverage( TypeCounter *c, const int i )
1276 {
1277  return( (_base_ / (double)i ) * c->c1 + c->c2 / (double)i );
1278 }
1279 
1280 
1281 #ifdef _STATS_
1282 TypeCounter scalarProducts;
1283 
1284 void _InitScalarProductCounter()
1285 {
1286  _InitCounter( &scalarProducts );
1287 }
1288 static void _IncScalarProductCounter()
1289 {
1290  _AddToCounter( &scalarProducts, 1 );
1291 }
1292 double _GetScalarProductAverage( int n )
1293 {
1294  return( _GetCounterAverage( &scalarProducts, n ) );
1295 }
1296 #endif
1297 
1298 
1299 
1300 
1301 /* square distance
1302  */
1303 double _SquareDistance( const double *a, const double *b, const int dim )
1304 {
1305  register int i;
1306  register double d = 0.0;
1307  register double ba;
1308  for ( i=0; i<dim; i++ ) {
1309  ba = b[i] - a[i];
1310  d += ba * ba;
1311  }
1312 
1313 #ifdef _STATS_
1314  _IncScalarProductCounter();
1315 #endif
1316 
1317  return( d );
1318 }
1319 
1320 
1321 
1322 
1323 
1324 double _SquareDistance3D( const double *a, const double *b )
1325 {
1326 
1327 #ifdef _STATS_
1328  _IncScalarProductCounter();
1329 #endif
1330 
1331  return( (b[0]-a[0])*(b[0]-a[0]) +
1332  (b[1]-a[1])*(b[1]-a[1]) +
1333  (b[2]-a[2])*(b[2]-a[2]) );
1334 }
1335 
1336 
1337 double _SquareDistance2D( const double *a, const double *b )
1338 {
1339 
1340 #ifdef _STATS_
1341  _IncScalarProductCounter();
1342 #endif
1343 
1344  return( (b[0]-a[0])*(b[0]-a[0]) +
1345  (b[1]-a[1])*(b[1]-a[1]) );
1346 }
1347 
1348 
1349 
1350 
1351 
1352 /* dot product
1353  */
1354 double _ScalarProduct( const double *a, const double *b,
1355  const double *c, const double *d, const int dim )
1356 {
1357  register int i;
1358  register double scalar = 0.0;
1359  register double ab, cd;
1360  for ( i=0; i<dim; i++ ) {
1361  ab = b[i] - a[i];
1362  cd = d[i] - c[i];
1363  scalar += ab * cd;
1364  }
1365 
1366 #ifdef _STATS_
1367  _IncScalarProductCounter();
1368 #endif
1369 
1370  return( scalar );
1371 }
1372 
1373 
1374 
1375 double _ScalarProduct3D( const double *a, const double *b,
1376  const double *c, const double *d )
1377 {
1378 
1379 #ifdef _STATS_
1380  _IncScalarProductCounter();
1381 #endif
1382 
1383  return( (b[0]-a[0])*(d[0]-c[0]) +
1384  (b[1]-a[1])*(d[1]-c[1]) +
1385  (b[2]-a[2])*(d[2]-c[2]) );
1386 }
1387 
1388 double _ScalarProduct2D( const double *a, const double *b,
1389  const double *c, const double *d )
1390 {
1391 
1392 #ifdef _STATS_
1393  _IncScalarProductCounter();
1394 #endif
1395 
1396  return( (b[0]-a[0])*(d[0]-c[0]) +
1397  (b[1]-a[1])*(d[1]-c[1]) );
1398 }
1399 
1400 int _FindPointInList( const double **theList,
1401  const int first,
1402  const int last,
1403  double x0,
1404  double x1 )
1405 {
1406  int i, j=-1;
1407  double e=1e-5;
1408  for ( i=first; i<=last; i++ ) {
1409  if ( theList[i][0]-e < x0 && theList[i][0]+e > x0 &&
1410  theList[i][1]-e < x1 && theList[i][1]+e > x1 ) {
1411  if ( j == -1 ) {
1412  j = i;
1413  } else {
1414  fprintf( stderr, "found again at #%d\n", i );
1415  }
1416  }
1417  }
1418  return( j );
1419 }
1420 
1421 
1422 
1423 
1424 
1425 
1426 
1427 
1428 
1429 
1430 
1431 
1432 
1433 
1434 
1435 
1436 
1437 
1438 
1439 
1440 
1441 
1442 double _QuadraticDiameterInOneList( TypeSegment *theDiam,
1443  const double **theList,
1444  const int first,
1445  const int last,
1446  const int dim )
1447 {
1448  int i, j;
1449  double d;
1450 
1451  theDiam->extremity1 = (double*)NULL;
1452  theDiam->extremity2 = (double*)NULL;
1453  theDiam->squareDiameter = std::numeric_limits<double>::lowest();
1454 
1455  d = 0.0;
1456 
1457  if ( dim == 2 ) {
1458 
1459  for ( i=first; i<=last-1; i++ )
1460  for ( j=i+1; j<=last; j++ ) {
1461  d = _SquareDistance2D( theList[i], theList[j] );
1462  if ( d > theDiam->squareDiameter ) {
1463  theDiam->squareDiameter = d;
1464  theDiam->extremity1 = theList[i];
1465  theDiam->extremity2 = theList[j];
1466  }
1467  }
1468  return( theDiam->squareDiameter );
1469 
1470  }
1471 
1472 
1473 
1474  if ( dim == 3 ) {
1475 
1476  for ( i=first; i<=last-1; i++ )
1477  for ( j=i+1; j<=last; j++ ) {
1478  d = _SquareDistance3D( theList[i], theList[j] );
1479  if ( d > theDiam->squareDiameter ) {
1480  theDiam->squareDiameter = d;
1481  theDiam->extremity1 = theList[i];
1482  theDiam->extremity2 = theList[j];
1483  }
1484  }
1485  return( theDiam->squareDiameter );
1486 
1487  }
1488 
1489 
1490 
1491  for ( i=first; i<=last-1; i++ )
1492  for ( j=i+1; j<=last; j++ ) {
1493  d = _SquareDistance( theList[i], theList[j], dim );
1494  if ( d > theDiam->squareDiameter ) {
1495  theDiam->squareDiameter = d;
1496  theDiam->extremity1 = theList[i];
1497  theDiam->extremity2 = theList[j];
1498  }
1499  }
1500 
1501  return( theDiam->squareDiameter );
1502 }
1503 
1504 
1505 
1506 
1507 
1508 
1509 
1510 
1511 double _QuadraticDiameterInTwoLists( TypeSegment *theDiam,
1512  int *index1,
1513  int *index2,
1514  const double **theList1,
1515  const int first1,
1516  const int last1,
1517  const double **theList2,
1518  const int first2,
1519  const int last2,
1520  const int dim )
1521 {
1522  int i, j;
1523  double d;
1524 
1525  /*
1526  theDiam->extremity1 = (double*)NULL;
1527  theDiam->extremity2 = (double*)NULL;
1528  theDiam->squareDiameter = std::numeric_limits<double>::lowest();
1529  */
1530 
1531  if ( index1 != NULL && index2 != NULL ) {
1532  *index1 = first1-1;
1533  *index2 = first2-1;
1534  }
1535 
1536  d = 0.0;
1537 
1538  if ( dim == 2 ) {
1539 
1540  for ( i=first1; i<=last1; i++ )
1541  for ( j=first2; j<=last2; j++ ) {
1542  d = _SquareDistance2D( theList1[i], theList2[j] );
1543  if ( d > theDiam->squareDiameter ) {
1544  theDiam->squareDiameter = d;
1545  theDiam->extremity1 = theList1[i];
1546  theDiam->extremity2 = theList2[j];
1547  if ( index1 != NULL && index2 != NULL ) {
1548  *index1 = i;
1549  *index2 = j;
1550  }
1551  }
1552  }
1553  return( theDiam->squareDiameter );
1554 
1555  }
1556 
1557 
1558 
1559  if ( dim == 3 ) {
1560 
1561  for ( i=first1; i<=last1; i++ )
1562  for ( j=first2; j<=last2; j++ ) {
1563  d = _SquareDistance3D( theList1[i], theList2[j] );
1564  if ( d > theDiam->squareDiameter ) {
1565  theDiam->squareDiameter = d;
1566  theDiam->extremity1 = theList1[i];
1567  theDiam->extremity2 = theList2[j];
1568  if ( index1 != NULL && index2 != NULL ) {
1569  *index1 = i;
1570  *index2 = j;
1571  }
1572  }
1573  }
1574  return( theDiam->squareDiameter );
1575 
1576  }
1577 
1578 
1579 
1580  for ( i=first1; i<=last1; i++ )
1581  for ( j=first2; j<=last2; j++ ) {
1582  d = _SquareDistance( theList1[i], theList2[j], dim );
1583  if ( d > theDiam->squareDiameter ) {
1584  theDiam->squareDiameter = d;
1585  theDiam->extremity1 = theList1[i];
1586  theDiam->extremity2 = theList2[j];
1587  if ( index1 != NULL && index2 != NULL ) {
1588  *index1 = i;
1589  *index2 = j;
1590  }
1591  }
1592  }
1593 
1594  return( theDiam->squareDiameter );
1595 }
1596 
1597 }
1598 }
ApproxMVBB::Diameter::_FarthestPointFromSphere
APPROXMVBB_EXPORT int _FarthestPointFromSphere(TypeSegment *theSeg, double const **theList, const int first, int *last, const int dim, const int _reduction_mode_)
Definition: util.cpp:867
ApproxMVBB
These are some container definitions.
Definition: EstimateDiameter.hpp:17
ApproxMVBB::Diameter::_MaximalSegmentInOneList
APPROXMVBB_EXPORT double _MaximalSegmentInOneList(TypeSegment *theSeg, const int index, double const **theList, int *first, int *last, const int dim)
Definition: util.cpp:1115
ApproxMVBB::Diameter::_SquareDistance3D
APPROXMVBB_EXPORT double _SquareDistance3D(double const *a, double const *b)
Definition: util.cpp:1324
ApproxMVBB::Diameter::_SwapPoints
APPROXMVBB_EXPORT void _SwapPoints(double const **theList, const int i, const int j)
Definition: util.cpp:1249
ApproxMVBB::Diameter::_FindPointInList
APPROXMVBB_EXPORT int _FindPointInList(double const **theList, const int first, const int last, double x0, double x1)
Definition: util.cpp:1400
ApproxMVBB::Diameter::_QuadraticDiameterInTwoLists
APPROXMVBB_EXPORT double _QuadraticDiameterInTwoLists(TypeSegment *theDiam, int *index1, int *index2, double const **theList1, const int first1, const int last1, double const **theList2, const int first2, const int last2, const int dim)
Definition: util.cpp:1511
ApproxMVBB::Diameter::_QuadraticDiameterInOneList
APPROXMVBB_EXPORT double _QuadraticDiameterInOneList(TypeSegment *theDiam, double const **theList, const int first, const int last, const int dim)
Definition: util.cpp:1442
ApproxMVBB::Diameter::_MaximalSegmentInTwoLists
APPROXMVBB_EXPORT double _MaximalSegmentInTwoLists(TypeSegment *theSeg, const int index1, double const **theList1, int *first1, int *last1, double const **theList2, int *first2, int *last2, int dim)
Definition: util.cpp:1001
ApproxMVBB::Diameter::_LastPointOutsideSphereWithDiameter
APPROXMVBB_EXPORT int _LastPointOutsideSphereWithDiameter(TypeSegment *theSeg, double constsquareDiameter, double const **theList, const int first, int *last, const int dim, const int _reduction_mode_)
Definition: util.cpp:44
ApproxMVBB::Diameter::_ScalarProduct
APPROXMVBB_EXPORT double _ScalarProduct(double const *a, double const *b, double const *c, double const *d, const int dim)
Definition: util.cpp:1354
ApproxMVBB::Diameter::_GetCounterAverage
APPROXMVBB_EXPORT double _GetCounterAverage(TypeCounter *c, const int i)
Definition: util.cpp:1275
ApproxMVBB::Diameter::_InitCounter
APPROXMVBB_EXPORT void _InitCounter(TypeCounter *c)
Definition: util.cpp:1259
ApproxMVBB::Diameter::_SquareDistance2D
APPROXMVBB_EXPORT double _SquareDistance2D(double const *a, double const *b)
Definition: util.cpp:1337
ApproxMVBB::Diameter::_ScalarProduct2D
APPROXMVBB_EXPORT double _ScalarProduct2D(double const *a, double const *b, double const *c, double const *d)
Definition: util.cpp:1388
ApproxMVBB::Diameter::_MaximalDistanceFromPoint
APPROXMVBB_EXPORT double _MaximalDistanceFromPoint(int *index, double const *ref, double const **theList, const int first, const int last, const int dim)
Definition: util.cpp:1178
ApproxMVBB::Diameter::_AddToCounter
APPROXMVBB_EXPORT void _AddToCounter(TypeCounter *c, const int i)
Definition: util.cpp:1263
ApproxMVBB::Diameter::_LastPointOutsideSphereAndBoundWithDiameter
APPROXMVBB_EXPORT int _LastPointOutsideSphereAndBoundWithDiameter(TypeSegment *theSeg, double constsquareDiameter, double const **theList, const int first, int *last, const int dim, const int _reduction_mode_, double *bound)
Definition: util.cpp:386
ApproxMVBB::Diameter::_SquareDistance
APPROXMVBB_EXPORT double _SquareDistance(double const *a, double const *b, const int dim)
Definition: util.cpp:1303
ApproxMVBB::Diameter::_ScalarProduct3D
APPROXMVBB_EXPORT double _ScalarProduct3D(double const *a, double const *b, double const *c, double const *d)
Definition: util.cpp:1375
ApproxMVBB::Diameter::_base_
static int _base_
Definition: util.cpp:1257

asr_approx_mvbb
Author(s): Gassner Nikolai
autogenerated on Mon Jun 10 2019 12:38:08