Source code: com/port80/graph/dot/impl/BoxToBound.java
1 //
2 // Copyright(c) 2002, Chris Leung
3 //
4
5 package com.port80.graph.dot.impl;
6
7 import com.port80.util.msg;
8
9 /** Construct bounding polygon from path boxes.
10 *
11 * . Since the code make assumption on the constant values, the
12 * constants and routine are packed into this class to decouple
13 * them from others.
14 */
15 public class BoxToBound {
16
17 private static final String NAME = "BoxToBound";
18 private static final boolean DEBUG = false;
19
20 private static final int BOXBOTTOM = 0;
21 private static final int BOXRIGHT = 1;
22 private static final int BOXTOP = 2;
23 private static final int BOXLEFT = 3;
24
25 private static final int UL = 0x00;
26 private static final int LL = 0x01;
27 private static final int LR = 0x02;
28 private static final int UR = 0x03;
29
30 /** Construct bounding polygon from path boxes by transversing in
31 * anti-clockwise direction.
32 *
33 * @enter boxes are sequence of non-overlapped boxes touching the
34 * box before and after it on one and only one side for
35 * length>0.
36 *
37 * @exit The starting vertex of the result polygon may be on either
38 * end of the path.
39 *
40 * Each box is always walked in anticlockwise order, but it may
41 * start at any of the 4 corner depending on where the previous
42 * box touch the current box.
43 *
44 * We look three boxes (the prev, the current and the next) at a
45 * time with an entry condition that specify which side the
46 * current box touch the previous box. For each combination the
47 * walking sequence is:
48 *
49 * (NOTE: All contact side are with respect to the current box
50 * (ie. T mean previous or next box touches the top of the
51 * current box.)
52 *
53 * start/forward count
54 * ------------------------------------------
55 * T(ul)-TL: B(lr1),UL,LL,LR,UR {UL,0}
56 * T(ul)-TR: B(lr1),UL,LL,LR,UR {UL,4}
57 * B(lr)-TX: LR,UR,B(lr1),UL,LL {LR,2}
58 * L(ll)-TX: LL,LR,UR,B(lr1),UL {LL,3}
59 * R(ur)-TX: UR,B(lr1),UL,LL,LR {UR,1}
60 *
61 * T(ul)-BX: UL,LL,T(ul1),LR,UR {UL,2}
62 * B(lr)-BL: LR,UR,UL,LL,T(ul1) {LR,4}
63 * B(lr)-BR: T(ul1),LR,UR,UL,LL {LR,0}
64 * L(ll)-BX: LL,T(ul1),LR,UR,UL {LL,1}
65 * R(ur)-BX: UR,UL,LL,T(ul1),LR {UR,3}
66 *
67 * T(ul)-XL: UL,R(ur1),LL,LR,UR {UL,1}
68 * B(lr)-XL: LR,UR,UL,R(ur1),LL {LR,3}
69 * L(ll)-LL: R(ur1),LL,LR,UR,UL {LL,0} next first
70 * L(ll)-UL: LL,LR,UR,UL,R(ur1) {LL,4} this first
71 * R(ur)-XL: UR,UL,R(ur1),LL,LR {UR,2}
72 *
73 * T(ul)-XR: UL,LL,LR,L(ll1),UR {UL,3}
74 * B(lr)-XR: LR,L(ll1),UR,UL,LL {LR,1}
75 * L(ll)-XR: LL,LR,L(ll1),UR,UL {LL,2}
76 * R(ur)-LR: UR,UL,LL,LR,L(ll1) {UR,4}
77 * R(ur)-UR: L(ll1),UR,UL,LL,LR {UR,0}
78 *
79 * . A reordered table is much more interesting:
80 *
81 * { //T-X
82 * {UL,2}, //T-B
83 * {UL,3}, //T-R
84 * {UL,0}, //T-T
85 * {UL,1}, //T-L
86 * },
87 * { //L-X
88 * {LL,1}, //L-B
89 * {LL,2}, //L-R
90 * {LL,3}, //L-T
91 * {LL,0}, //L-L
92 * },
93 * { //B-X
94 * {LR,0}, //B-B
95 * {LR,1}, //B-R
96 * {LR,2}, //B-T
97 * {LR,3}, //B-L
98 * },
99 * { //R-X
100 * {UR,3}, //R-B
101 * {UR,0}, //R-R
102 * {UR,1}, //R-T
103 * {UR,2}, //R-L
104 * }
105 *
106 * . From the modified table, we can observe that since we
107 * always transverse in anticlockwise direction, the contact
108 * side determines the start corner of the forward (start
109 * index) and return (next index) path.
110 *
111 * 'contactPrev' at 'prevContact' this at start corner
112 * ---------------------------------------------------------------
113 * T of this B of prev UL
114 * L R LL
115 * B T of prev LR
116 * R L UR
117 * ---------------------------------------------------------------
118 *
119 * . Number of corners (count) for the forward path depends on the
120 * distance between the previous contact (contactPrev) and the
121 * next contact in anticlockwise order (mod 4). For example,
122 * contactPrev=R,contactNext=T count=1 BR-TLBRTL
123 * contactPrev=L,contactNext=T count=3 BRTL-B-R-TL
124 *
125 * . In case both the prev and next contact are on the same side, there
126 * would be two possible transversals. Transverse the current box
127 * first or transverse the next box first depend on which contact
128 * comes first in anticlockwise order.
129 *
130 * . Special condition to consider is when two boxes touches at
131 * their corners, the result path may have duplicated the
132 * points. The extra 0 length line doens't really hurt but can
133 * be eliminated.
134 *
135 * . Another case is the case when the previous box touch the
136 * next box. The result is a line extended into the inside of
137 * the polygon. Eliminating the extra vertex is not required
138 * for routing but would enable a more direct route.
139 *
140 */
141 public static void antiClockwise(DotPath path, DotPolyline ret) {
142
143 if (DEBUG)
144 msg.println(
145 "// "
146 + NAME
147 + ".antiClockwise(): e="
148 + path.getOriginal()
149 + ", path=\n"
150 + path.toGeneralPath());
151
152 ret.growTo(path.fSize * 4 + 4);
153 DotPoint[] out = ret.pts;
154 // Instead of using recursion which would be quite expensive
155 // for large number of boxes. The return path is saving from
156 // the back of the output array them moved forward when done.
157 //
158 // xxxx........xxxx
159 // ^fi ^bi
160 int fi = 0; // forward index.
161 int bi = out.length; // backward index.
162 // UL,LL,LR,UR
163 IntPoint[] corners = new IntPoint[4];
164 for (int i = 0; i < 4; ++i)
165 corners[i] = new IntPoint();
166 //
167 DotBox[] boxes = path.fBoxes;
168 DotBox prevbox = null;
169 DotBox box = boxes[0];
170 DotBox box1 = boxes[1];
171 int contact = contactSide(box, box1);
172 for (int i = 0, imax = path.fSize; i < imax; ++i) {
173 corners[0].y = box.ury; // UL
174 corners[0].x = box.llx;
175 corners[1].y = box.lly; // LL
176 corners[1].x = box.llx;
177 corners[2].y = box.lly; // LR
178 corners[2].x = box.urx;
179 corners[3].y = box.ury; // UR
180 corners[3].x = box.urx;
181 int start = contact;
182 int count = 4;
183 if (i + 1 < imax) {
184 box1 = boxes[i + 1];
185 contact = contactSide(box, box1);
186 count = (contact + 4 - (start - 2)) % 4;
187 if (count == 0 && antiClockwiseOrder(box1, prevbox, contact))
188 count += 4;
189 prevbox = box;
190 box = box1;
191 }
192 for (int k = start, n = count; n > 0; k = (k + 1) % 4) {
193 out[fi].x = corners[k].x;
194 out[fi].y = corners[k].y;
195 ++fi;
196 --n;
197 }
198 // (x-1)%4==(x+4-1)%4
199 for (int k = ((start + 4 - 1) % 4), n = 4 - count; n > 0; k = (k + 4 - 1) % 4) {
200 --bi;
201 out[bi].x = corners[k].x;
202 out[bi].y = corners[k].y;
203 --n;
204 }
205 }
206 // Merge forward path to the return path at the back except out[0].
207 while (fi > 1) {
208 --fi;
209 --bi;
210 out[bi].x = out[fi].x;
211 out[bi].y = out[fi].y;
212 }
213 // Remove duplicated points.
214 for (; bi < out.length; ++bi) {
215 if (out[bi].x == out[fi - 1].x && out[bi].y == out[fi - 1].y)
216 continue;
217 out[fi].x = out[bi].x;
218 out[fi].y = out[bi].y;
219 ++fi;
220 }
221 ret.size = fi;
222 if (DEBUG)
223 msg.println("// " + NAME + ".antiClockwise(): ret=\n" + ret.toGeneralPath(3));
224 }
225
226 /** Determine contact side. */
227 private static int contactSide(DotBox box, DotBox box1) {
228 if (box.lly == box1.ury)
229 return BOXBOTTOM;
230 if (box.ury == box1.lly)
231 return BOXTOP;
232 if (box.llx == box1.urx)
233 return BOXLEFT;
234 if (box.urx == box1.llx)
235 return BOXRIGHT;
236 msg.err(
237 NAME
238 + ".contactSide(): Invalid contact"
239 + ": box="
240 + box.toString()
241 + ", box1="
242 + box1.toString());
243 return 0;
244 }
245
246 /** @param side of a third box which both 'box' and 'box1' touched.
247 * @return true if 'box' is before 'box' in anticlockwise order.
248 *
249 * @assume Java coordinate system (origin at UL).
250 */
251 private static boolean antiClockwiseOrder(DotBox box, DotBox box1, int side) {
252 switch (side) {
253 case BOXBOTTOM :
254 return (box.urx < box1.urx);
255 case BOXRIGHT :
256 return (box.lly > box1.lly);
257 case BOXTOP :
258 return (box.llx > box1.llx);
259 case BOXLEFT :
260 return (box.ury < box1.ury);
261 default :
262 msg.err(NAME + ".antiClockwiseOrder(): Invalid side: " + side);
263 return false;
264 }
265 }
266
267 ////////////////////////////////////////////////////////////////////////
268
269 public static void main(String[] args) {
270 DotPath path = new DotPath();
271 DotPolyline ret = new DotPolyline();
272 DotBox box;
273 int[][] sides = { { BOXTOP, BOXTOP, BOXTOP, BOXTOP }, {
274 BOXBOTTOM, BOXBOTTOM, BOXRIGHT, BOXRIGHT, BOXTOP, BOXTOP }, {
275 BOXRIGHT,
276 BOXRIGHT,
277 BOXTOP,
278 BOXRIGHT,
279 BOXRIGHT,
280 BOXBOTTOM,
281 BOXBOTTOM,
282 BOXLEFT,
283 BOXBOTTOM }
284 };
285 for (int i = 0; i < sides.length; ++i) {
286 int[] a = sides[i];
287 path.reset();
288 box = path.add(250, 300, 300, 250);
289 for (int k = 0; k < a.length; ++k) {
290 box = newNeighbour(box, a[k], path);
291 }
292 msg.println("path=" + path.toString());
293 msg.println("\n// Path: " + i + "\n");
294 antiClockwise(path, ret.reset());
295 }
296 }
297
298 private static DotBox newNeighbour(DotBox box, int side, DotPath path) {
299 final int MIN = 10;
300 int llx, lly, urx, ury;
301 int x = (box.urx + box.llx) / 2;
302 int y = (box.ury + box.lly) / 2;
303 int w = box.urx - box.llx;
304 int h = box.lly - box.ury;
305 int dx = (int) ((w - 2 * MIN) * (Math.random() - 0.5));
306 int dy = (int) ((h - 2 * MIN) * (Math.random() - 0.5));
307 int dir = (int) (2 * Math.random() - 1);
308 if (dir == 0)
309 dir = 1;
310 w = (int) (w * (Math.random() + 0.5));
311 h = (int) (h * (Math.random() + 0.5));
312 if (w < 2 * MIN)
313 w = (int) (MIN * (1 + Math.random()) * 4);
314 if (w < 2 * MIN)
315 h = (int) (MIN * (1 + Math.random()) * 4);
316 if (side < 0)
317 side = (int) (Math.random() * 4);
318 switch (side) {
319 case BOXBOTTOM :
320 ury = box.lly;
321 urx = x + dx + (dir > 0 ? w * dir : 0);
322 llx = x + dx + (dir > 0 ? 0 : w * dir);
323 lly = box.lly + h;
324 break;
325 case BOXRIGHT :
326 llx = box.urx;
327 lly = y + dy + (dir > 0 ? w * dir : 0);
328 urx = box.urx + w;
329 ury = y + dy + w * (dir > 0 ? 0 : w * dir);
330 break;
331 case BOXTOP :
332 llx = x + dx + (dir > 0 ? 0 : w * dir);
333 lly = box.ury;
334 urx = x + dx + (dir > 0 ? w * dir : 0);
335 ury = box.ury - h;
336 break;
337 case BOXLEFT :
338 default :
339 urx = box.llx;
340 ury = y + dy + (dir > 0 ? 0 : h * dir);
341 llx = box.llx - w;
342 lly = y + dy + (dir > 0 ? h * dir : 0);
343 break;
344 }
345 return path.add(llx, lly, urx, ury);
346 }
347 }