Changeset 461

Timestamp:

11/12/08 18:11:11 (1 year ago)

Author:

aaron

Message:

version 0.2

Files:

• trunk/clustr/README (modified) (1 diff)
• trunk/clustr/clustr.cpp (modified) (4 diffs)
• trunk/clustr/clustr.h (modified) (2 diffs)

trunk/clustr/README

@@ -63 +63 @@
-Bugs
-----
-
+
+
+
+
+
+
+
+
+
-
-License
-
+---
-
-Copyright (c) 2007-2008 Yahoo! Inc.

trunk/clustr/clustr.cpp

@@ -21 +21 @@
-#include <stdexcept>
-#include <cmath>
+#include <algorithm>
-
-#include <unistd.h> 
@@ -79 +80 @@
-}
-
+bool compare_polygon_sizes (const Polygon &a, const Polygon &b) {
+    return a.size() < b.size();
+}
+
+void attach_interior_rings (vector<Polygon> &input, vector<Polygon> &output, bool verbose = false) {
+    unsigned int count = 0;
+
+    /* First, sort the polygons by area. This guarantees that smaller polygons
+     * will wind up inside larger polygons. */
+    sort(input.begin(), input.end(), compare_polygon_sizes);
+
+    for (vector<Polygon>::iterator it = input.begin(); it != input.end(); it++) {
+        bool is_interior_ring = false;
+
+        for (vector<Polygon>::iterator comp = it + 1; comp != input.end(); comp++) {
+            /* check if the first point in the first ring of *it is inside the outer ring
+             * of *comp. If it is, then we assume that the entire polygon *it is actually
+             * inside *comp.
+             *
+             * Note that *comp needs to be a simple polygon -- it *should* be but sometimes
+             * the polygons that come out of the alpha shape self-intersect at a point.
+             * Not sure what to do about this. */
+            if ((*comp)[0].is_simple() && (*comp)[0].encloses((*it)[0][0])) {
+                for (Polygon::iterator ring = it->begin(); ring != it->end(); ring++) {
+                    // this is actually going to get double-interior rings backwards,
+                    // but fixing that means making the logic in
+                    // Polygon::push_back a lot more sophisticated...
+                    comp->push_back(*ring); 
+                }
+                is_interior_ring = true;
+                count++;
+                break;
+            }
+        }
+
+        if (!is_interior_ring)
+            output.push_back(*it);
+    }
+
+    if (verbose && count)
+        cerr << count << " interior rings attached." << endl;
+}
+
-void construct_alpha_shape (Config &config, Shapefile &shape,
-                            vector<Point> &pts, string text)
@@ -84 +128 @@
-    coord_type alpha = config.alpha;
-    Mesh mesh(pts.begin(), pts.end(), alpha);
+    vector<Polygon> polygons, output;
-
-    if (alpha == 0) {
@@ -96 +141 @@
-              " component(s) found for alpha value " << alpha << "." << endl;
-
-
-
+
-        Polygon poly;
-
-
-
-
-
+
+
+
+
+
+
+
+
+
-    }
-}

trunk/clustr/clustr.h

@@ -17 +17 @@
-#define CLUSTR_H
-
-1
+2
-#define AUTHOR      "Schuyler Erle <schuyler@nocat.net>"
-#define COPYRIGHT   "(c) 2007-2008 Yahoo!, Inc."
@@ -174 +174 @@
-        iterator begin (void) { return vertices_begin(); };
-        iterator end (void) { return vertices_end(); };
+        bool encloses (const Point &p) { bounded_side(p) == CGAL::ON_BOUNDED_SIDE; };
-    };
-