DGtal  0.9.3
Functions
testDSLSubsegment.cpp File Reference
#include <iostream>
#include "DGtal/base/Common.h"
#include <map>
#include "DGtal/geometry/curves/DSLSubsegment.h"
#include "DGtal/arithmetic/StandardDSLQ0.h"
#include "DGtal/kernel/CPointPredicate.h"
#include "DGtal/arithmetic/IntegerComputer.h"
#include "DGtal/arithmetic/SternBrocot.h"
#include "DGtal/arithmetic/LighterSternBrocot.h"
#include "DGtal/arithmetic/LightSternBrocot.h"
#include "DGtal/arithmetic/Pattern.h"
#include "DGtal/geometry/curves/ArithDSSIterator.h"
#include "DGtal/geometry/curves/ArithmeticalDSSComputer.h"
#include "DGtal/base/Clock.h"
Include dependency graph for testDSLSubsegment.cpp:

Go to the source code of this file.

Functions

template<typename Integer , typename Fraction >
bool testDSLSubsegment (Integer modb)
 
int main ()
 

Detailed Description

This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Author
Isabelle Sivignon (isabe.nosp@m.lle..nosp@m.sivig.nosp@m.non@.nosp@m.gipsa.nosp@m.-lab.nosp@m..gren.nosp@m.oble.nosp@m.-inp..nosp@m.fr ) gipsa-lab Grenoble Images Parole Signal Automatique (CNRS, UMR 5216), CNRS, France
Date
2013/09/16

Functions for testing class DSLSubsegment.

Definition in file testDSLSubsegment.cpp.

Function Documentation

◆ main()

int main ( )

Definition at line 209 of file testDSLSubsegment.cpp.

References DGtal::Trace::beginBlock(), DGtal::Trace::emphase(), DGtal::Trace::endBlock(), DGtal::Trace::info(), srand(), and DGtal::trace.

210 {
211  typedef DGtal::int64_t Integer;
213  typedef LSB::Fraction Fraction;
214 
215  trace.beginBlock ( "Testing class DSLSubsegment" );
216  trace.info() << std::endl;
217 
218  Integer i = 1000;
219  srand(time(NULL));
220 
221  bool res = testDSLSubsegment<Integer,Fraction>(i);
222 
223  trace.emphase() << ( res ? "Passed." : "Error." ) << endl;
224  trace.endBlock();
225 
226  return res ? 0 : 1;
227 
228 }
void beginBlock(const std::string &keyword="")
DGtal::int32_t Integer
Definition: StdDefs.h:74
Trace trace
Definition: Common.h:137
srand(0)
double endBlock()
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
std::ostream & emphase()
std::ostream & info()
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74

◆ testDSLSubsegment()

template<typename Integer , typename Fraction >
bool testDSLSubsegment ( Integer  modb)

Definition at line 58 of file testDSLSubsegment.cpp.

References DGtal::Trace::beginBlock(), DGtal::Trace::endBlock(), DGtal::IntegerComputer< TInteger >::floorDiv(), DGtal::IntegerComputer< TInteger >::gcd(), DGtal::Trace::info(), and DGtal::trace.

