Project

General

Profile

Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.73 KB)

1
//=========================================================================
2
//  HEAPEMBEDDING.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 "heapembedding.h"
18

    
19
USING_NAMESPACE
20

    
21
HeapEmbedding::HeapEmbedding(GraphComponent *graphComponent, double vertexSpacing)
22
{
23
    this->graphComponent = graphComponent;
24
    this->vertexSpacing = vertexSpacing;
25
}
26

    
27
void HeapEmbedding::embed()
28
{
29
    std::vector<Rc> rcs; // rectangles of vertices already positioned
30
    std::vector<Pt> pts; // candidate points where vertices may be positioned
31
    pts.push_back(Pt::getZero());
32

    
33
    // delete all vertex positions
34
    for (int i = 0; i < graphComponent->getVertexCount(); i++)
35
        graphComponent->getVertex(i)->rc.pt = Pt::getNil();
36

    
37
    // go through vertices in spanning tree order
38
    for (int i = 0; i < (int)graphComponent->spanningTreeVertices.size(); i++) {
39
        Vertex *vertex = graphComponent->spanningTreeVertices[i];
40
        Rs rs = vertex->rc.rs;
41

    
42
        // find the best minimizing the distance cost function
43
        double bestDistance = POSITIVE_INFINITY;
44
        Rc bestRc;
45

    
46
        // for all candidate points
47
        for (int j = 0; j < (int)pts.size(); j++) {
48
            Pt pt = pts[j];
49

    
50
            // align vertex to candidate points with its various points
51
            for (int k = 0; k < 8; k++) {
52
                Rc candidateRc;
53
                Pt ptCopy(pt);
54

    
55
                switch (k) {
56
                    case 0:
57
                        // candidate point is top left
58
                        candidateRc = Rc(ptCopy.subtract(0, 0, 0), rs);
59
                        break;
60
                    case 1:
61
                        // candidate point is top center
62
                        candidateRc = Rc(ptCopy.subtract(rs.width / 2, 0, 0), rs);
63
                        break;
64
                    case 2:
65
                        // candidate point is top right
66
                        candidateRc = Rc(ptCopy.subtract(rs.width, 0, 0), rs);
67
                        break;
68
                    case 3:
69
                        // candidate point is center left
70
                        candidateRc = Rc(ptCopy.subtract(0, rs.height / 2, 0), rs);
71
                        break;
72
                    case 4:
73
                        // candidate point is center right
74
                        candidateRc = Rc(ptCopy.subtract(rs.width, rs.height / 2, 0), rs);
75
                        break;
76
                    case 5:
77
                        // candidate point is bottom left
78
                        candidateRc = Rc(ptCopy.subtract(0, rs.height, 0), rs);
79
                        break;
80
                    case 6:
81
                        // candidate point is bottom center
82
                        candidateRc = Rc(ptCopy.subtract(rs.width / 2, rs.height, 0), rs);
83
                        break;
84
                    case 7:
85
                        // candidate point is bottom right
86
                        candidateRc = Rc(ptCopy.subtract(rs.width, rs.height, 0), rs);
87
                        break;
88
                }
89

    
90
                // find an already positioned vertex which would intersect the candidate rectangle
91
                bool intersects = false;
92
                for (int l = 0; l < (int)rcs.size(); l++) {
93
                    Rc rc = rcs[l];
94
                    if (candidateRc.basePlaneProjectionIntersects(rc, true)) {
95
                        intersects = true;
96
                        break;
97
                    }
98
                }
99
                // if found one then this is a wrong candidate
100
                if (intersects)
101
                    continue;
102

    
103
                // calculate the distance sum to neighbours already positioned
104
                double distance = 0;
105
                for (int k = 0; k < (int)vertex->neighbours.size(); k++) {
106
                    Vertex *neighbour = vertex->neighbours[k];
107

    
108
                    if (!neighbour->rc.pt.isNil())
109
                        distance += candidateRc.getCenterCenter().getDistance(neighbour->rc.getCenterCenter());
110
                }
111

    
112
                // if better than the current best
113
                if (distance < bestDistance)
114
                                {
115
                    bestRc = candidateRc;
116
                    bestDistance = distance;
117
                }
118
            }
119
        }
120

    
121
        // store position and rectangle
122
        vertex->rc.pt = bestRc.pt;
123

    
124
        // grow rectangle
125
        bestRc.pt.x -= vertexSpacing;
126
        bestRc.pt.y -= vertexSpacing;
127
        bestRc.rs.width += 2 * vertexSpacing;
128
        bestRc.rs.height += 2 * vertexSpacing;
129

    
130
        // delete candidate points covered by best rc
131
        for (int j = 0; j < (int)pts.size(); j++) {
132
            Pt pt = pts[j];
133

    
134
            if (bestRc.basePlaneProjectionContains(pt, true))
135
                pts.erase(pts.begin() + j--);
136
        }
137

    
138
        // push new candidates
139
        pushPtUnlessRcsContains(pts, rcs, bestRc.getCenterTop());
140
        pushPtUnlessRcsContains(pts, rcs, bestRc.getCenterBottom());
141
        pushPtUnlessRcsContains(pts, rcs, bestRc.getLeftCenter());
142
        pushPtUnlessRcsContains(pts, rcs, bestRc.getRightCenter());
143

    
144
        rcs.push_back(bestRc);
145
    }
146
}
147

    
148
void HeapEmbedding::pushPtUnlessRcsContains(std::vector<Pt>& pts, const std::vector<Rc>& rcs, const Pt& pt)
149
{
150
    for (int j = 0; j < (int)rcs.size(); j++) {
151
        Rc rc = rcs[j];
152

    
153
        if (rc.basePlaneProjectionContains(pt, true))
154
            return;
155
    }
156

    
157
    pts.push_back(pt);
158
}