RubyGems - abscondment-rubyvor - Versions diffs - 0.1.2 - Mend

abscondment-rubyvor 0.1.2

This diff represents the content of publicly available package versions that have been released to one of the supported registries. The information contained in this diff is provided for informational purposes only and reflects changes between package versions as they appear in their respective public registries.

Files changed (31) hide show

data/History.txt +56 -0
data/Manifest.txt +30 -0
data/README.txt +76 -0
data/Rakefile +35 -0
data/ext/Doc +30 -0
data/ext/edgelist.c +204 -0
data/ext/extconf.rb +3 -0
data/ext/geometry.c +219 -0
data/ext/heap.c +118 -0
data/ext/memory.c +118 -0
data/ext/output.c +251 -0
data/ext/rb_cComputation.c +369 -0
data/ext/rb_cPoint.c +35 -0
data/ext/rb_cPriorityQueue.c +121 -0
data/ext/ruby_vor_c.c +115 -0
data/ext/ruby_vor_c.h +28 -0
data/ext/vdefs.h +150 -0
data/ext/voronoi.c +271 -0
data/lib/ruby_vor.rb +16 -0
data/lib/ruby_vor/computation.rb +137 -0
data/lib/ruby_vor/geo_ruby_extensions.rb +15 -0
data/lib/ruby_vor/point.rb +32 -0
data/lib/ruby_vor/priority_queue.rb +84 -0
data/lib/ruby_vor/version.rb +3 -0
data/lib/ruby_vor/visualizer.rb +218 -0
data/rubyvor.gemspec +36 -0
data/test/test_computation.rb +354 -0
data/test/test_point.rb +100 -0
data/test/test_priority_queue.rb +129 -0
data/test/test_voronoi_interface.rb +161 -0
metadata +99 -0

data/History.txt ADDED

@@ -0,0 +1,56 @@
+=== 0.1.2 / 2009-04-24
+* Compilation fixes for OSX. Thanks to jpemberthy and febuiles!
+=== 0.1.1 / 2009-01-15
+* LibXML require conflict fix.
+=== 0.1.0 / 2009-01-13
+* Configurable handling of "no neighbors" case.
+* Tests for "no neighbors" case.
+=== 0.0.9 / 2009-01-01
+Happy New Year!
+* New speed improvements.
+* Additional visualization tweaks.
+* More tests.
+=== 0.0.8 / 2008-12-23
+* Several C warning fixes (more ISO C compliance unused variables, etc)
+* Moved minimum_spanning_tree computation into C, yielding large speed gain.
+* Basic SVG visualization.
+=== 0.0.7 / 2008-12-12
+* Bugfix: there are cases where performing a Delaunay triangulation on a set of points will not yield a complete nearest neighbor graph. This causes computation of the minimum spanning tree and clustering to fail for these nodes (they always appear as disconnected from the main graph).
+* To fix this, the nn_graph function now treats any point that is excluded from Delaunay triangulation as having *all* other points as nearest neighbors. This is a naive approach, but is a good fix while a more efficient solution is considered.
+=== 0.0.6 / 2008-12-11
+* Implementation of cluster_by_size to partition points into N clusters.
+=== 0.0.5 / 2008-12-10
+* Beginnings of clustering and useful graph algorithms.
+* Some refactoring of C methods.
+=== 0.0.4 / 2008-12-04
+* Fixed 64-bit segfaults due to improper definition of the myrealloc() function.
+=== 0.0.3 / 2008-12-03
+* Fixed a segfault by using rb_ary_push instead of direct pointer manipulation. Much simpler.
+=== 0.0.2 / 2008-12-03
+* Computations succeed on a naive Point class, returning raw values for the associated Voronoi Diagram and Delaunay triangulation.
+=== 0.0.1 / 2008-12-01
+* Initial release. Nothing works.

data/Manifest.txt ADDED

@@ -0,0 +1,30 @@
+History.txt
+Manifest.txt
+README.txt
+Rakefile
+ext/Doc
+ext/edgelist.c
+ext/extconf.rb
+ext/geometry.c
+ext/heap.c
+ext/memory.c
+ext/output.c
+ext/rb_cComputation.c
+ext/rb_cPoint.c
+ext/rb_cPriorityQueue.c
+ext/ruby_vor_c.c
+ext/ruby_vor_c.h
+ext/vdefs.h
+ext/voronoi.c
+lib/ruby_vor.rb
+lib/ruby_vor/computation.rb
+lib/ruby_vor/geo_ruby_extensions.rb
+lib/ruby_vor/point.rb
+lib/ruby_vor/priority_queue.rb
+lib/ruby_vor/version.rb
+lib/ruby_vor/visualizer.rb
+rubyvor.gemspec
+test/test_computation.rb
+test/test_point.rb
+test/test_priority_queue.rb
+test/test_voronoi_interface.rb

