lib/interpolation.rb in xrvg-0.0.2 vs lib/interpolation.rb in xrvg-0.0.3

@@ -1,10 +1,11 @@
 # Interpolation file.
 #
 # See
 # - +Interpolation+
 # - +Interpolator+
+# - +InterpolatorQuad+
 
 require 'utils'
 require 'attributable'
 
 # Interpolation module
@@ -31,23 +32,23 @@
   # from an input between 0.0 and 1.0, returns linear interpolated value
   #
   # interpolate uses + and * scalar operators on interpolation values
   def interpolate( dindex )
     result = nil
-    pvalue, pindex = self.samplelist[0..1]
-    self.samplelist.foreach do |value, index|
+    pindex, pvalue = self.samplelist[0..1]
+    self.samplelist.foreach do |index, value|
       if dindex <= index
 	if dindex == index
 	  return value
 	end
 	result = pvalue + ((value + pvalue * (-1.0) ) * ((dindex - pindex) / (index - pindex )))
 	break
       end
       pvalue, pindex = value, index
     end
     if not result
-      result = self.samplelist[-2]
+      result = self.samplelist[-1]
     end
     return result
   end
 end
 
@@ -56,6 +57,102 @@
 # Simply instanciated module in a class
 class Interpolator
   include Attributable
   attribute :samplelist
   include Interpolation
+end
+
+class QuadRange
+
+  def initialize( limit, quadleft, quadright, range=nil )
+    @limit     = limit
+    @quadleft  = quadleft
+    @quadright = quadright
+    @range     = range
+  end
+
+  def limit
+    return @limit
+  end
+
+  def range( index )
+    if @limit
+      if index < @limit
+	return @quadleft.range( index )
+      else
+	return @quadright.range( index )
+      end
+    else
+      return @range
+    end
+  end
+end
+
+# QuadTree class
+# = Intro
+# Optim class to look for predefine ranges for a value. Is actually a binary tree data structure, but used as unlinear space partitioner.
+# = Example
+#  quad = QuadTree.new( [0.0,1.0, 0.2,0.0, 0.6,1.0,  0.8,0.0, 1.0,1.0]  )
+#  quad.range( 0.5 ); #=> [0.2,0.0,0.6,1.0]
+class QuadTree
+
+  def initialize( samplelist ) #:nodoc:
+    quads = []
+    ends  = []
+    samplelist.foreach(2).pairs do |ppair, pair|
+      pindex, pvalue = ppair
+      index, value   = pair
+      quads << QuadRange.new( nil, nil, nil, [pindex, pvalue, index, value] )
+      ends  << index
+    end
+    @root = build_quads( quads, ends )
+  end
+
+  def build_quads( quads, ends ) #:nodoc:
+    newquads = []
+    newends  = []
+    index = 0
+    quads.foreach do |quad1, quad2|
+      newquads << QuadRange.new( ends[2*index], quad1, quad2, nil)
+      newends  << ends[2*index + 1]
+      index += 1
+    end
+    if newquads.size == 1
+      return newquads[0]
+    else
+      return build_quads( newquads, newends )
+    end
+  end
+
+  # utilitary method to retrieve range of index
+  #  QuadTree.new( [0.0,1.0, 0.2,0.0, 0.6,1.0,  0.8,0.0, 1.0,1.0]  ).range( 0.5 ); #=> [0.2,0.0,0.6,1.0]  
+  def range( index )
+    return @root.range( index )
+  end
+end
+  
+# Quad tree interpolator
+# 
+# Use QuadTree to retrieve range of values between linear interpolation.
+#
+# Used in BezierSpline to compute parameter from length.
+class InterpolatorQuad < Interpolator
+
+  def compute_quad #:nodoc:
+    @quad = QuadTree.new( self.samplelist )
+  end
+  
+  # - first use QuadTree range to retrieve range of dindex, 
+  # - then linearly interpolate
+  def interpolate( dindex )
+    if not @quad
+      compute_quad
+    end
+    pindex, pvalue, index, value = @quad.range( dindex )
+    if pindex.fequal?(index)
+      result = value
+    else
+      result = pvalue + ((value + pvalue * (-1.0) ) * ((dindex - pindex) / (index - pindex )))
+    end
+    return result
+  end
 end