From 9d968ec366cf2dfa9e7a49d10cdaa457c0d318ab Mon Sep 17 00:00:00 2001
From: Ben Boeckel <MathStuf@gmail.com>
Date: Wed, 22 Apr 2009 16:46:39 -0400
Subject: Fix finalize() to merge the rectangles in the mapping

---
 sigmodr/widgets/mapeditor/WorldMapPlacement.cpp | 57 +++++++++++++++++--------
 1 file changed, 39 insertions(+), 18 deletions(-)

diff --git a/sigmodr/widgets/mapeditor/WorldMapPlacement.cpp b/sigmodr/widgets/mapeditor/WorldMapPlacement.cpp
index 9130a5e8..18408ce4 100644
--- a/sigmodr/widgets/mapeditor/WorldMapPlacement.cpp
+++ b/sigmodr/widgets/mapeditor/WorldMapPlacement.cpp
@@ -19,9 +19,12 @@
 #include "WorldMapPlacement.h"
 
 // Qt includes
+#include <QtCore/QtAlgorithms>
+#include <QtCore/QBitArray>
 #include <QtCore/QMap>
 #include <QtCore/QPair>
 #include <QtCore/QQueue>
+#include <QtCore/QSet>
 
 // Standard includes
 #include <climits>
@@ -39,6 +42,11 @@ static bool operator<(const QPoint& point1, const QPoint& point2)
     return point1.y() < point2.y();
 }
 
+static bool operator<(const QRect& rect1, const QRect& rect2)
+{
+    return rect1.topLeft() < rect2.topLeft();
+}
+
 static bool touches(const QPolygon& polygon1, const QPolygon& polygon2)
 {
     foreach (const QPoint& point, polygon1)
@@ -283,31 +291,44 @@ void WorldMapPlacement::finalize()
 {
     if (m_cacheGood)
         return;
-    foreach (const QRect& rect, m_rects)
+    qSort(m_rects);
+    QList<QBitArray> conns;
+    for (int i = 0; i < m_rects.size(); ++i)
     {
-        bool merged = false;
-        QMutableListIterator<QPolygon> i(m_polygons);
-        QMutableListIterator<QPolygon> j(m_polygons);
-        while (i.hasNext())
+        QBitArray arr(m_rects.size());
+        arr.setBit(i);
+        conns.append(arr);
+    }
+    for (int i = 0; i < m_rects.size(); ++i)
+    {
+        for (int j = 0; j < m_rects.size(); ++j)
         {
-            i.next();
-            if (!merged)
+            if (touches(m_rects[i], m_rects[j]))
             {
-                j.next();
-                if (touches(i.value(), rect))
-                {
-                    i.value() = mergePolygons(i.value(), rect);
-                    merged = true;
-                }
+                conns[i] |= conns[j];
+                conns[j] |= conns[i];
             }
-            else if (touches(j.value(), i.value()))
+        }
+    }
+    QSet<QBitArray> uniqConns = QSet<QBitArray>::fromList(conns);
+    foreach (const QBitArray& array, uniqConns)
+    {
+        QPolygon polygon;
+        for (int i = 0; i < m_rects.size(); ++i)
+        {
+            if (array[i])
             {
-                j.value() = mergePolygons(j.value(), i.value());
-                i.remove();
+                if (polygon.isEmpty())
+                    polygon = m_rects[i];
+                else
+                {
+                    QList<QPolygon> polygons = mergePolygons(polygon, m_rects[i]);
+                    polygon = polygons.takeFirst();
+                    m_polygons += polygons;
+                }
             }
         }
-        if (!merged)
-            m_polygons.append(rect);
+        m_polygons.append(polygon);
     }
     m_cacheGood = true;
 }
-- 
cgit