win/Qt/qt_clust.cpp

   1 /* aNetHack 0.0.1       qt_clust.cpp    $ANH-Date$  $ANH-Branch$:$ANH-Revision$ */
   2 /* Copyright (c) Warwick Allison, 1999. */
   3 /* aNetHack may be freely redistributed.  See license for details. */
   4 #include "qt_clust.h"
   5
   6 static
   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 */
  27 Clusterizer::Clusterizer(int maxclusters) :
  28         cluster(new QRect[maxclusters]),
  29         count(0),
  30         max(maxclusters)
  31 { }
  32
  33 Clusterizer::~Clusterizer()
  34 {
  35         delete [] cluster;
  36 }
  37
  38 void Clusterizer::clear()
  39 {
  40         count=0;
  41 }
  42
  43 void Clusterizer::add(int x, int y)
  44 {
  45         add(QRect(x,y,1,1));
  46 }
  47
  48 void Clusterizer::add(int x, int y, int w, int h)
  49 {
  50         add(QRect(x,y,w,h));
  51 }
  52
  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
 165 const QRect& Clusterizer::operator[](int i)
 166 {
 167         return cluster[i];
 168 }