I have an html5 canvas providing a view into a world with a bunch of points. The user can click and drag around to pan the view.

I'd like to know if my method here is horribly inefficient and could possibly be optimized another order of magnitude. It's currently a little laggy for me with a million points.

jsfiddle: https://jsfiddle.net/3oc1mnu6/2/

HTML:

<canvas id="myCanvas" width="960" height="540" style="border:1px solid #000000;"></canvas>

Javascript:

//world dimensions
var worldWidth = 4000;
var worldHeight = 3000;

//mouse down bool
var mouseDown = 0;

var canvas = document.getElementById("myCanvas");
var context = canvas.getContext("2d");

//point class
function point(x, y){
  this.x = x;
  this.y = y;
}

//some key points
var camera = new point(1000, 1000);
var cameraLocationWhenMouseClicked = new point();
var mouseDownLocation = new point();

//the mass of points
var numPoints = 1000000;
var points = [];

for (var i = 0; i < numPoints; i++){
  points.push(new point(Math.random() * worldWidth, Math.random() * worldHeight));
}

//mouse event handlers
canvas.addEventListener("mousedown", mouseDownEventHandler);
canvas.addEventListener("mousemove", mouseMoveEventHandler);
canvas.addEventListener("mouseup", mouseUpEventHandler);

//on mouse down
function mouseDownEventHandler(e){
  mouseDown = 1;

  //update mouseDownLocation
  mouseDownLocation.x = e.offsetX;
  mouseDownLocation.y = e.offsetY;

  //store where the camera was when mouse down occurred
  cameraLocationWhenMouseClicked.x = camera.x;
  cameraLocationWhenMouseClicked.y = camera.y;
}

//on mouse move
function mouseMoveEventHandler(e){
  //if mouse is down
  if (mouseDown == 1){
    //adjust camera location
    camera.x = cameraLocationWhenMouseClicked.x + (mouseDownLocation.x - e.offsetX);
    camera.y = cameraLocationWhenMouseClicked.y + (mouseDownLocation.y - e.offsetY);
  }
}

//on mouse up
function mouseUpEventHandler(){
  mouseDown = 0;
}

function drawScreen(){
  //draw canvas
  context.fillStyle = "white";
  context.fillRect(0, 0, canvas.width, canvas.height);

  //draw points
  context.fillStyle = "black";
  for (var i = 0; i < points.length; i++){
    //only draw if in view
    if((camera.x < points[i].x)&&(points[i].x < camera.x + canvas.width)&&(camera.y < points[i].y)&&(points[i].y < camera.y + canvas.height)){
      context.fillRect(points[i].x - camera.x, points[i].y - camera.y, 1, 1);
    }
  }
}

window.setInterval(drawScreen);

You are currently looping through every point to see if it is visible, this could probably benefit from a space partition. For instance, instead of having, a single array with all the points spread over the entire area, you would have a series of smaller arrays representing smaller areas. You would then check which of these smaller areas is visible, and loop through their points if visible. Look into space partitions such as quadtree.

You could have a 2-d array. Where each element of the array is a series of points contained in area (x,y)-(x+w, y+h), where x and y are array indicies but also associated with locations in space. With this method you could easily find if an entire group of points is likely to be visible. Space Partitioning: method to make fewer spacial comparisons given the camera only looks at  a specific area of space. 

On 11/18/2017 at 10:14 AM, h8CplusplusGuru said:

You are currently looping through every point to see if it is visible, this could probably benefit from a space partition. For instance, instead of having, a single array with all the points spread over the entire area, you would have a series of smaller arrays representing smaller areas. You would then check which of these smaller areas is visible, and loop through their points if visible. Look into space partitions such as quadtree.

You could have a 2-d array. Where each element of the array is a series of points contained in area (x,y)-(x+w, y+h), where x and y are array indicies but also associated with locations in space. With this method you could easily find if an entire group of points is likely to be visible. Space Partitioning: method to make fewer spacial comparisons given the camera only looks at  a specific area of space. 

This immediately strikes me as feasible and very interesting. Thank you for the suggestion. It's definitely something I will try to implement. I have an idea involving a pair of binary searches (one per dimension)