Project

General

Profile

Statistics
| Branch: | Revision:

root / src / layout / startreeembedding.cc @ 8aeaaccc

History | View | Annotate | Download (8.17 KB)

1 01873262 Georg Kunz
//=========================================================================
2
//  STARTREEEMBEDDING.CC - part of
3
//                  OMNeT++/OMNEST
4
//           Discrete System Simulation in C++
5
//
6
//  Author: Levente Meszaros
7
//
8
//=========================================================================
9
10
/*--------------------------------------------------------------*
11
  Copyright (C) 2006-2008 OpenSim Ltd.
12

13
  This file is distributed WITHOUT ANY WARRANTY. See the file
14
  `license' for details on this and other legal matters.
15
*--------------------------------------------------------------*/
16
17
#include "startreeembedding.h"
18
19
USING_NAMESPACE
20
21
StarTreeEmbedding::StarTreeEmbedding(GraphComponent *graphComponent, double vertexSpacing)
22
{
23
    this->graphComponent = graphComponent;
24
    this->vertexSpacing = vertexSpacing;
25
}
26
27
void StarTreeEmbedding::embed()
28
{
29
    calculateCenter();
30
    rotateCenter();
31
    calculatePosition();
32
}
33
34
void StarTreeEmbedding::calculateCenter()
35
{
36
    calculateCenterRecursive(graphComponent->spanningTreeRoot);
37
}
38
39
void StarTreeEmbedding::calculateCenterRecursive(Vertex *vertex)
40
{
41
    if (vertex->spanningTreeChildren.size() == 0)
42
    {
43
        // position a vertex without children
44
        vertex->starTreeRadius = vertex->rc.rs.getDiagonalLength() / 2;
45
        vertex->starTreeCenter = Pt::getZero();
46
        vertex->starTreeCircleCenter = Pt::getZero();
47
    }
48
    else
49
    {
50
        vertex->starTreeCenter =  Pt::getZero();
51
52
        for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++)
53
            calculateCenterRecursive(*it);
54
55
        std::vector<Pt> pts;
56
        std::vector<Cc> circles;
57
58
        for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++) {
59
            Vertex *vertexChild = *it;
60
            pts.clear();
61
            circles.clear();
62
63
            circles.push_back(Cc(Pt::getZero(), vertex->rc.rs.getDiagonalLength() / 2 + vertexSpacing + vertexChild->starTreeRadius));
64
65
            for (std::vector<Vertex *>::iterator jt = vertex->spanningTreeChildren.begin(); jt != vertex->spanningTreeChildren.end(); jt++) {
66
                Vertex *vertexPositioned = *jt;
67
68
                if (vertexPositioned == vertexChild)
69
                    break;
70
71
                circles.push_back(Cc(vertexPositioned->starTreeCenter.copy().add(vertexPositioned->starTreeCircleCenter), vertexPositioned->starTreeRadius + vertexSpacing + vertexChild->starTreeRadius));
72
            }
73
74
            // Find point candidates
75
            for (int i = 0; i < (int)circles.size(); i++)
76
                for (int j = i + 1; j < (int)circles.size(); j++)
77
                {
78
                    Cc circle1 = circles[i];
79
                    Cc circle2 = circles[j];
80
81
                    std::vector<Pt> intersectingPts = circle1.basePlaneProjectionIntersect(circle2);
82
83
                    for (std::vector<Pt>::iterator it = intersectingPts.begin(); it != intersectingPts.end(); it++)
84
                        pts.push_back(*it);
85
                }
86
87
            // Default points
88
            if (circles.size() == 1)
89
            {
90
                Cc circleSelf = circles[0];
91
                pts.push_back(circleSelf.getCenterTop());
92
                pts.push_back(circleSelf.getCenterBottom());
93
                pts.push_back(circleSelf.getLeftCenter());
94
                pts.push_back(circleSelf.getRightCenter());
95
            }
96
97
            for (int j = 0; j < (int)pts.size(); j++) {
98
                for (std::vector<Cc>::iterator kt = circles.begin(); kt != circles.end(); kt++) {
99
                    Pt pt = pts[j];
100
                    Cc cc = *kt;
101
102
                    if (pt.getDistance(cc.origin) < cc.radius - 1)
103
                    {
104
                        pts.erase(pts.begin() + j--);
105
                        break;
106
                    }
107
                }
108
            }
109
110
            // Optimize cost function
111
            double costMin = POSITIVE_INFINITY;
112
113
            for (std::vector<Pt>::iterator jt = pts.begin(); jt != pts.end(); jt++) {
114
                Pt pt = *jt;
115
                double cost = vertex->starTreeCenter.getDistance(pt);
116
117
                if (cost < costMin)
118
                {
119
                    costMin = cost;
120
                    vertexChild->starTreeCenter = pt.copy().subtract(vertexChild->starTreeCircleCenter);
121
                }
122
            }
123
        }
