1 /* SCCS Id: @(#)qt_clust.cpp 3.4 1999/11/19 */
2 /* Copyright (c) Warwick Allison, 1999. */
3 /* NetHack may be freely redistributed. See license for details. */
4 #include "qt_clust.h"
5
6 static
include(QRect & r,const QRect & rect)7 void include(QRect& r, const QRect& rect)
8 {
9 if (rect.left()<r.left()) {
10 r.setLeft(rect.left());
11 }
12 if (rect.right()>r.right()) {
13 r.setRight(rect.right());
14 }
15 if (rect.top()<r.top()) {
16 r.setTop(rect.top());
17 }
18 if (rect.bottom()>r.bottom()) {
19 r.setBottom(rect.bottom());
20 }
21 }
22
23 /*
24 A Clusterizer groups rectangles (QRects) into non-overlapping rectangles
25 by a merging heuristic.
26 */
Clusterizer(int maxclusters)27 Clusterizer::Clusterizer(int maxclusters) :
28 cluster(new QRect[maxclusters]),
29 count(0),
30 max(maxclusters)
31 { }
32
~Clusterizer()33 Clusterizer::~Clusterizer()
34 {
35 delete [] cluster;
36 }
37
clear()38 void Clusterizer::clear()
39 {
40 count=0;
41 }
42
add(int x,int y)43 void Clusterizer::add(int x, int y)
44 {
45 add(QRect(x,y,1,1));
46 }
47
add(int x,int y,int w,int h)48 void Clusterizer::add(int x, int y, int w, int h)
49 {
50 add(QRect(x,y,w,h));
51 }
52
add(const QRect & rect)53 void Clusterizer::add(const QRect& rect)
54 {
55 QRect biggerrect(rect.x()-1,rect.y()-1,rect.width()+2,rect.height()+2);
56
57 //assert(rect.width()>0 && rect.height()>0);
58
59 int cursor;
60
61 for (cursor=0; cursor<count; cursor++) {
62 if (cluster[cursor].contains(rect)) {
63 // Wholly contained already.
64 return;
65 }
66 }
67
68 int lowestcost=9999999;
69 int cheapest=-1;
70 for (cursor=0; cursor<count; cursor++) {
71 if (cluster[cursor].intersects(biggerrect)) {
72 QRect larger=cluster[cursor];
73 include(larger,rect);
74 int cost=larger.width()*larger.height()
75 - cluster[cursor].width()*cluster[cursor].height();
76
77 if (cost < lowestcost) {
78 bool bad=FALSE;
79 for (int c=0; c<count && !bad; c++) {
80 bad=cluster[c].intersects(larger) && c!=cursor;
81 }
82 if (!bad) {
83 cheapest=cursor;
84 lowestcost=cost;
85 }
86 }
87 }
88 }
89 if (cheapest>=0) {
90 include(cluster[cheapest],rect);
91 return;
92 }
93
94 if (count < max) {
95 cluster[count++]=rect;
96 return;
97 }
98
99 // Do cheapest of:
100 // add to closest cluster
101 // do cheapest cluster merge, add to new cluster
102
103 lowestcost=9999999;
104 cheapest=-1;
105 for (cursor=0; cursor<count; cursor++) {
106 QRect larger=cluster[cursor];
107 include(larger,rect);
108 int cost=larger.width()*larger.height()
109 - cluster[cursor].width()*cluster[cursor].height();
110 if (cost < lowestcost) {
111 bool bad=FALSE;
112 for (int c=0; c<count && !bad; c++) {
113 bad=cluster[c].intersects(larger) && c!=cursor;
114 }
115 if (!bad) {
116 cheapest=cursor;
117 lowestcost=cost;
118 }
119 }
120 }
121
122 // XXX could make an heuristic guess as to whether we
123 // XXX need to bother looking for a cheap merge.
124
125 int cheapestmerge1=-1;
126 int cheapestmerge2=-1;
127
128 for (int merge1=0; merge1<count; merge1++) {
129 for (int merge2=0; merge2<count; merge2++) {
130 if (merge1!=merge2) {
131 QRect larger=cluster[merge1];
132 include(larger,cluster[merge2]);
133 int cost=larger.width()*larger.height()
134 - cluster[merge1].width()*cluster[merge1].height()
135 - cluster[merge2].width()*cluster[merge2].height();
136 if (cost < lowestcost) {
137 bool bad=FALSE;
138 for (int c=0; c<count && !bad; c++) {
139 bad=cluster[c].intersects(larger) && c!=cursor;
140 }
141 if (!bad) {
142 cheapestmerge1=merge1;
143 cheapestmerge2=merge2;
144 lowestcost=cost;
145 }
146 }
147 }
148 }
149 }
150
151 if (cheapestmerge1>=0) {
152 include(cluster[cheapestmerge1],cluster[cheapestmerge2]);
153 cluster[cheapestmerge2]=cluster[count--];
154 } else {
155 // if (!cheapest) debugRectangles(rect);
156 include(cluster[cheapest],rect);
157 }
158
159 // NB: clusters do not intersect (or intersection will
160 // overwrite). This is a result of the above algorithm,
161 // given the assumption that (x,y) are ordered topleft
162 // to bottomright.
163 }
164
operator [](int i)165 const QRect& Clusterizer::operator[](int i)
166 {
167 return cluster[i];
168 }
169