// Test of closest pair algorithms // David Eppstein, UC Irvine, 19 Apr 1997 // // Conga line closest pair algorithm // // Keeps a partition of the points into subsets, with a graph // for each subset computed as described in my paper. Each graph is initially // computed using a nearest-neighbor insertion process alternating between // points in the subset and points in the whole database. // // Constructor takes as arg number of subsets to make; if omitted, uses // ceil(log_2(n)). // // Total space: 42n + O(k) bytes (where k=number of subsets, normally O(log n)). // Time per insertion: O(n log(n/k)) amortized // Time per deletion: O(n log(n/k)) expected, O(nk log(n/k)) worst case amortized // // Time per closest pair: O(n). #include "ClosestPairs.h" #include "SortedArray.h" // how many subsets can we have? need to leave one for scratch, one for inactive #define MaxCongaSubsets 65534L class CongaLine : public ClosestPairs { Distance & dist; // how to compare two points unsigned long max_points; typedef unsigned short CongaSubset; SortedArray subset_sizes; // list of subset sizes CongaSubset how_many_subsets; typedef struct { point in, out; double d; CongaSubset s; } CongaEdge; CongaEdge * edges; // list of all edges in graph unsigned long how_many_edges; CongaSubset * subsets; // which subset is each point in? point * scratch; void FixWhat(point); // update subset_sizes prior to removing pt void AddEdge(point, point, double, CongaSubset); // add an edge to the graph void RemoveEdge(unsigned long); // remove edge w/given index void MoveToSubset(point, CongaSubset); // move point to new subset void CleanAllGraphs(); // remove non-inter-subset edges unsigned long NeighborInList(point pt, point * ptlist, unsigned long listlen, double & d); // return dist & list pos of nearest nbr in list to pt void FindSubsetEdges(CongaSubset); // recompute edges in subset void MergeSubsets(CongaSubset,CongaSubset); // combine subsets CongaSubset FindFreeSubset(); // where can I put this newly inserted pt? void MadeNewSubset(CongaSubset, unsigned long); // make edges etc public: ~CongaLine(); CongaLine(long np, long mp, Distance & d, long how_many_subs = 0); void operator += (point); void operator -= (point); double operator () (point & a, point & b); void UpdatePoint(point); void UpdateDistance(point,point); };