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