1 /* NetHack 3.6 qt_clust.cpp $NHDT-Date: 1524684507 2018/04/25 19:28:27 $ $NHDT-Branch: NetHack-3.6.0 $:$NHDT-Revision: 1.8 $ */
2 /* Copyright (c) Warwick Allison, 1999. */
3 /* NetHack may be freely redistributed. See license for details. */
7 void include(QRect& r, const QRect& rect)
9 if (rect.left()<r.left()) {
10 r.setLeft(rect.left());
12 if (rect.right()>r.right()) {
13 r.setRight(rect.right());
15 if (rect.top()<r.top()) {
18 if (rect.bottom()>r.bottom()) {
19 r.setBottom(rect.bottom());
24 A Clusterizer groups rectangles (QRects) into non-overlapping rectangles
25 by a merging heuristic.
27 Clusterizer::Clusterizer(int maxclusters) :
28 cluster(new QRect[maxclusters]),
33 Clusterizer::~Clusterizer()
38 void Clusterizer::clear()
43 void Clusterizer::add(int x, int y)
48 void Clusterizer::add(int x, int y, int w, int h)
53 void Clusterizer::add(const QRect& rect)
55 QRect biggerrect(rect.x()-1,rect.y()-1,rect.width()+2,rect.height()+2);
57 //assert(rect.width()>0 && rect.height()>0);
61 for (cursor=0; cursor<count; cursor++) {
62 if (cluster[cursor].contains(rect)) {
63 // Wholly contained already.
68 int lowestcost=9999999;
70 for (cursor=0; cursor<count; cursor++) {
71 if (cluster[cursor].intersects(biggerrect)) {
72 QRect larger=cluster[cursor];
74 int cost=larger.width()*larger.height()
75 - cluster[cursor].width()*cluster[cursor].height();
77 if (cost < lowestcost) {
79 for (int c=0; c<count && !bad; c++) {
80 bad=cluster[c].intersects(larger) && c!=cursor;
90 include(cluster[cheapest],rect);
95 cluster[count++]=rect;
100 // add to closest cluster
101 // do cheapest cluster merge, add to new cluster
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) {
112 for (int c=0; c<count && !bad; c++) {
113 bad=cluster[c].intersects(larger) && c!=cursor;
122 // XXX could make an heuristic guess as to whether we
123 // XXX need to bother looking for a cheap merge.
125 int cheapestmerge1=-1;
126 int cheapestmerge2=-1;
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) {
138 for (int c=0; c<count && !bad; c++) {
139 bad=cluster[c].intersects(larger) && c!=cursor;
142 cheapestmerge1=merge1;
143 cheapestmerge2=merge2;
151 if (cheapestmerge1>=0) {
152 include(cluster[cheapestmerge1],cluster[cheapestmerge2]);
153 cluster[cheapestmerge2]=cluster[count--];
155 // if (!cheapest) debugRectangles(rect);
156 include(cluster[cheapest],rect);
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
165 const QRect& Clusterizer::operator[](int i)