← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/inkscape/oneiric-updates

« back to all changes in this revision

Viewing changes to src/libavoid/geometry.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Alex Valavanis
  • Date: 2010-09-12 19:44:58 UTC
  • mfrom: (1.1.12 upstream) (45.1.3 maverick)
  • Revision ID: james.westby@ubuntu.com-20100912194458-4sjwmbl7dlsrk5dc
Tags: 0.48.0-1ubuntu1
https://launchpad.net/bugs/628048
https://launchpad.net/bugs/401567
https://launchpad.net/bugs/456248
https://launchpad.net/bugs/463602
https://launchpad.net/bugs/591986
https://launchpad.net/bugs/513319
* Merge with Debian unstable (LP: #628048, LP: #401567, LP: #456248, 
  LP: #463602, LP: #591986)
* debian/control: 
  - Ubuntu maintainers
  - Promote python-lxml, python-numpy, python-uniconvertor to Recommends.
  - Demote pstoedit to Suggests (universe package).
  - Suggests ttf-dejavu instead of ttf-bitstream-vera (LP: #513319)
* debian/rules:
  - Run intltool-update on build (Ubuntu-specific).
  - Add translation domain to .desktop files (Ubuntu-specific).
* debian/dirs:
  - Add usr/share/pixmaps.  Allow inkscape.xpm installation
* drop 50-poppler-API.dpatch (now upstream)
* drop 51-paste-in-unwritable-directory.dpatch (now upstream) 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libavoid/geometry.cpp
2
2
 * vim: ts=4 sw=4 et tw=0 wm=0
3
3
 *
4
4
 * libavoid - Fast, Incremental, Object-avoiding Line Router
5
 
 * Copyright (C) 2004-2006  Michael Wybrow <mjwybrow@users.sourceforge.net>
 
5
 *
 
6
 * Copyright (C) 2004-2009  Monash University
6
7
 *
7
8
 * --------------------------------------------------------------------
8
9
 * Much of the code in this module is based on code published with
18
19
 * modify it under the terms of the GNU Lesser General Public
19
20
 * License as published by the Free Software Foundation; either
20
21
 * version 2.1 of the License, or (at your option) any later version.
 
22
 * See the file LICENSE.LGPL distributed with the library.
 
23
 *
 
24
 * Licensees holding a valid commercial license may use this file in
 
25
 * accordance with the commercial license agreement provided with the 
 
26
 * library.
21
27
 *
22
28
 * This library is distributed in the hope that it will be useful,
23
29
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
25
 
 * Lesser General Public License for more details.
26
 
 *
27
 
 * You should have received a copy of the GNU Lesser General Public
28
 
 * License along with this library; if not, write to the Free Software
29
 
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
30
 
 *
 
30
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 
31
 *
 
32
 * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
31
33
*/
32
34
 
 
35
 
 
36
#include <cmath>
 
37
 
33
38
#include "libavoid/graph.h"
34
39
#include "libavoid/geometry.h"
35
 
#include "libavoid/polyutil.h"
36
 
 
37
 
#include <math.h>
 
40
#include "libavoid/assertions.h"
38
41
 
39
42
namespace Avoid {
40
43
 
41
44
 
42
 
Point::Point()
43
 
{
44
 
}
45
 
 
46
 
 
47
 
Point::Point(const double xv, const double yv)
48
 
    : x(xv)
49
 
    , y(yv)
50
 
{
51
 
}
52
 
 
53
 
 
54
 
bool Point::operator==(const Point& rhs) const
55
 
{
56
 
    if ((x == rhs.x) && (y == rhs.y))
57
 
    {
58
 
        return true;
59
 
    }
60
 
    return false;
61
 
}
62
 
 
63
 
 
64
 
bool Point::operator!=(const Point& rhs) const
65
 
{
66
 
    if ((x != rhs.x) || (y != rhs.y))
67
 
    {
68
 
        return true;
69
 
    }
70
 
    return false;
71
 
}
72
 
 
73
45
 
74
46
// Returns true iff the point c lies on the closed segment ab.
 
47
// To be used when the points are known to be collinear.
75
48
//
76
49
// Based on the code of 'Between'.
77
50
//
78
 
static const bool inBetween(const Point& a, const Point& b, const Point& c)
 
51
bool inBetween(const Point& a, const Point& b, const Point& c)
79
52
{
80
53
    // We only call this when we know the points are collinear,
81
54
    // otherwise we should be checking this here.
82
 
    assert(vecDir(a, b, c) == 0);
 
55
    COLA_ASSERT(vecDir(a, b, c, 0.0001) == 0);
83
56
 
84
 
    if (a.x != b.x)
 
57
    if ((fabs(a.x - b.x) > 1) && (a.x != b.x))
85
58
    {
86
59
        // not vertical
87
60
        return (((a.x < c.x) && (c.x < b.x)) ||
95
68
}
96
69
 
97
70
 
 
71
// Returns true iff the point c lies on the closed segment ab.
 
72
//
 
73
bool pointOnLine(const Point& a, const Point& b, const Point& c, 
 
74
        const double tolerance)
 
75
{
 
76
    return (vecDir(a, b, c, tolerance) == 0) && inBetween(a, b, c);
 
77
}
 
78
 
 
79
 
98
80
// Returns true if the segment cd intersects the segment ab, blocking
99
81
// visibility.
100
82
//
104
86
        const Point& d)
105
87
{
106
88
    int ab_c = vecDir(a, b, c);
107
 
    if ((ab_c == 0) && inBetween(a, b, c))
 
89
    if (ab_c == 0)
108
90
    {
109
 
        return true;
 
91
        return false;
110
92
    }
111
93
 
112
94
    int ab_d = vecDir(a, b, d);
113
 
    if ((ab_d == 0) && inBetween(a, b, d))
 
95
    if (ab_d == 0)
114
96
    {
115
 
        return true;
 
97
        return false;
116
98
    }
117
99
 
118
100
    // It's ok for either of the points a or b to be on the line cd,
131
113
}
132
114
 
133
115
 
 
116
// Returns true if the segment e1-e2 intersects the shape boundary 
 
117
// segment s1-s2, blocking visibility.
 
118
//
 
119
bool segmentShapeIntersect(const Point& e1, const Point& e2, const Point& s1,
 
120
        const Point& s2, bool& seenIntersectionAtEndpoint)
 
121
{
 
122
    if (segmentIntersect(e1, e2, s1, s2))
 
123
    {
 
124
        // Basic intersection of segments.
 
125
        return true;
 
126
    }
 
127
    else if ( (((s2 == e1) || pointOnLine(s1, s2, e1)) && 
 
128
               (vecDir(s1, s2, e2) != 0)) 
 
129
              ||
 
130
              (((s2 == e2) || pointOnLine(s1, s2, e2)) &&
 
131
               (vecDir(s1, s2, e1) != 0)) )
 
132
    {
 
133
        // Segments intersect at the endpoint of one of the segments.  We
 
134
        // allow this once, but the second one blocks visibility.  Otherwise
 
135
        // shapes butted up against each other could have visibility through
 
136
        // shapes.
 
137
        if (seenIntersectionAtEndpoint)
 
138
        {
 
139
            return true;
 
140
        }
 
141
        seenIntersectionAtEndpoint = true;
 
142
    }
 
143
    return false;
 
144
}
 
145
 
 
146
 
134
147
// Returns true iff the point p in a valid region that can contain
135
148
// shortest paths.  a0, a1, a2 are ordered vertices of a shape.
136
149
//
205
218
    int s12p = vecDir(c1, c2, p);
206
219
    int s23p = vecDir(c2, c3, p);
207
220
 
208
 
    if (s12p == 0)
209
 
    {
210
 
        // Case of p being somewhere on c1-c2.
211
 
        return s23p;
212
 
    }
213
 
    if (s23p == 0)
214
 
    {
215
 
        // Case of p being somewhere on c2-c3.
216
 
        return s12p;
217
 
    }
218
 
 
219
221
    if (s123 == 1)
220
222
    {
221
 
        if ((s12p == 1) && (s23p == 1))
 
223
        if ((s12p >= 0) && (s23p >= 0))
222
224
        {
223
225
            return 1;
224
226
        }
226
228
    }
227
229
    else if (s123 == -1)
228
230
    {
229
 
        if ((s12p == -1) && (s23p == -1))
 
231
        if ((s12p <= 0) && (s23p <= 0))
230
232
        {
231
233
            return -1;
232
234
        }
233
235
        return 1;
234
236
    }
235
 
    // Case of c3 being somewhere on c1-c2.
 
237
 
 
238
    // c1-c2-c3 are collinear, so just return vecDir from c1-c2
236
239
    return s12p;
237
240
}
238
241
 
239
242
 
240
 
// Returns the distance between points a and b.
 
243
// Returns the Euclidean distance between points a and b.
 
244
//
 
245
double euclideanDist(const Point& a, const Point& b)
 
246
{
 
247
    double xdiff = a.x - b.x;
 
248
    double ydiff = a.y - b.y;
 
249
 
 
250
    return sqrt((xdiff * xdiff) + (ydiff * ydiff));
 
251
}
 
252
 
 
253
// Returns the Manhattan distance between points a and b.
 
254
//
 
255
double manhattanDist(const Point& a, const Point& b)
 
256
{
 
257
    return fabs(a.x - b.x) + fabs(a.y - b.y);
 
258
}
 
259
 
 
260
 
 
261
// Returns the Euclidean distance between points a and b.
241
262
//
242
263
double dist(const Point& a, const Point& b)
243
264
{
248
269
}
249
270
 
250
271
// Returns the total length of all line segments in the polygon
251
 
double totalLength(const Polygn& poly)
 
272
double totalLength(const Polygon& poly)
252
273
{
253
274
    double l = 0;
254
 
    for (int i = 0; i < poly.pn-1; ++i) {
255
 
        l += dist(poly.ps[i], poly.ps[i+1]);
 
275
    for (size_t i = 1; i < poly.size(); ++i) 
 
276
    {
 
277
        l += dist(poly.ps[i-1], poly.ps[i]);
256
278
    }
257
279
    return l;
258
280
}
277
299
// This is a fast version that only works for convex shapes.  The
278
300
// other version (inPolyGen) is more general.
279
301
//
280
 
bool inPoly(const Polygn& poly, const Point& q)
 
302
bool inPoly(const Polygon& poly, const Point& q, bool countBorder)
281
303
{
282
 
    int n = poly.pn;
283
 
    Point *P = poly.ps;
284
 
    for (int i = 0; i < n; i++)
 
304
    size_t n = poly.size();
 
305
    const std::vector<Point>& P = poly.ps;
 
306
    bool onBorder = false;
 
307
    for (size_t i = 0; i < n; i++)
285
308
    {
286
309
        // point index; i1 = i-1 mod n
287
 
        int prev = (i + n - 1) % n;
288
 
        if (vecDir(P[prev], P[i], q) == -1)
 
310
        size_t prev = (i + n - 1) % n;
 
311
        int dir = vecDir(P[prev], P[i], q);
 
312
        if (dir == -1)
289
313
        {
 
314
            // Point is outside
290
315
            return false;
291
316
        }
 
317
        // Record if point was on a boundary.
 
318
        onBorder |= (dir == 0);
 
319
    }
 
320
    if (!countBorder && onBorder)
 
321
    {
 
322
        return false;
292
323
    }
293
324
    return true;
294
325
}
299
330
//
300
331
// Based on the code of 'InPoly'.
301
332
//
302
 
bool inPolyGen(const Polygn& argpoly, const Point& q)
 
333
bool inPolyGen(const PolygonInterface& argpoly, const Point& q)
303
334
{
304
335
    // Numbers of right and left edge/ray crossings.
305
336
    int Rcross = 0;
306
337
    int Lcross = 0;
307
338
 
308
339
    // Copy the argument polygon
309
 
    Polygn poly = copyPoly(argpoly);
310
 
    Point *P = poly.ps;
311
 
    int    n = poly.pn;
 
340
    Polygon poly = argpoly;
 
341
    std::vector<Point>& P = poly.ps;
 
342
    size_t    n = poly.size();
312
343
 
313
344
    // Shift so that q is the origin. This is done for pedogical clarity.
314
 
    for (int i = 0; i < n; ++i)
 
345
    for (size_t i = 0; i < n; ++i)
315
346
    {
316
347
        P[i].x = P[i].x - q.x;
317
348
        P[i].y = P[i].y - q.y;
318
349
    }
319
350
 
320
351
    // For each edge e=(i-1,i), see if crosses ray.
321
 
    for (int i = 0; i < n; ++i)
 
352
    for (size_t i = 0; i < n; ++i)
322
353
    {
323
354
        // First see if q=(0,0) is a vertex.
324
355
        if ((P[i].x == 0) && (P[i].y == 0))
325
356
        {
326
357
            // We count a vertex as inside.
327
 
            freePoly(poly);
328
358
            return true;
329
359
        }
330
360
 
331
361
        // point index; i1 = i-1 mod n
332
 
        int i1 = ( i + n - 1 ) % n;
 
362
        size_t i1 = ( i + n - 1 ) % n;
333
363
 
334
364
        // if e "straddles" the x-axis...
335
365
        // The commented-out statement is logically equivalent to the one
367
397
            }
368
398
        }
369
399
    }
370
 
    freePoly(poly);
371
400
 
372
401
    // q on the edge if left and right cross are not the same parity.
373
402
    if ( (Rcross % 2) != (Lcross % 2) )
400
429
int segmentIntersectPoint(const Point& a1, const Point& a2,
401
430
        const Point& b1, const Point& b2, double *x, double *y) 
402
431
{
403
 
 
404
 
    double Ax,Bx,Cx,Ay,By,Cy,d,e,f,num,offset;
 
432
    double Ax,Bx,Cx,Ay,By,Cy,d,e,f,num;
405
433
    double x1lo,x1hi,y1lo,y1hi;
406
434
 
407
435
    Ax = a2.x - a1.x;
450
478
        if (y1hi < b1.y || b2.y < y1lo) return DONT_INTERSECT;
451
479
    }
452
480
 
453
 
 
454
481
    Cx = a1.x - b1.x;
455
482
    Cy = a1.y - b1.y;
456
483
    // alpha numerator:
457
484
    d = By*Cx - Bx*Cy;
458
485
    // Both denominator:
459
486
    f = Ay*Bx - Ax*By;
460
 
    // aplha tests:
 
487
    // alpha tests:
461
488
    if (f > 0)
462
489
    {
463
490
        if (d < 0 || d > f) return DONT_INTERSECT;
485
512
    
486
513
    // Numerator:
487
514
    num = d*Ax;
488
 
    // Round direction:
489
 
    offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
490
 
    // Intersection X:
491
 
    *x = a1.x + (num+offset) / f;
492
 
 
493
 
    num = d*Ay;
494
 
    offset = SAME_SIGNS(num,f) ? f/2 : -f/2;
495
 
    // Intersection Y:
496
 
    *y = a1.y + (num+offset) / f;
 
515
    // Intersection X:
 
516
    *x = a1.x + (num) / f;
 
517
 
 
518
    num = d*Ay;
 
519
    // Intersection Y:
 
520
    *y = a1.y + (num) / f;
 
521
 
 
522
    return DO_INTERSECT;
 
523
}
 
524
 
 
525
 
 
526
// Line Segment Intersection
 
527
// Original code by Franklin Antonio 
 
528
//
 
529
int rayIntersectPoint(const Point& a1, const Point& a2,
 
530
        const Point& b1, const Point& b2, double *x, double *y) 
 
531
{
 
532
    double Ax,Bx,Cx,Ay,By,Cy,d,f,num;
 
533
 
 
534
    Ay = a2.y - a1.y;
 
535
    By = b1.y - b2.y;
 
536
    Ax = a2.x - a1.x;
 
537
    Bx = b1.x - b2.x;
 
538
 
 
539
    Cx = a1.x - b1.x;
 
540
    Cy = a1.y - b1.y;
 
541
    // alpha numerator:
 
542
    d = By*Cx - Bx*Cy;
 
543
    // Both denominator:
 
544
    f = Ay*Bx - Ax*By;
 
545
 
 
546
    // compute intersection coordinates:
 
547
 
 
548
    if (f == 0) return PARALLEL;
 
549
    
 
550
    // Numerator:
 
551
    num = d*Ax;
 
552
    // Intersection X:
 
553
    *x = a1.x + (num) / f;
 
554
 
 
555
    num = d*Ay;
 
556
    // Intersection Y:
 
557
    *y = a1.y + (num) / f;
497
558
 
498
559
    return DO_INTERSECT;
499
560
}