124
125
        // Find minimum covering circle
126
        circles.clear();
127
        circles.push_back(Cc(Pt::getZero(), vertex->rc.rs.getDiagonalLength() / 2));
128
129
        for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++) {
130
            Vertex *vertexChild = *it;
131
            circles.push_back(Cc(vertexChild->starTreeCenter.copy().add(vertexChild->starTreeCircleCenter), vertexChild->starTreeRadius));
132
        }
133
134
        Cc circleEncolsing = Cc::getBasePlaneProjectionEnclosingCircle(circles);
135
136
        vertex->starTreeRadius = circleEncolsing.radius;
137
        vertex->starTreeCircleCenter = circleEncolsing.origin;
138
    }
139
}
140
141
void StarTreeEmbedding::rotateCenter()
142
{
143
    rotateCenterRecursive(graphComponent->spanningTreeRoot);
144
}
145
146
void StarTreeEmbedding::rotateCenterRecursive(Vertex *vertex)
147
{
148
    if (vertex->spanningTreeChildren.size() != 0)
149
    {
150
        if (vertex->spanningTreeParent)
151
        {
152
            Pt pt = Pt::getZero();
153
            double angle = (vertex->starTreeCenter.copy().add(vertex->starTreeCircleCenter)).getBasePlaneProjectionAngle();
154
155
            // Find weight point
156
            Pt weightPoint = Pt::getZero();
157
            double area = 0;
158
159
            for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++) {
160
                Vertex *vertexChild = *it;
161
                area += vertexChild->rc.rs.getArea();
162
                weightPoint.add(vertexChild->starTreeCenter.copy().add(vertex->starTreeCircleCenter).multiply(vertexChild->rc.rs.getArea()));
163
            }
164
165
            weightPoint.divide(area);
166
            double angleWeight = weightPoint.getBasePlaneProjectionAngle();
167
            double angleRotate = angle - angleWeight;
168
169
            if (!isNaN(angleRotate))
170
            {
171
                // Rotate children around circle center
172
                for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++) {
173
                    Vertex *vertexChild = *it;
174
                    pt.assign(vertexChild->starTreeCenter).add(vertexChild->starTreeCircleCenter).add(vertex->starTreeCircleCenter);
175
                    pt.basePlaneRotate(angleRotate);
176
                    vertexChild->starTreeCenter.assign(pt).subtract(vertexChild->starTreeCircleCenter);
177
                }
178
179
                // Rotate parent around circle center
180
                pt.assign(vertex->starTreeCircleCenter).reverse();
181
                pt.basePlaneRotate(angleRotate);
182
                vertex->starTreeCenter.add(vertex->starTreeCircleCenter).add(pt);
183
                vertex->starTreeCircleCenter.assign(pt).reverse();
184
185
                // Correct children position
186
                for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++) {
187
                    Vertex *vertexChild = *it;
188
                    vertexChild->starTreeCenter.subtract(vertex->starTreeCircleCenter);
189
                }
190
            }
191
        }
192
193
        for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++)
194
            rotateCenterRecursive(*it);
195
    }
196
}
197
198
void StarTreeEmbedding::calculatePosition()
199
{
200
    calculatePositionRecursive(graphComponent->spanningTreeRoot, Pt::getZero());
201
}
202
203
void StarTreeEmbedding::calculatePositionRecursive(Vertex *vertex, Pt pt)
204
{
205
    vertex->rc.pt = Pt(pt.x - vertex->rc.rs.width / 2, pt.y  - vertex->rc.rs.height / 2, pt.z);
206
207
    if (vertex->spanningTreeParent)
208
        vertex->starTreeCircleCenter.add(pt);
209
210
    for (std::vector<Vertex *>::iterator it = vertex->spanningTreeChildren.begin(); it != vertex->spanningTreeChildren.end(); it++) {
211
        Vertex *child = *it;
212
        calculatePositionRecursive(child, pt.copy().add(child->starTreeCenter));
213
    }
214
}