?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / src / planarlayout / MMCBBase.cpp
blobabc44de6f9bccec16808b61336a187218bc16e96
1 /*
2 * $Revision: 2554 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-06 11:39:38 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of Mixed-Model crossings beautifiers.
11 *
12 * \author Carsten Gutwenger
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
42
43 #include <ogdf/planarlayout/MMCBDoubleGrid.h>
44 #include <ogdf/planarlayout/MMCBLocalStretch.h>
45
46
47 namespace ogdf {
48
49
50 //------------------------------------------------------------------
51 // MMCBBase
52 //------------------------------------------------------------------
53
54 void MMCBBase::insertBend(GridLayout &gl, edge e, node v, int x, int y)
55 {
56 if (v == e->target()) {
57 gl.bends(e).pushBack(IPoint(x,y));
58 } else {
59 gl.bends(e).pushFront(IPoint(x,y));
60 }
61 }
62
63
64 void MMCBBase::copyOn(int old_a[] , int new_a[])
65 {
66 for (int i = 0; i < 3; ++i)
67 new_a[i] = old_a[i];
68 }
69
70
71 int MMCBBase::workOn(GridLayout &gl, node v)
72 {
73 edge L[4];
74 int ev[4][3];
75 int count = 0;
76
77 adjEntry adj;
78 forall_adj(adj,v)
79 {
80 edge e = adj->theEdge();
81
82 IPolyline &ip = gl.bends(e);
83 int xc = gl.x(v), yc = gl.y(v);
84 int xxc = gl.x(v), yyc = gl.y(v);
85 int add_l = 0;
86 do {
87 if (ip.size() < (1+add_l) ) {
88 if (v == e->target()) {
89 xc = gl.x(e->source());
90 yc = gl.y(e->source());
91 } else {
92 xc = gl.x(e->target());
93 yc = gl.y(e->target());
94 }
95 } else {
96 IPoint p;
97 if (v == e->target()) {
98 p = *ip.get(ip.size()-add_l -1);
99 } else {
100 p = *ip.get(1+add_l -1);
101 }
102 xc = p.m_x;
103 yc = p.m_y;
104 }
105 ++add_l;
106 } while((xc == xxc) && (yc == yyc));
107
108 if (xc < gl.x(v))
109 ev[count][0] = -1;
110 else if (xc == gl.x(v))
111 ev[count][0] = 0;
112 else
113 ev[count][0] = 1;
114
115 if (yc < gl.y(v))
116 ev[count][1] = -1;
117 else if (yc == gl.y(v))
118 ev[count][1] = 0;
119 else
120 ev[count][1] = 1;
121
122 L[count] = e;
123 ++count;
124 if (3 < count)
125 break;
126 }
127
128 for (int i = 0; i < 4 ; i++)
129 {
130 if (ev[i][0] > 0) {
131 ev[i][2] = 4 + ev[i][1] + 2;
132
133 } else if (ev[i][0] == 0) {
134 if(ev[i][1] > 0) {
135 ev[i][2] = 0;
136 } else {
137 ev[i][2] = 4;
138 }
139
140 } else {
141 ev[i][2] = -ev[i][1]+2;
142 }
143 }
144
145 int ew[4][3];
146 edge Lw[4];
147
148 int k = 4;
149 for (int i = 0; (i < 8) && (k >= 0) ; i++)
150 {
151 for (int j = 0; j < 4; j++)
152 {
153 if (i == ev[j][2]) {
154 copyOn(ev[j],ew[4-k]);
155 edge edge_k = L[j];
156 Lw[4-k] = edge_k;
157 --k;
158 }
159 }
160 }
161
162 //so now in ew the edges are in an order against the clock starting at position 0,1
163 int ea, eb;
164 int crossingCase = 0;
165
166 ea = ew[2][2] - ew[0][2];
167 if (ea > 4)
168 ea = 8 - ea;
169 eb = ew[3][2] - ew[1][2];
170 if (eb > 4)
171 eb = 8 - eb;
172
173 // first case: there is an edge with angle of pi/2
174 // in this case i'm going to, well, cut this edge
175 // e4 O _/e3 Ooo _/
176 // O _/ Ooo _/
177 // \ O _/ \ OXo
178 // O / _/ Ooo
179 // -- *ooooooo^ ==> -- / Ooo
180 // e2
181 // / | \ / | \_
182 // e1
183
184 int lw_add = 0;
185 if (ea <= 2) {
186 if (ew[2][2] - ew[0][2] > 4) {
187 lw_add = 2;
188 crossingCase = 1;
189 } else {
190 crossingCase = 1;
191 }
192 } else if (eb <=2) {
193 if (ew[3][2] - ew[1][2] > 4) {
194 lw_add = 1;
195 crossingCase = 1;
196 } else {
197 lw_add = 3;
198 crossingCase = 1;
199 }
200
201 // second case: both angles are 3pi/4, in this case
202 // i'm going to take both of them back with a row
203 // ^ _/ ooO _/
204 // O _/ ooO _/
205 // O _/ Ooo _/
206 // O/ Ooo _/
207 // *o ==> OXo
208 // |Ooo _/ Ooo
209 // | Oo _/ Ooo
210 // | Ooo \_ Ooo
211 // | Oo \_ Oo
212 //
213 } else if (ea == 3) {
214 if (eb == 3) {
215 if (ew[1][2]-ew[0][2] >= 3) {
216 if (ew[1][2]-ew[0][2] == 3)
217 crossingCase = 2;
218 else
219 crossingCase = 3;
220 }
221 else if (ew[2][2]-ew[1][2] >= 3) {
222 lw_add = 3;
223 if (ew[2][2]-ew[1][2] == 3)
224 crossingCase=2;
225 else
226 crossingCase=3;
227 } else if (ew[3][2]-ew[2][2] >= 3) {
228 lw_add = 2;
229 if (ew[3][2]-ew[2][2] == 3)
230 crossingCase=2;
231 else
232 crossingCase=3;
233 } else {
234 lw_add = 1;
235 if (ew[3][2]-ew[0][2] == 3)
236 crossingCase=2;
237 else
238 crossingCase=3;
239 }
240
241 // third case: one of the angles is 3pi/4 and the other one is pi
242 // ^ O
243 // O O
244 // O O
245 // O O
246 // --------*o------- ==> ---------X--------
247 // Ooo O
248 // Ooo O
249 // Ooo O
250 // Oo Ooooooooo
251 //
252 } else {
253 if (ew[1][2]-ew[0][2] == 2) {
254 crossingCase=4;
255 }
256 else {
257 lw_add = 2;
258 crossingCase=4;
259 }
260 }
261 } else if (eb == 3) {
262 if (ew[2][2]-ew[1][2] == 2) {
263 lw_add = 3;
264 crossingCase=4;
265 } else {
266 lw_add = 1;
267 crossingCase=4;
268 }
269 }
270
271 // v, Lw, ev
272 copyOn(ew[(0+lw_add) %4],ev[0]);
273 copyOn(ew[(1+lw_add) %4],ev[1]);
274 copyOn(ew[(2+lw_add) %4],ev[2]);
275 copyOn(ew[(3+lw_add) %4],ev[3]);
276
277 edge e0 = Lw[(0+lw_add) %4];
278 edge e1 = Lw[(1+lw_add) %4];
279 edge e2 = Lw[(2+lw_add) %4];
280 edge e3 = Lw[(3+lw_add) %4];
281
282 int retVal = 0;
283
284 switch(crossingCase)
285 {
286 case 4:
287 if ((ev[0][0]*ev[0][1] == 0) || (gl.bends(e3).size() > 0)) {
288 insertBend(gl,e3,v,gl.x(v)-ev[1][0],gl.y(v)-ev[1][1]);
289 } else {
290 insertBend(gl,e0,v,gl.x(v)+ev[3][0],gl.y(v)+ev[3][1]);
291 insertBend(gl,e2,v,gl.x(v)-ev[3][0],gl.y(v)-ev[3][1]);
292 insertBend(gl,e1,v,gl.x(v)+ev[0][0]+ev[3][0],gl.y(v)+ev[0][1]+ev[3][1]);
293 }
294 break;
295
296 case 3:
297 if (ev[0][0]*ev[0][1] != 0) {
298 insertBend(gl,e0,v,gl.x(v)-ev[2][0],gl.y(v)-ev[2][1]);
299 insertBend(gl,e1,v,gl.x(v)-ev[3][0],gl.y(v)-ev[3][1]);
300 } else {
301 gl.x(v) = gl.x(v)+ev[2][0]-ev[1][0];
302 gl.y(v) = gl.y(v)+ev[2][1]-ev[1][1];
303 if (ev[2][0]-ev[1][0] == 0) {
304 retVal = 2;
305 } else {
306 retVal = 1;
307 }
308 }
309 break;
310
311 case 2:
312 insertBend(gl,e1,v,gl.x(v)-ev[3][0],gl.y(v)-ev[3][1]);
313 insertBend(gl,e2,v,gl.x(v)-ev[0][0],gl.y(v)-ev[0][0]);
314 break;
315
316 case 1:
317 if (ev[0][0]*ev[0][1] == 0) {
318 int old_x = gl.x(v);
319 int old_y = gl.y(v);
320 int x_plus = (ev[0][0]+ev[2][0]);
321 int y_plus = (ev[0][1]+ev[2][1]);
322 insertBend(gl,e0,v,old_x+2*ev[0][0],old_y+2*ev[0][1]);
323 insertBend(gl,e2,v,old_x+2*ev[2][0],old_y+2*ev[2][1]);
324 insertBend(gl,e1,v,old_x,old_y);
325 insertBend(gl,e3,v,old_x,old_y);
326 gl.x(v) = old_x+x_plus;
327 gl.y(v) = old_y+y_plus;
328 retVal = 3;
329 } else {
330 int old_x = gl.x(v);
331 int old_y = gl.y(v);
332
333 gl.x(v) = gl.x(v)+ev[1][0];
334 gl.y(v) = gl.y(v)+ev[1][1];
335 insertBend(gl,e3,v,old_x,old_y);
336 insertBend(gl,e1,v,gl.x(v)+ev[1][0],gl.y(v)+ev[1][1]);
337 if (ev[1][0] != 0) {
338 retVal = 1;
339 } else {
340 retVal = 2;
341 }
342
343 }
344 break;
345
346 case 0:
347 retVal = 0;
348 break;
349
350 OGDF_NODEFAULT
351 }
352
353 return retVal;
354 }
355
356
357 //------------------------------------------------------------------
358 // MMCBDoubleGrid
359 //------------------------------------------------------------------
360
361 void MMCBDoubleGrid::doCall(const PlanRep &PG, GridLayout &gl, const List<node> &L)
362 {
363 edge e;
364 forall_edges(e,PG) {
365 ListIterator<IPoint> it;
366 for(it = gl.bends(e).begin(); it.valid(); ++it) {
367 IPoint &p = *it;
368 p.m_x *= 2;
369 p.m_y *= 2;
370 }
371 }
372
373 node v;
374 forall_nodes(v,PG) {
375 gl.x(v) *= 2;
376 gl.y(v) *= 2;
377 }
378
379 ListConstIterator<node> itV;
380 for(itV = L.begin(); itV.valid(); ++itV)
381 workOn(gl,*itV);
382 }
383
384
385 //------------------------------------------------------------------
386 // MMCBLocalStretch
387 //------------------------------------------------------------------
388
389 void MMCBLocalStretch::doCall(const PlanRep &PG, GridLayout &gl, const List<node> &L)
390 {
391 int max_x = 0, max_y = 0;
392
393 edge e;
394 forall_edges(e,PG) {
395 ListIterator<IPoint> it;
396 for(it = gl.bends(e).begin(); it.valid(); ++it) {
397 IPoint &p = *it;
398 if (p.m_x > max_x) max_x = p.m_x;
399 if (p.m_y > max_y) max_y = p.m_y;
400 p.m_x *= 2;
401 p.m_y *= 2;
402 }
403 }
404
405 node v;
406 forall_nodes(v,PG) {
407 if (gl.x(v) > max_x) max_x = gl.x(v);
408 if (gl.y(v) > max_y) max_y = gl.y(v);
409 gl.x(v) *= 2;
410 gl.y(v) *= 2;
411 }
412
413 Array<int> change_x(0,max_x,1);
414 Array<int> change_y(0,max_y,1);
415
416 change_x[0] = 0;
417 change_y[0] = 0;
418
419 ListConstIterator<node> itV;
420 for(itV = L.begin(); itV.valid(); ++itV) {
421 v = *itV;
422 int val = workOn(gl,v);
423 if (val > 0) {
424 if (val != 2)
425 change_x[(gl.x(v)+1)/2] = 0;
426 if (val != 1)
427 change_y[(gl.y(v)+1)/2] = 0;
428 }
429 }
430
431 if (max_x > 1)
432 for (int i = 1; i <= max_x; i++) {
433 change_x[i] = change_x[i] + change_x[i-1];
434 }
435 if (max_y > 1)
436 for (int i = 1; i <= max_y; i++) {
437 change_y[i] = change_y[i] + change_y[i-1];
438 }
439
440 forall_edges(e,PG) {
441 ListIterator<IPoint> it;
442 for(it = gl.bends(e).begin(); it.valid(); ++it) {
443 IPoint &p = *it;
444 p.m_x = p.m_x - change_x[(p.m_x+1)/2];
445 p.m_y = p.m_y - change_y[(p.m_y+1)/2];
446 }
447 }
448
449 forall_nodes(v,PG) {
450 gl.x(v)=gl.x(v)-change_x[(gl.x(v)+1)/2];
451 gl.y(v)=gl.y(v)-change_y[(gl.y(v)+1)/2];
452 }
453 }
454
455
456 } // end namespace ogdf
Windows Explorer Extension to Operate Git