20f04523146280191eeaa14ff52b84dcf6a7e5e8
1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * --------------------------------------------------------------------
8 * Much of the code in this module is based on code published with
9 * and/or described in "Computational Geometry in C" (Second Edition),
10 * Copyright (C) 1998 Joseph O'Rourke <orourke@cs.smith.edu>
11 * --------------------------------------------------------------------
12 *
13 * This library is free software; you can redistribute it and/or
14 * modify it under the terms of the GNU Lesser General Public
15 * License as published by the Free Software Foundation; either
16 * version 2.1 of the License, or (at your option) any later version.
17 *
18 * This library is distributed in the hope that it will be useful,
19 * but WITHOUT ANY WARRANTY; without even the implied warranty of
20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
21 * Lesser General Public License for more details.
22 *
23 * You should have received a copy of the GNU Lesser General Public
24 * License along with this library; if not, write to the Free Software
25 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
26 *
27 */
29 #include "libavoid/graph.h"
30 #include "libavoid/geometry.h"
31 #include "libavoid/polyutil.h"
33 #include <math.h>
35 namespace Avoid {
38 // Returns true iff the point c lies on the closed segment ab.
39 //
40 // Based on the code of 'Between'.
41 //
42 static const bool inBetween(const Point& a, const Point& b, const Point& c)
43 {
44 // We only call this when we know the points are collinear,
45 // otherwise we should be checking this here.
46 assert(vecDir(a, b, c) == 0);
48 if (a.x != b.x)
49 {
50 // not vertical
51 return (((a.x < c.x) && (c.x < b.x)) ||
52 ((b.x < c.x) && (c.x < a.x)));
53 }
54 else
55 {
56 return (((a.y < c.y) && (c.y < b.y)) ||
57 ((b.y < c.y) && (c.y < a.y)));
58 }
59 }
62 // Returns true if the segment cd intersects the segment ab, blocking
63 // visibility.
64 //
65 // Based on the code of 'IntersectProp' and 'Intersect'.
66 //
67 bool segmentIntersect(const Point& a, const Point& b, const Point& c,
68 const Point& d)
69 {
70 int ab_c = vecDir(a, b, c);
71 if ((ab_c == 0) && inBetween(a, b, c))
72 {
73 return true;
74 }
76 int ab_d = vecDir(a, b, d);
77 if ((ab_d == 0) && inBetween(a, b, d))
78 {
79 return true;
80 }
82 // It's ok for either of the points a or b to be on the line cd,
83 // so we don't have to check the other two cases.
85 int cd_a = vecDir(c, d, a);
86 int cd_b = vecDir(c, d, b);
88 // Is an intersection if a and b are on opposite sides of cd,
89 // and c and d are on opposite sides of the line ab.
90 //
91 // Note: this is safe even though the textbook warns about it
92 // since, unlike them, out vecDir is equivilent to 'AreaSign'
93 // rather than 'Area2'.
94 return (((ab_c * ab_d) < 0) && ((cd_a * cd_b) < 0));
95 }
98 // Returns true iff the point p in a valid region that can contain
99 // shortest paths. a0, a1, a2 are ordered vertices of a shape.
100 // This function may seem 'backwards' to the user due to some of
101 // the code being reversed due to screen cooridinated being the
102 // opposite of graph paper coords.
103 // TODO: Rewrite this after checking whether it works for Inkscape.
104 //
105 // Based on the code of 'InCone'.
106 //
107 bool inValidRegion(bool IgnoreRegions, const Point& a0, const Point& a1,
108 const Point& a2, const Point& b)
109 {
110 int rSide = vecDir(b, a0, a1);
111 int sSide = vecDir(b, a1, a2);
113 bool rOutOn = (rSide >= 0);
114 bool sOutOn = (sSide >= 0);
116 bool rOut = (rSide > 0);
117 bool sOut = (sSide > 0);
119 if (vecDir(a0, a1, a2) > 0)
120 {
121 // Concave at a1:
122 //
123 // !rO rO
124 // !sO !sO
125 //
126 // +---s---
127 // |
128 // !rO r rO
129 // sO | sO
130 //
131 //
132 return (IgnoreRegions ? false : (rOutOn && sOutOn));
133 }
134 else
135 {
136 // Convex at a1:
137 //
138 // !rO rO
139 // sO sO
140 //
141 // ---s---+
142 // |
143 // !rO r rO
144 // !sO | !sO
145 //
146 //
147 if (IgnoreRegions)
148 {
149 return (rOutOn && !sOut) || (!rOut && sOutOn);
150 }
151 return (rOutOn || sOutOn);
152 }
153 }
156 // Returns the distance between points a and b.
157 //
158 double dist(const Point& a, const Point& b)
159 {
160 double xdiff = a.x - b.x;
161 double ydiff = a.y - b.y;
163 return sqrt((xdiff * xdiff) + (ydiff * ydiff));
164 }
167 // Returns true iff the point q is inside (or on the edge of) the
168 // polygon argpoly.
169 //
170 // Based on the code of 'InPoly'.
171 //
172 bool inPoly(const Polygn& argpoly, const Point& q)
173 {
174 // Numbers of right and left edge/ray crossings.
175 int Rcross = 0;
176 int Lcross = 0;
178 // Copy the argument polygon
179 Polygn poly = copyPoly(argpoly);
180 Point *P = poly.ps;
181 int n = poly.pn;
183 // Shift so that q is the origin. This is done for pedogical clarity.
184 for (int i = 0; i < n; ++i)
185 {
186 P[i].x = P[i].x - q.x;
187 P[i].y = P[i].y - q.y;
188 }
190 // For each edge e=(i-1,i), see if crosses ray.
191 for (int i = 0; i < n; ++i)
192 {
193 // First see if q=(0,0) is a vertex.
194 if ((P[i].x == 0) && (P[i].y == 0))
195 {
196 // We count a vertex as inside.
197 freePoly(poly);
198 return true;
199 }
201 // point index; i1 = i-1 mod n
202 int i1 = ( i + n - 1 ) % n;
204 // if e "straddles" the x-axis...
205 // The commented-out statement is logically equivalent to the one
206 // following.
207 // if( ((P[i].y > 0) && (P[i1].y <= 0)) ||
208 // ((P[i1].y > 0) && (P[i].y <= 0)) )
210 if ((P[i].y > 0) != (P[i1].y > 0))
211 {
212 // e straddles ray, so compute intersection with ray.
213 double x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
214 / (P[i1].y - P[i].y);
216 // crosses ray if strictly positive intersection.
217 if (x > 0)
218 {
219 Rcross++;
220 }
221 }
223 // if e straddles the x-axis when reversed...
224 // if( ((P[i].y < 0) && (P[i1].y >= 0)) ||
225 // ((P[i1].y < 0) && (P[i].y >= 0)) )
227 if ((P[i].y < 0) != (P[i1].y < 0))
228 {
229 // e straddles ray, so compute intersection with ray.
230 double x = (P[i].x * P[i1].y - P[i1].x * P[i].y)
231 / (P[i1].y - P[i].y);
233 // crosses ray if strictly positive intersection.
234 if (x < 0)
235 {
236 Lcross++;
237 }
238 }
239 }
240 freePoly(poly);
242 // q on the edge if left and right cross are not the same parity.
243 if ( (Rcross % 2) != (Lcross % 2) )
244 {
245 // We count the edge as inside.
246 return true;
247 }
249 // Inside iff an odd number of crossings.
250 if ((Rcross % 2) == 1)
251 {
252 return true;
253 }
255 // Outside.
256 return false;
257 }
260 }