DGtal  1.2.0
testDSLSubsegment.cpp
Go to the documentation of this file.
1
30 #include <iostream>
31 #include "DGtal/base/Common.h"
33
34 #include <map>
35 #include "DGtal/geometry/curves/DSLSubsegment.h"
36 #include "DGtal/arithmetic/StandardDSLQ0.h"
37 #include "DGtal/kernel/CPointPredicate.h"
38 #include "DGtal/arithmetic/IntegerComputer.h"
39 #include "DGtal/arithmetic/SternBrocot.h"
40 #include "DGtal/arithmetic/LighterSternBrocot.h"
41 #include "DGtal/arithmetic/LightSternBrocot.h"
42 #include "DGtal/arithmetic/Pattern.h"
43 #include "DGtal/geometry/curves/ArithDSSIterator.h"
44 #include "DGtal/geometry/curves/ArithmeticalDSSComputer.h"
45 #include "DGtal/base/Clock.h"
46
47 using namespace std;
48 using namespace DGtal;
49
51 // Functions for testing class DSLSubsegment.
53
54 //#define CHECK_RES
55
56
57 template <typename Integer,typename Fraction>
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 }
203
204
205
207 // Standard services - public :
208
209 int main()
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((unsigned int)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 }
229 // //
Aim: An iterator on the points of a Digital Straight Segment. Template parameters are the integer typ...
Aim: Given a Digital Straight line and two endpoints A and B on this line, compute the minimal charac...
Definition: DSLSubsegment.h:76
Integer gcd(IntegerParamType a, IntegerParamType b) const
Integer floorDiv(IntegerParamType na, IntegerParamType nb) const
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Aim: This class represents a standard digital straight segment (DSS), ie. the sequence of simply 8-co...
Aim: Represents a digital straight line with slope in the first quadrant (Q0: x >= 0,...
Definition: StandardDSLQ0.h:80
void beginBlock(const std::string &keyword="")
std::ostream & emphase()
std::ostream & info()
double endBlock()
Point::Coordinate Integer
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::int64_t int64_t
signed 94-bit integer.
Definition: BasicTypes.h:74
Trace trace
Definition: Common.h:154
MyPointD Point
Definition: testClone2.cpp:383
srand(0)
bool testDSLSubsegment(Integer modb)
int main()