[Edu-sig] Basic dictionary question

[Scott David Daniels]

Kirby Urner wrote:
> I'm translating a volume 3 cube around in a 3D checkerboard, trying to flag
> all kitty-corner mid-edges (my bridge points), but not flagging border-line
> edges where the connector tabs shouldn't appear -- some large borg-like
> array of icosahedra connected by zig-zag tensed bands (Lanahan's patent
> pending).
> 
> See http://www.4dsolutions.net/satacad/pythonicmath/icosa_in_holder.jpg for
> a picture of a unit cell (the array might contain thousands).
> 
> So the XYZ tuples of interest are indeed highly distinct and in a regular
> grid pattern.  It's just that there're a whole lot of them, and if I could
> find a hash key that'd keep only the unique ones unique and ignore floating
> point fuzz, I'd be set.  Any pairing/doubling would define a bridge point,
> and therefore a green light to render a tab connector.
> 
> I think the key is probably to transform the grid by scaling, such that my
> mid-edge points of interest get expressed using all integer coordinates.
> Even though my actual map is floating point, the isomorphism will work for
> pruning, and the tuples'll be easy to manage (so maybe scratch the decimal
> type idea for now).
> 
> I'll post again when I have more research behind me and either a solution or
> concrete frustration in sight -- not before.
> 
> Kirby

Does something like this work?  The idea is two exact matches on the
discretization and one off-by-one on the third discretization merits
a check.  discrete(point) gives the "integer-ized" coordinates.  There
is some fancy dancing to avoid the distance check (done as the square
just to avoid a few square roots) unless possibly helpful.  It only
tries to solve "near-misses" (skips exact matches) on the theory you
can already get the exact matches from a dictionary.

def clustered(source_of_points, threshold2)
     xy = {}
     xz = {}
     yz = {}
     for point in source_of_points:
         ix, iy, iz = discrete(point)
         xy.setdefault([]).append((iz, point))
         xz.setdefault([]).append((iy, point))
         yz.setdefault([]).append((ix, point))

     for collection in (xy, xz, yz):
         for parts in collection.itervalues():
             if len(parts) > 1:
                 parts.sort()
                 for (da, a), (db, b) in zip(parts, parts[1:]):
                     if 0 <= db - da <= 1:
                         if 0 < dist2(a, b) < threshold2:
                             yield a, b

-- 
-- Scott David Daniels
Scott.Daniels at Acm.Org