data/README.txt ADDED

@@ -0,0 +1,76 @@
+= rubyvor
+Efficient Voronoi diagrams and Delaunay trianglation for Ruby
+== Description
+RubyVor provides efficient computation of Voronoi diagrams and
+Delaunay triangulation for a set of Ruby points. It is intended to
+function as a complemenet to GeoRuby. These structures can be used to
+compute a nearest-neighbor graph for a set of points. This graph can
+in turn be used for proximity-based clustering of the input points.
+== Usage:
+require 'lib/ruby_vor'
+require 'pp'
+points = [
+  RubyVor::Point.new(120, 290),
+  RubyVor::Point.new(110, 120),
+  RubyVor::Point.new(160, 90.2),
+  RubyVor::Point.new(3.14159265, 3.14159265)
+]
+# Compute the diagram & triangulation
+comp = RubyVor::VDDT::Computation.from_points(points)
+puts "The nearest-neighbor graph:"
+pp comp.nn_graph
+puts "\nThe minimum-spanning tree:"
+pp comp.minimum_spanning_tree
+#
+# Visualize these things as SVGs
+#
+# Just the triangulation
+RubyVor::Visualizer.make_svg(comp, :name => 'tri.svg')
+# Just the MST
+RubyVor::Visualizer.make_svg(comp, :name => 'mst.svg', :triangulation => false, :mst => true)
+# Voronoi diagram and the triangulation
+RubyVor::Visualizer.make_svg(comp, :name => 'dia.svg', :voronoi_diagram => true)
+== LICENSE:
+Original public-domain C code (by Steven Fortune; http://ect.bell-labs.com/who/sjf/) and
+memory-management fixes for said C code (by Derek Bradley; http://www.derekbradley.ca)
+used (and released under the MIT-LICENSE) with permission.
+(The MIT License)
+Copyright (c) 2008 Brendan Ribera <brendan.ribera+rubyvor@gmail.com>
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.

data/Rakefile ADDED

@@ -0,0 +1,35 @@
+# -*- ruby -*-
+require 'rubygems'
+require 'hoe'
+require './lib/ruby_vor/version.rb'
+EXT = "ext/voronoi_interface.#{Hoe::DLEXT}"
+Hoe.new('rubyvor', RubyVor::VERSION) do |p|
+  p.developer('Brendan Ribera', 'brendan.ribera+rubyvor@gmail.com')
+  p.url = 'http://github.com/bribera/rubyvor'
+  # C extension goodness
+  p.spec_extras[:extensions] = "ext/extconf.rb"
+  p.clean_globs << EXT << 'ext/*.o' << 'ext/Makefile'
+end
+desc "Compile extensions"
+task :compile => EXT
+task :test => :compile
+file EXT => ['ext/extconf.rb', 'ext/ruby_vor_c.c'] do
+  Dir.chdir 'ext' do
+    ruby 'extconf.rb'
+    sh 'make'
+  end
+end
+desc "Prepare for github upload"
+task :github do
+  system "git ls-files | egrep -v \"\\.gitignore\" > Manifest.txt"
+  system "rake debug_gem | egrep -v \"^\\(in\" > rubyvor.gemspec"
+end
+task :gem => :github

data/ext/Doc ADDED

@@ -0,0 +1,30 @@
+voronoi - compute Voronoi diagram or Delaunay triangulation
+SYNOPSIS
+	voronoi [-s -t] <pointfile >outputfile
+Voronoi reads the standard input for a set of points in the plane and writes either
+the Voronoi diagram or the Delaunay triangulation to the standard output.
+Each input line should consist of two real numbers, separated by white space.
+If option
+	-t
+is present, the Delaunay triangulation is produced.
+Each output line is a triple
+	i j k
+which are the indices of the three points in a Delaunay triangle. Points are
+numbered starting at 0. If this option is not present, the
+Voronoi diagram is produced.  There are four output record types.
+	s a b
+indicates that an input point at coordinates
+	l a b c
+indicates a line with equation ax + by = c.
+	v a b
+indicates a vertex at  a b.
+	e l v1 v2
+indicates a Voronoi segment which is a subsegment of line number l;
+with endpoints numbered v1 and v2.  If v1 or v2 is -1, the line
+extends to infinity.
+AUTHOR
+Steve J. Fortune (1987) A Sweepline Algorithm for Voronoi Diagrams,
+Algorithmica 2, 153-174.

data/ext/edgelist.c ADDED

@@ -0,0 +1,204 @@
+/*** EDGELIST.C ***/
+#include "vdefs.h"
+static int ELhashsize ;
+static Halfedge * ELleftend, * ELrightend, ** ELhash ;
+static Freelist hfl ;
+static int ntry, totalsearch ;
+void
+ELinitialize(void)
+{
+    int i ;
+    freeinit(&hfl, sizeof(Halfedge)) ;
+    ELhashsize = 2 * rubyvorState.sqrt_nsites ;
+    ELhash = (Halfedge **)myalloc( sizeof(*ELhash) * ELhashsize) ;
+    for (i = 0  ; i < ELhashsize  ; i++)
+    {
+        ELhash[i] = (Halfedge *)NULL ;
+    }
+    ELleftend = HEcreate((Edge *)NULL, 0) ;
+    ELrightend = HEcreate((Edge *)NULL, 0) ;
+    ELleftend->ELleft = (Halfedge *)NULL ;
+    ELleftend->ELright = ELrightend ;
+    ELrightend->ELleft = ELleftend ;
+    ELrightend->ELright = (Halfedge *)NULL ;
+    ELhash[0] = ELleftend ;
+    ELhash[ELhashsize-1] = ELrightend ;
+}
+Halfedge *
+HEcreate(Edge * e, int pm)
+{
+    Halfedge * answer ;
+    answer = (Halfedge *)getfree(&hfl) ;
+    answer->ELedge = e ;
+    answer->ELpm = pm ;
+    answer->PQnext = (Halfedge *)NULL ;
+    answer->vertex = (Site *)NULL ;
+    answer->ELrefcnt = 0 ;
+    return (answer) ;
+}
+void
+ELinsert(Halfedge * lb, Halfedge * new)
+{
+    new->ELleft = lb ;
+    new->ELright = lb->ELright ;
+    (lb->ELright)->ELleft = new ;
+    lb->ELright = new ;
+}
+/* Get entry from hash table, pruning any deleted nodes */
+Halfedge *
+ELgethash(int b)
+{
+    Halfedge * he ;
+    if ((b < 0) || (b >= ELhashsize))
+    {
+        return ((Halfedge *)NULL) ;
+    }
+    he = ELhash[b] ;
+    if ((he == (Halfedge *)NULL) || (he->ELedge != (Edge *)DELETED))
+    {
+        return (he) ;
+    }
+    /* Hash table points to deleted half edge.  Patch as necessary. */
+    ELhash[b] = (Halfedge *)NULL ;
+    if ((--(he->ELrefcnt)) == 0)
+    {
+        makefree((Freenode *)he, (Freelist *)&hfl) ;
+    }
+    return ((Halfedge *)NULL) ;
+}
+Halfedge *
+ELleftbnd(Point * p)
+{
+    int i, bucket ;
+    Halfedge * he ;
+    /* Use hash table to get close to desired halfedge */
+    bucket = (p->x - rubyvorState.xmin) / rubyvorState.deltax * ELhashsize ;
+    if (bucket < 0)
+    {
+        bucket = 0 ;
+    }
+    if (bucket >= ELhashsize)
+    {
+        bucket = ELhashsize - 1 ;
+    }
+    he = ELgethash(bucket) ;
+    if  (he == (Halfedge *)NULL)
+    {
+        for (i = 1 ; 1 ; i++)
+        {
+            if ((he = ELgethash(bucket-i)) != (Halfedge *)NULL)
+            {
+                break ;
+            }
+            if ((he = ELgethash(bucket+i)) != (Halfedge *)NULL)
+            {
+                break ;
+            }
+        }
+        totalsearch += i ;
+    }
+    ntry++ ;
+    /* Now search linear list of halfedges for the corect one */
+    if (he == ELleftend || (he != ELrightend && right_of(he,p)))
+    {
+        do  {
+            he = he->ELright ;
+        } while (he != ELrightend && right_of(he,p)) ;
+        he = he->ELleft ;
+    }
+    else
+    {
+        do  {
+            he = he->ELleft ;
+        } while (he != ELleftend && !right_of(he,p)) ;
+    }
+    /*** Update hash table and reference counts ***/
+    if ((bucket > 0) && (bucket < ELhashsize-1))
+    {
+        if (ELhash[bucket] != (Halfedge *)NULL)
+        {
+            (ELhash[bucket]->ELrefcnt)-- ;
+        }
+        ELhash[bucket] = he ;
+        (ELhash[bucket]->ELrefcnt)++ ;
+    }
+    return (he) ;
+}
+/*** This delete routine can't reclaim node, since pointers from hash
+ : table may be present.
+ ***/
+void
+ELdelete(Halfedge * he)
+{
+    (he->ELleft)->ELright = he->ELright ;
+    (he->ELright)->ELleft = he->ELleft ;
+    he->ELedge = (Edge *)DELETED ;
+}
+Halfedge *
+ELright(Halfedge * he)
+{
+    return (he->ELright) ;
+}
+Halfedge *
+ELleft(Halfedge * he)
+{
+    return (he->ELleft) ;
+}
+Site *
+leftreg(Halfedge * he)
+{
+    if (he->ELedge == (Edge *)NULL)
+    {
+        return(rubyvorState.bottomsite) ;
+    }
+    return (he->ELpm == le ? he->ELedge->reg[le] :
+            he->ELedge->reg[re]) ;
+}
+Site *
+rightreg(Halfedge * he)
+{
+    if (he->ELedge == (Edge *)NULL)
+    {
+        return(rubyvorState.bottomsite) ;
+    }
+    return (he->ELpm == le ? he->ELedge->reg[re] :
+            he->ELedge->reg[le]) ;
+}
+/*
+ * Semi-hacky way to access these static variables. Placing them inside rubyvorState
+ * causes pointer issues that I don't want to debug, and they're only accessed briefly
+ * inside of voronoi.c.  Since we're just doing pointer comparison there, this is an
+ * acceptable compromise.
+ */
+Halfedge *
+getELleftend(void)
+{
+    return(ELleftend);
+}
+Halfedge *
+getELrightend(void)
+{
+    return(ELrightend);
+}

data/ext/extconf.rb ADDED

@@ -0,0 +1,3 @@
+require 'mkmf'
+dir_config('ruby_vor_c')
+create_makefile('ruby_vor_c')

data/ext/geometry.c ADDED

@@ -0,0 +1,219 @@
+/*** GEOMETRY.C ***/
+#include <math.h>
+#include "vdefs.h"
+static Freelist efl;
+void
+geominit(void)
+{
+    freeinit(&efl, sizeof(Edge)) ;
+    rubyvorState.nvertices = rubyvorState.nedges = 0 ;
+    rubyvorState.sqrt_nsites = sqrt(rubyvorState.nsites+4) ;
+    rubyvorState.deltay = rubyvorState.ymax - rubyvorState.ymin ;
+    rubyvorState.deltax = rubyvorState.xmax - rubyvorState.xmin ;
+}
+Edge *
+bisect(Site * s1, Site * s2)
+{
+    float dx, dy, adx, ady ;
+    Edge * newedge ;
+    newedge = (Edge *)getfree(&efl) ;
+    newedge->reg[0] = s1 ;
+    newedge->reg[1] = s2 ;
+    ref(s1) ;
+    ref(s2) ;
+    newedge->ep[0] = newedge->ep[1] = (Site *)NULL ;
+    dx = s2->coord.x - s1->coord.x ;
+    dy = s2->coord.y - s1->coord.y ;
+    adx = dx>0 ? dx : -dx ;
+    ady = dy>0 ? dy : -dy ;
+    newedge->c = s1->coord.x * dx + s1->coord.y * dy + (dx*dx +
+dy*dy) * 0.5 ;
+    if (adx > ady)
+    {
+        newedge->a = 1.0 ;
+        newedge->b = dy/dx ;
+        newedge->c /= dx ;
+    }
+    else
+    {
+        newedge->b = 1.0 ;
+        newedge->a = dx/dy ;
+        newedge->c /= dy ;
+    }
+    newedge->edgenbr = rubyvorState.nedges ;
+    out_bisector(newedge) ;
+    rubyvorState.nedges++ ;
+    return (newedge) ;
+}
+Site *
+intersect(Halfedge * el1, Halfedge * el2)
+{
+    Edge * e1, * e2, * e ;
+    Halfedge * el ;
+    float d, xint, yint ;
+    int right_of_site ;
+    Site * v ;
+    e1 = el1->ELedge ;
+    e2 = el2->ELedge ;
+    if ((e1 == (Edge*)NULL) || (e2 == (Edge*)NULL))
+    {
+        return ((Site *)NULL) ;
+    }
+    if (e1->reg[1] == e2->reg[1])
+    {
+        return ((Site *)NULL) ;
+    }
+    d = (e1->a * e2->b) - (e1->b * e2->a) ;
+    if ((-1.0e-10 < d) && (d < 1.0e-10))
+    {
+        return ((Site *)NULL) ;
+    }
+    xint = (e1->c * e2->b - e2->c * e1->b) / d ;
+    yint = (e2->c * e1->a - e1->c * e2->a) / d ;
+    if ((e1->reg[1]->coord.y < e2->reg[1]->coord.y) ||
+        (e1->reg[1]->coord.y == e2->reg[1]->coord.y &&
+        e1->reg[1]->coord.x < e2->reg[1]->coord.x))
+    {
+        el = el1 ;
+        e = e1 ;
+    }
+    else
+    {
+        el = el2 ;
+        e = e2 ;
+    }
+    right_of_site = (xint >= e->reg[1]->coord.x) ;
+    if ((right_of_site && (el->ELpm == le)) ||
+       (!right_of_site && (el->ELpm == re)))
+    {
+        return ((Site *)NULL) ;
+    }
+    v = (Site *)getfree(&(rubyvorState.sfl)) ;
+    v->refcnt = 0 ;
+    v->coord.x = xint ;
+    v->coord.y = yint ;
+    return (v) ;
+}
+/*** returns 1 if p is to right of halfedge e ***/
+int
+right_of(Halfedge * el, Point * p)
+{
+    Edge * e ;
+    Site * topsite ;
+    int right_of_site, above, fast ;
+    float dxp, dyp, dxs, t1, t2, t3, yl ;
+    e = el->ELedge ;
+    topsite = e->reg[1] ;
+    right_of_site = (p->x > topsite->coord.x) ;
+    if (right_of_site && (el->ELpm == le))
+    {
+        return (1) ;
+    }
+    if(!right_of_site && (el->ELpm == re))
+    {
+        return (0) ;
+    }
+    if (e->a == 1.0)
+    {
+        dyp = p->y - topsite->coord.y ;
+        dxp = p->x - topsite->coord.x ;
+        fast = 0 ;
+        if ((!right_of_site & (e->b < 0.0)) ||
+         (right_of_site & (e->b >= 0.0)))
+        {
+            fast = above = (dyp >= e->b*dxp) ;
+        }
+        else
+        {
+            above = ((p->x + p->y * e->b) > (e->c)) ;
+            if (e->b < 0.0)
+            {
+                above = !above ;
+            }
+            if (!above)
+            {
+                fast = 1 ;
+            }
+        }
+        if (!fast)
+        {
+            dxs = topsite->coord.x - (e->reg[0])->coord.x ;
+            above = (e->b * (dxp*dxp - dyp*dyp))
+                    <
+                    (dxs * dyp * (1.0 + 2.0 * dxp /
+                    dxs + e->b * e->b)) ;
+            if (e->b < 0.0)
+            {
+                above = !above ;
+            }
+        }
+    }
+    else  /*** e->b == 1.0 ***/
+    {
+        yl = e->c - e->a * p->x ;
+        t1 = p->y - yl ;
+        t2 = p->x - topsite->coord.x ;
+        t3 = yl - topsite->coord.y ;
+        above = ((t1*t1) > ((t2 * t2) + (t3 * t3))) ;
+    }
+    return (el->ELpm == le ? above : !above) ;
+}
+void
+endpoint(Edge * e, int lr, Site * s)
+{
+    e->ep[lr] = s ;
+    ref(s) ;
+    if (e->ep[re-lr] == (Site *)NULL)
+    {
+        return ;
+    }
+    out_ep(e) ;
+    deref(e->reg[le]) ;
+    deref(e->reg[re]) ;
+    makefree((Freenode *)e, (Freelist *) &efl) ;
+}
+float
+dist(Site * s, Site * t)
+{
+    float dx,dy ;
+    dx = s->coord.x - t->coord.x ;
+    dy = s->coord.y - t->coord.y ;
+    return (sqrt(dx*dx + dy*dy)) ;
+}
+void
+makevertex(Site * v)
+{
+    v->sitenbr = rubyvorState.nvertices++ ;
+    out_vertex(v) ;
+}
+void
+deref(Site * v)
+{
+    if (--(v->refcnt) == 0 )
+    {
+        makefree((Freenode *)v, (Freelist *)&(rubyvorState.sfl)) ;
+    }
+}
+void
+ref(Site * v)
+{
+    ++(v->refcnt) ;
+}