grid finding

gistfile1.js

    //multiplicative range to keep neighbours beyond nearest neighbour
    var rangeSensitivity = Math.sqrt(1.8); //a bit less than sqrt(2), basically a magic number

    //main function  
    GridThing.doMap = function(collection){
        var graph = new Graph();
        
        //unimportant construction of points
        buildGrid(graph);
        
        //actual algorithm
        connectPoints(graph);
        clearSmallCycles(graph);
        
        return graph;
    }
    
    function connectPoints(graph){
        var it = graph.vertices.iterator();
        while(it.hasNext()){
            var pt = it.next();
            var it2 = graph.vertices.iterator();
            var bestDist = 99999999;
            var inRange = []; 

            // This is an easy but very inefficient implementation. 
            // Recommend building a k-nearest neighours structure for k=4 
            // to retrieve the top candididates for each point quickly
            // Should also ideally have some special cases to always include two nearest neighbours
            // To avoid degree 1 vertices
            while(it2.hasNext()){
                var candidate = it2.next();
                var dist = candidate.distance(pt);
                
                if(dist == 0) continue;

                if(dist < bestDist*rangeSensitivity){
                    inRange.push(candidate);
                }

                if(dist < bestDist){
                    bestDist = dist;
                    clearCandidates(pt, inRange, bestDist);
                }
            }

            for(var i=0; i<inRange.length; ++i){
                graph.addEdge(pt, inRange[i]);
            }
        }
    }

    function clearCandidates(pt, inRange, bestDist){
        for(var i=inRange.length-1; i>=0; --i){
            var oldCandidate = inRange[i];
            if(oldCandidate.distance(pt) >= bestDist*rangeSensitivity){
                inRange.splice(i,1);
            }
        }
    }

    function clearSmallCycles(graph){
        var it = graph.vertices.iterator();
        while(it.hasNext()){
            var pt = it.next();
            if(pt.edges.length > 2){
                DFSForSmallCycle(graph, pt, pt, 1);
            }
        }
    }

    function DFSForSmallCycle(graph, pt, target, depth){
        var it = pt.edges.iterator();
        while(it.hasNext()){
            var edge = it.next();
            var otherPt = edge.getOtherEnd(pt);
            if(otherPt === target){
                if(depth == 3){
                    return edge;
                }
            }else if(depth < 3){
                var result = DFSForSmallCycle(graph, otherPt, target, depth + 1);
                if(result){
                    //We found a 3-cycle, delete the longest edge
                    if(result.length < edge.length){
                        result = edge;
                    }
                    if(depth == 1){
                        graph.removeEdge(result);
                    }
                    return result;
                }
            }
        }
        return false;
    }