59 {
60  //typedef long double Number;
61  typedef DGtal::DSLSubsegment<Integer,Integer> DSLSubseg;
62  //typedef DGtal::DSLSubsegment<Integer,Number> DSLSubsegD;
63 
64 
65  typedef ArithDSSIterator<Integer,8> DSSIterator;
66  typedef NaiveDSS8<Integer> ArithDSS;
67 
68  typedef typename DSLSubseg::Point Point;
69 
70  typedef StandardDSLQ0<Fraction> DSL;
71  typedef typename DSL::Point PointDSL;
72 
74 
75 
76  // Draw random value for b in [0,modb]
77  Integer b( rand() % modb +1);
78 
79  // Draw random value for a in [0,b]
80  Integer a( rand() % b +1);
81  // Draw a new a while a and b are not coprime (do not divide by
82  // the gcd so that b remains in the required interval)
83  while(ic.gcd(a,b) !=1)
84  a = rand() %b +1;
85 
86  // Draw random value for mu in [0,2modb]
87  Integer mu = rand() % (2*modb);
88 
89  Integer l = 200; // max length of the DSSs
90 
91  // Draw random values for the subsegment first extremity abscissa
92  Integer xf = rand() % modb;
93 
94  trace.beginBlock("Draw random values for a,b,mu and abscissa of the first point");
95  trace.info() << "a b mu xf:" << a << " " << b << " " << mu << " " << xf << std::endl;
96  trace.endBlock();
97  trace.info() << std::endl;
98 
99  int error1 = 0;
100  // Consider the subsegment S of the line (a,b,mu), with xf <= x < xf+l
101  // Test all the subsegments of S
102 
103  trace.beginBlock("Compare DSLSubsegment/Farey fan with ArithmeticalDSS algorithm");
104  for(unsigned int i = 0; i<l; i++)
105  for(unsigned int j = i+1; j<l; j++)
106  {
107  Integer x1 = xf+i;
108  Integer x2 = xf+j;
109 
110  Integer y1 = ic.floorDiv(a*x1+mu,b);
111  Integer y2 = ic.floorDiv(a*x2+mu,b);
112  Point A = Point(x1,y1);
113  Point B = Point(x2,y2);
114 
115  // DSLSubsegment with Farey Fan (O(log(n))
116  DSLSubseg DSLsub(a,b,mu,A,B,"farey");
117 
118 
119  // ArithmeticalDSS recognition algorithm (O(n))
120  DSSIterator it(a,b,-mu,A);
121  ArithDSS myDSS(*it, *it);
122  ++it;
123  while ( (*it)[0] <=x2 && myDSS.extendFront(*it))
124  { ++it; }
125 
126  // If results are different, count an error
127  if(DSLsub.getA() != myDSS.a() || DSLsub.getB() != myDSS.b() || DSLsub.getMu() != - myDSS.mu())
128  error1 ++;
129  }
130  trace.info() << error1 << " errors." << std::endl;
131  trace.endBlock();
132  trace.info() << std::endl;
133 
134  int error2 = 0;
135  trace.beginBlock("Compare DSLSubsegment/localCH with DSLSubsegment/FareyFan");
136  for(unsigned int i = 0; i<l; i++)
137  for(unsigned int j = i+1; j<l; j++)
138  {
139  Integer x1 = xf+i;
140  Integer x2 = xf+j;
141 
142  Integer y1 = ic.floorDiv(a*x1+mu,b);
143  Integer y2 = ic.floorDiv(a*x2+mu,b);
144  Point A = Point(x1,y1);
145  Point B = Point(x2,y2);
146 
147  // DSLSubsegment with local CH (O(log(n))
148  DSLSubseg DSLsubCH(a,b,mu,A,B,"localCH");
149 
150  // DSLSubsegment with Farey Fan (O(log(n))
151  DSLSubseg DSLsubF(a,b,mu,A,B,"farey");
152 
153 
154  // If results are different, count an error
155  if(DSLsubCH.getA() != DSLsubF.getA() || DSLsubCH.getB() != DSLsubF.getB() || DSLsubCH.getMu() != DSLsubF.getMu())
156  error2 ++;
157 
158  }
159  trace.info() << error2 << " errors." << std::endl;
160  trace.endBlock();
161  trace.info() << std::endl;
162 
163  int error3 = 0;
164  trace.beginBlock("Compare DSLSubsegment/FareyFan with ReversedSmartDSS for 4-connected DSL");
165  for(unsigned int i = 0; i<l; i++)
166  for(unsigned int j = i+1; j<l; j++)
167  {
168  Integer x1 = xf+i;
169  Integer x2 = xf+j;
170 
171  DSL D( a, b, mu );
172  PointDSL AA = D.lowestY( x1 );
173  PointDSL BB = D.lowestY( x2 );
174 
175  // ReversedSmartDSS algorithm
176  DSL S = D.reversedSmartDSS(AA,BB);
177 
178  // DSLSubsegment algorithm for 4-connected DSL.
179  // Application of an horizontal shear transform
180  Point A2 = AA;
181  A2[0] += A2[1];
182  Point B2 = BB;
183  B2[0] += B2[1];
184 
185  // DSLSubsegment algorithm works with the definition 0 <= ab -by + mu <
186  // b whereas reversedSmartDSS uses mu <= ab-by < mu + b
187  // => -mu is introduced in order to compare the results
188 
189  DSLSubseg D2(a,a+b,-mu,A2,B2,"farey");
190  // The result is (aa,getB()-aa, nu)
191  // Compare results of DSLsubseg4 and reversedSmartDSS
192  if(!(D2.getA()==S.a() && (D2.getB()-D2.getA())==S.b() && D2.getMu()==-S.mu()))
193  error3 ++;
194 
195  }
196  trace.info() << error3 << " errors." << std::endl;
197  trace.endBlock();
198  trace.info() << std::endl;
199 
200  return (error1==0 && error2==0 && error3==0);
201 
202 }
void beginBlock(const std::string &keyword="")
DGtal::int32_t Integer
Definition: StdDefs.h:74
Aim: Represents a digital straight line with slope in the first quadrant (Q0: x >= 0...
Definition: StandardDSLQ0.h:79
Trace trace
Definition: Common.h:137
double endBlock()
Aim: Given a Digital Straight line and two endpoints A and B on this line, compute the minimal charac...
Definition: DSLSubsegment.h:75
Integer floorDiv(IntegerParamType na, IntegerParamType nb) const
MyPointD Point
Definition: testClone2.cpp:383
std::ostream & info()
Aim: This class represents a standard digital straight segment (DSS), ie. the sequence of simply 8-co...
Integer gcd(IntegerParamType a, IntegerParamType b) const
Aim: An iterator on the points of a Digital Straight Segment. Template parameters are the integer typ...