Skip to content

Instantly share code, notes, and snippets.

@mparke
Last active December 18, 2015 22:38
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mparke/5855348 to your computer and use it in GitHub Desktop.
Save mparke/5855348 to your computer and use it in GitHub Desktop.
Matrix find function intended for use with pixel positions
//searches the matrix for x and y pixel position using binary search
function find(x, y){
var rowData = binarySearch(mx, 0, mx.length - 1, 'y', this.ySize, y);
var colData = binarySearch(rowData.x, 0, rowData.x.length - 1, 'x', this.xSize, x);
return colData;
}
function binarySearch(arr, start, stop, bottomBoundKey, size, val){
var midpoint, data, midBottomBound, midTopBound;
if(stop < start){
return null;
}else{
midpoint = midpoint(start, stop);
data = arr[midpoint];
midBottomBound = data[bottomBoundKey];
midTopBound = midBottomBound + size;
if(val < midBottomBound){
//search bottom half
return binarySearch(arr, start, midpoint, bottomBoundKey, size, val);
}else if(val > midTopBound){
//search top half
return binarySearch(arr, midpoint, stop, bottomBoundKey, size, val);
}else{
//found
return data;
}
}
}
function midpoint(start, stop){
return Math.floor((start + stop) / 2);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment