← Back to branch summary

~evarlast/ubuntu/utopic/mongodb/upstart-workaround-debian-bug-718702

« back to all changes in this revision

Viewing changes to src/mongo/db/geo/shapes.h

  • Committer: Package Import Robot
  • Author(s): James Page, James Page, Robie Basak
  • Date: 2013-05-29 17:44:42 UTC
  • mfrom: (44.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20130529174442-z0a4qmoww4y0t458
Tags: 1:2.4.3-1ubuntu1
[ James Page ]
* Merge from Debian unstable, remaining changes:
  - Enable SSL support:
    + d/control: Add libssl-dev to BD's.
    + d/rules: Enabled --ssl option.
    + d/mongodb.conf: Add example SSL configuration options.
  - d/mongodb-server.mongodb.upstart: Add upstart configuration.
  - d/rules: Don't strip binaries during scons build for Ubuntu.
  - d/control: Add armhf to target archs.
  - d/p/SConscript.client.patch: fixup install of client libraries.
  - d/p/0010-install-libs-to-usr-lib-not-usr-lib64-Closes-588557.patch:
    Install libraries to lib not lib64.
* Dropped changes:
  - d/p/arm-support.patch: Included in Debian.
  - d/p/double-alignment.patch: Included in Debian.
  - d/rules,control: Debian also builds with avaliable system libraries
    now.
* Fix FTBFS due to gcc and boost upgrades in saucy:
  - d/p/0008-ignore-unused-local-typedefs.patch: Add -Wno-unused-typedefs
    to unbreak building with g++-4.8.
  - d/p/0009-boost-1.53.patch: Fixup signed/unsigned casting issue.

[ Robie Basak ]
* d/p/0011-Use-a-signed-char-to-store-BSONType-enumerations.patch: Fixup
  build failure on ARM due to missing signed'ness of char cast.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/mongo/db/geo/shapes.h
1
1
/**
2
 
*    Copyright (C) 2012 10gen Inc.
 
2
*    Copyright (C) 2008-2012 10gen Inc.
3
3
*
4
4
*    This program is free software: you can redistribute it and/or  modify
5
5
*    it under the terms of the GNU Affero General Public License, version 3,
16
16
 
17
17
#pragma once
18
18
 
19
 
#ifndef GEODEBUG
20
 
#define GEODEBUG(x)
21
 
#endif
 
19
#include "mongo/pch.h"
 
20
#include "mongo/db/jsobj.h"
22
21
 
23
22
namespace mongo {
24
 
    class Point {
25
 
    public:
26
 
        explicit Point( const BSONElement& e ) {
27
 
            BSONObjIterator i(e.Obj());
28
 
            _x = i.next().number();
29
 
            _y = i.next().number();
30
 
        }
31
 
 
32
 
        explicit Point( const BSONObj& o ) {
33
 
            BSONObjIterator i(o);
34
 
            _x = i.next().number();
35
 
            _y = i.next().number();
36
 
        }
37
 
 
38
 
        Point( double x , double y )
39
 
            : _x( x ) , _y( y ) {
40
 
        }
41
 
 
42
 
        Point() : _x(0),_y(0) {
43
 
        }
44
 
 
45
 
        double distance( const Point& p ) const {
46
 
            double a = _x - p._x;
47
 
            double b = _y - p._y;
48
 
 
49
 
            // Avoid numerical error if possible...
50
 
            if( a == 0 ) return abs( _y - p._y );
51
 
            if( b == 0 ) return abs( _x - p._x );
52
 
 
53
 
            return sqrt( ( a * a ) + ( b * b ) );
54
 
        }
55
 
 
56
 
        /**
57
 
         * Distance method that compares x or y coords when other direction is zero,
58
 
         * avoids numerical error when distances are very close to radius but axis-aligned.
59
 
         *
60
 
         * An example of the problem is:
61
 
         * (52.0 - 51.9999) - 0.0001 = 3.31965e-15 and 52.0 - 51.9999 > 0.0001 in double arithmetic
62
 
         * but:
63
 
         * 51.9999 + 0.0001 <= 52.0
64
 
         *
65
 
         * This avoids some (but not all!) suprising results in $center queries where points are
66
 
         * ( radius + center.x, center.y ) or vice-versa.
67
 
         */
68
 
        bool distanceWithin( const Point& p, double radius ) const {
69
 
            double a = _x - p._x;
70
 
            double b = _y - p._y;
71
 
 
72
 
            if( a == 0 ) {
73
 
                //
74
 
                // Note:  For some, unknown reason, when a 32-bit g++ optimizes this call, the sum is
75
 
                // calculated imprecisely.  We need to force the compiler to always evaluate it correctly,
76
 
                // hence the weirdness.
77
 
                //
78
 
                // On some 32-bit linux machines, removing the volatile keyword or calculating the sum inline
79
 
                // will make certain geo tests fail.  Of course this check will force volatile for all 32-bit systems,
80
 
                // not just affected systems.
81
 
                if( sizeof(void*) <= 4 ){
82
 
                    volatile double sum = _y > p._y ? p._y + radius : _y + radius;
83
 
                    return _y > p._y ? sum >= _y : sum >= p._y;
84
 
                }
85
 
                else {
86
 
                    // Original math, correct for most systems
87
 
                    return _y > p._y ? p._y + radius >= _y : _y + radius >= p._y;
88
 
                }
89
 
            }
90
 
            if( b == 0 ) {
91
 
                if( sizeof(void*) <= 4 ){
92
 
                    volatile double sum = _x > p._x ? p._x + radius : _x + radius;
93
 
                    return _x > p._x ? sum >= _x : sum >= p._x;
94
 
                }
95
 
                else {
96
 
                    return _x > p._x ? p._x + radius >= _x : _x + radius >= p._x;
97
 
                }
98
 
            }
99
 
 
100
 
            return sqrt( ( a * a ) + ( b * b ) ) <= radius;
101
 
        }
102
 
 
103
 
        string toString() const {
104
 
            StringBuilder buf;
105
 
            buf << "(" << _x << "," << _y << ")";
106
 
            return buf.str();
107
 
 
108
 
        }
109
 
 
110
 
        double _x;
111
 
        double _y;
112
 
    };
113
 
 
 
23
    struct Point;
 
24
    double distance(const Point& p1, const Point &p2);
 
25
    bool distanceWithin(const Point &p1, const Point &p2, double radius);
 
26
    void checkEarthBounds(const Point &p);
 
27
    double spheredist_rad(const Point& p1, const Point& p2);
 
28
    double spheredist_deg(const Point& p1, const Point& p2);
 
29
 
 
30
    struct Point {
 
31
        Point();
 
32
        Point(double x, double y);
 
33
        explicit Point(const BSONElement& e);
 
34
        explicit Point(const BSONObj& o);
 
35
        string toString() const;
 
36
 
 
37
        double x;
 
38
        double y;
 
39
    };
 
40
 
 
41
    struct Circle {
 
42
        Circle();
 
43
        Circle(double radius, Point center);
 
44
 
 
45
        double radius;
 
46
        Point center;
 
47
    };
114
48
 
115
49
    class Box {
116
50
    public:
117
 
        Box( double x , double y , double size )
118
 
            : _min( x , y ) ,
119
 
              _max( x + size , y + size ) {
120
 
        }
121
 
 
122
 
        Box( Point min , Point max )
123
 
            : _min( min ) , _max( max ) {
124
 
        }
125
 
 
126
 
        Box() {}
127
 
 
128
 
        BSONArray toBSON() const {
129
 
            return BSON_ARRAY( BSON_ARRAY( _min._x << _min._y ) << BSON_ARRAY( _max._x << _max._y ) );
130
 
        }
131
 
 
132
 
        string toString() const {
133
 
            StringBuilder buf;
134
 
            buf << _min.toString() << " -->> " << _max.toString();
135
 
            return buf.str();
136
 
        }
137
 
 
138
 
        bool between( double min , double max , double val , double fudge=0) const {
139
 
            return val + fudge >= min && val <= max + fudge;
140
 
        }
141
 
 
142
 
        bool onBoundary( double bound, double val, double fudge = 0 ) const {
143
 
            return ( val >= bound - fudge && val <= bound + fudge );
144
 
        }
145
 
 
146
 
        bool mid( double amin , double amax , double bmin , double bmax , bool min , double& res ) const {
147
 
            verify( amin <= amax );
148
 
            verify( bmin <= bmax );
149
 
 
150
 
            if ( amin < bmin ) {
151
 
                if ( amax < bmin )
152
 
                    return false;
153
 
                res = min ? bmin : amax;
154
 
                return true;
155
 
            }
156
 
            if ( amin > bmax )
157
 
                return false;
158
 
            res = min ? amin : bmax;
159
 
            return true;
160
 
        }
161
 
 
162
 
        double intersects( const Box& other ) const {
163
 
 
164
 
            Point boundMin(0,0);
165
 
            Point boundMax(0,0);
166
 
 
167
 
            if ( mid( _min._x , _max._x , other._min._x , other._max._x , true , boundMin._x ) == false ||
168
 
                    mid( _min._x , _max._x , other._min._x , other._max._x , false , boundMax._x ) == false ||
169
 
                    mid( _min._y , _max._y , other._min._y , other._max._y , true , boundMin._y ) == false ||
170
 
                    mid( _min._y , _max._y , other._min._y , other._max._y , false , boundMax._y ) == false )
171
 
                return 0;
172
 
 
173
 
            Box intersection( boundMin , boundMax );
174
 
 
175
 
            return intersection.area() / area();
176
 
        }
177
 
 
178
 
        double area() const {
179
 
            return ( _max._x - _min._x ) * ( _max._y - _min._y );
180
 
        }
181
 
 
182
 
        double maxDim() const {
183
 
            return max( _max._x - _min._x, _max._y - _min._y );
184
 
        }
185
 
        // pointFromHash
186
 
        // pointToHash
187
 
        // boxFromHash
188
 
 
189
 
        Point center() const {
190
 
            return Point( ( _min._x + _max._x ) / 2 ,
191
 
                          ( _min._y + _max._y ) / 2 );
192
 
        }
193
 
 
194
 
        void truncate(double min, double max) {
195
 
            if( _min._x < min ) _min._x = min;
196
 
            if( _min._y < min ) _min._y = min;
197
 
            if( _max._x > max ) _max._x = max;
198
 
            if( _max._y > max ) _max._y = max;
199
 
        }
200
 
 
201
 
        void fudge(double error) {
202
 
            _min._x -= error;
203
 
            _min._y -= error;
204
 
            _max._x += error;
205
 
            _max._y += error;
206
 
        }
207
 
 
208
 
        bool onBoundary( Point p, double fudge = 0 ) {
209
 
            return onBoundary( _min._x, p._x, fudge ) ||
210
 
                   onBoundary( _max._x, p._x, fudge ) ||
211
 
                   onBoundary( _min._y, p._y, fudge ) ||
212
 
                   onBoundary( _max._y, p._y, fudge );
213
 
        }
214
 
 
215
 
        bool inside( Point p , double fudge = 0 ) const {
216
 
            bool res = inside( p._x , p._y , fudge );
217
 
            //cout << "is : " << p.toString() << " in " << toString() << " = " << res << endl;
218
 
            return res;
219
 
        }
220
 
 
221
 
        bool inside( double x , double y , double fudge = 0 ) const {
222
 
            return
223
 
                between( _min._x , _max._x  , x , fudge ) &&
224
 
                between( _min._y , _max._y  , y , fudge );
225
 
        }
226
 
 
227
 
        bool contains(const Box& other, double fudge=0) {
228
 
            return inside(other._min, fudge) && inside(other._max, fudge);
229
 
        }
230
 
 
 
51
        Box();
 
52
        Box(double x, double y, double size);
 
53
        Box(Point min, Point max);
 
54
 
 
55
        BSONArray toBSON() const;
 
56
        string toString() const;
 
57
 
 
58
        bool between(double min, double max, double val, double fudge = 0) const;
 
59
        bool onBoundary(double bound, double val, double fudge = 0) const;
 
60
        bool mid(double amin, double amax, double bmin, double bmax, bool min, double* res) const;
 
61
 
 
62
        double intersects(const Box& other) const;
 
63
        double area() const;
 
64
        double maxDim() const;
 
65
        Point center() const;
 
66
        void truncate(double min, double max);
 
67
        void fudge(double error);
 
68
        bool onBoundary(Point p, double fudge = 0);
 
69
        bool inside(Point p, double fudge = 0) const;
 
70
        bool inside(double x, double y, double fudge = 0) const;
 
71
        bool contains(const Box& other, double fudge = 0);
231
72
        Point _min;
232
73
        Point _max;
233
74
    };
234
75
 
235
 
 
236
76
    class Polygon {
237
77
    public:
238
 
 
239
 
        Polygon( void ) : _centroidCalculated( false ) {}
240
 
 
241
 
        Polygon( vector<Point> points ) : _centroidCalculated( false ),
242
 
            _points( points ) { }
243
 
 
244
 
        void add( Point p ) {
245
 
            _centroidCalculated = false;
246
 
            _points.push_back( p );
247
 
        }
248
 
 
249
 
        int size( void ) const {
250
 
            return _points.size();
251
 
        }
252
 
 
253
 
        /**
254
 
         * Determine if the point supplied is contained by the current polygon.
255
 
         *
256
 
         * The algorithm uses a ray casting method.
 
78
        Polygon();
 
79
        Polygon(vector<Point> points);
 
80
 
 
81
        void add(Point p);
 
82
        int size() const;
 
83
 
 
84
        bool contains(const Point& p) const;
 
85
 
 
86
        /* 
 
87
         * Return values:
 
88
         * -1 if no intersection
 
89
         * 0 if maybe an intersection (using fudge)
 
90
         * 1 if there is an intersection
257
91
         */
258
 
        bool contains( const Point& p ) const {
259
 
            return contains( p, 0 ) > 0;
260
 
        }
261
 
 
262
 
        int contains( const Point &p, double fudge ) const {
263
 
 
264
 
            Box fudgeBox( Point( p._x - fudge, p._y - fudge ), Point( p._x + fudge, p._y + fudge ) );
265
 
 
266
 
            int counter = 0;
267
 
            Point p1 = _points[0];
268
 
            for ( int i = 1; i <= size(); i++ ) {
269
 
                Point p2 = _points[i % size()];
270
 
 
271
 
                GEODEBUG( "Doing intersection check of " << fudgeBox.toString() << " with seg " << p1.toString() << " to " << p2.toString() );
272
 
 
273
 
                // We need to check whether or not this segment intersects our error box
274
 
                if( fudge > 0 &&
275
 
                        // Points not too far below box
276
 
                        fudgeBox._min._y <= std::max( p1._y, p2._y ) &&
277
 
                        // Points not too far above box
278
 
                        fudgeBox._max._y >= std::min( p1._y, p2._y ) &&
279
 
                        // Points not too far to left of box
280
 
                        fudgeBox._min._x <= std::max( p1._x, p2._x ) &&
281
 
                        // Points not too far to right of box
282
 
                        fudgeBox._max._x >= std::min( p1._x, p2._x ) ) {
283
 
 
284
 
                    GEODEBUG( "Doing detailed check" );
285
 
 
286
 
                    // If our box contains one or more of these points, we need to do an exact check.
287
 
                    if( fudgeBox.inside(p1) ) {
288
 
                        GEODEBUG( "Point 1 inside" );
289
 
                        return 0;
290
 
                    }
291
 
                    if( fudgeBox.inside(p2) ) {
292
 
                        GEODEBUG( "Point 2 inside" );
293
 
                        return 0;
294
 
                    }
295
 
 
296
 
                    // Do intersection check for vertical sides
297
 
                    if ( p1._y != p2._y ) {
298
 
 
299
 
                        double invSlope = ( p2._x - p1._x ) / ( p2._y - p1._y );
300
 
 
301
 
                        double xintersT = ( fudgeBox._max._y - p1._y ) * invSlope + p1._x;
302
 
                        if( fudgeBox._min._x <= xintersT && fudgeBox._max._x >= xintersT ) {
303
 
                            GEODEBUG( "Top intersection @ " << xintersT );
304
 
                            return 0;
305
 
                        }
306
 
 
307
 
                        double xintersB = ( fudgeBox._min._y - p1._y ) * invSlope + p1._x;
308
 
                        if( fudgeBox._min._x <= xintersB && fudgeBox._max._x >= xintersB ) {
309
 
                            GEODEBUG( "Bottom intersection @ " << xintersB );
310
 
                            return 0;
311
 
                        }
312
 
 
313
 
                    }
314
 
 
315
 
                    // Do intersection check for horizontal sides
316
 
                    if( p1._x != p2._x ) {
317
 
 
318
 
                        double slope = ( p2._y - p1._y ) / ( p2._x - p1._x );
319
 
 
320
 
                        double yintersR = ( p1._x - fudgeBox._max._x ) * slope + p1._y;
321
 
                        if( fudgeBox._min._y <= yintersR && fudgeBox._max._y >= yintersR ) {
322
 
                            GEODEBUG( "Right intersection @ " << yintersR );
323
 
                            return 0;
324
 
                        }
325
 
 
326
 
                        double yintersL = ( p1._x - fudgeBox._min._x ) * slope + p1._y;
327
 
                        if( fudgeBox._min._y <= yintersL && fudgeBox._max._y >= yintersL ) {
328
 
                            GEODEBUG( "Left intersection @ " << yintersL );
329
 
                            return 0;
330
 
                        }
331
 
 
332
 
                    }
333
 
 
334
 
                }
335
 
                else if( fudge == 0 ){
336
 
 
337
 
                    // If this is an exact vertex, we won't intersect, so check this
338
 
                    if( p._y == p1._y && p._x == p1._x ) return 1;
339
 
                    else if( p._y == p2._y && p._x == p2._x ) return 1;
340
 
 
341
 
                    // If this is a horizontal line we won't intersect, so check this
342
 
                    if( p1._y == p2._y && p._y == p1._y ){
343
 
                        // Check that the x-coord lies in the line
344
 
                        if( p._x >= std::min( p1._x, p2._x ) && p._x <= std::max( p1._x, p2._x ) ) return 1;
345
 
                    }
346
 
 
347
 
                }
348
 
 
349
 
                // Normal intersection test.
350
 
                // TODO: Invert these for clearer logic?
351
 
                if ( p._y > std::min( p1._y, p2._y ) ) {
352
 
                    if ( p._y <= std::max( p1._y, p2._y ) ) {
353
 
                        if ( p._x <= std::max( p1._x, p2._x ) ) {
354
 
                            if ( p1._y != p2._y ) {
355
 
                                double xinters = (p._y-p1._y)*(p2._x-p1._x)/(p2._y-p1._y)+p1._x;
356
 
                                // Special case of point on vertical line
357
 
                                if ( p1._x == p2._x && p._x == p1._x ){
358
 
 
359
 
                                    // Need special case for the vertical edges, for example:
360
 
                                    // 1) \e   pe/----->
361
 
                                    // vs.
362
 
                                    // 2) \ep---e/----->
363
 
                                    //
364
 
                                    // if we count exact as intersection, then 1 is in but 2 is out
365
 
                                    // if we count exact as no-int then 1 is out but 2 is in.
366
 
 
367
 
                                    return 1;
368
 
                                }
369
 
                                else if( p1._x == p2._x || p._x <= xinters ) {
370
 
                                    counter++;
371
 
                                }
372
 
                            }
373
 
                        }
374
 
                    }
375
 
                }
376
 
 
377
 
                p1 = p2;
378
 
            }
379
 
 
380
 
            if ( counter % 2 == 0 ) {
381
 
                return -1;
382
 
            }
383
 
            else {
384
 
                return 1;
385
 
            }
386
 
        }
 
92
        int contains(const Point &p, double fudge) const;
387
93
 
388
94
        /**
389
95
         * Calculate the centroid, or center of mass of the polygon object.
390
96
         */
391
 
        Point centroid( void ) {
392
 
 
393
 
            /* Centroid is cached, it won't change betwen points */
394
 
            if ( _centroidCalculated ) {
395
 
                return _centroid;
396
 
            }
397
 
 
398
 
            Point cent;
399
 
            double signedArea = 0.0;
400
 
            double area = 0.0;  // Partial signed area
401
 
 
402
 
            /// For all vertices except last
403
 
            int i = 0;
404
 
            for ( i = 0; i < size() - 1; ++i ) {
405
 
                area = _points[i]._x * _points[i+1]._y - _points[i+1]._x * _points[i]._y ;
406
 
                signedArea += area;
407
 
                cent._x += ( _points[i]._x + _points[i+1]._x ) * area;
408
 
                cent._y += ( _points[i]._y + _points[i+1]._y ) * area;
409
 
            }
410
 
 
411
 
            // Do last vertex
412
 
            area = _points[i]._x * _points[0]._y - _points[0]._x * _points[i]._y;
413
 
            cent._x += ( _points[i]._x + _points[0]._x ) * area;
414
 
            cent._y += ( _points[i]._y + _points[0]._y ) * area;
415
 
            signedArea += area;
416
 
            signedArea *= 0.5;
417
 
            cent._x /= ( 6 * signedArea );
418
 
            cent._y /= ( 6 * signedArea );
419
 
 
420
 
            _centroidCalculated = true;
421
 
            _centroid = cent;
422
 
 
423
 
            return cent;
424
 
        }
425
 
 
426
 
        Box bounds( void ) {
427
 
 
428
 
            // TODO: Cache this
429
 
 
430
 
            _bounds._max = _points[0];
431
 
            _bounds._min = _points[0];
432
 
 
433
 
            for ( int i = 1; i < size(); i++ ) {
434
 
 
435
 
                _bounds._max._x = max( _bounds._max._x, _points[i]._x );
436
 
                _bounds._max._y = max( _bounds._max._y, _points[i]._y );
437
 
                _bounds._min._x = min( _bounds._min._x, _points[i]._x );
438
 
                _bounds._min._y = min( _bounds._min._y, _points[i]._y );
439
 
 
440
 
            }
441
 
 
442
 
            return _bounds;
443
 
 
444
 
        }
445
 
 
 
97
        Point centroid();
 
98
        Box bounds();
446
99
    private:
447
 
 
448
100
        bool _centroidCalculated;
449
101
        Point _centroid;
450
 
 
451
102
        Box _bounds;
452
 
 
 
103
        bool _boundsCalculated;
453
104
        vector<Point> _points;
454
105
    };
455
106
}  // namespace mongo