Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
grid finding
//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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.