Лучше выбрать линию, чем использовать алгоритм Брешенема?

Question

Я рисую строки на холсте HTML и использую менее точный 2d-массив (представляющий блоки размером 10x10 пикселей), в котором я рисую линии с алгоритмом Брешенема для хранения идентификаторов строк, поэтому я могу использовать этот массив для см., какая строка выбрана.

Это работает, но я бы хотел, чтобы он был более точным - не в размере 10x10, который я использую (мне нравится, что мне не нужно просто щелкнуть по строке), но когда я рисую представление этого массив над моей фактической холст, я вижу, что есть много из 10х10 блоков не заполнен, даже если линия пересекает их:

есть ли лучшее решение этой проблемы? Я хочу, чтобы поймать ВСЕ блоки сетки, через которые проходит фактическая линия.

Answer 1

Не видя своего кода, я думаю, что вы сделали ошибку округления при заполнении таблицы поиска с использованием алгоритма Брешенема или вы масштабировали координаты перед запуском алгоритма.

Этот jsFiddle показывает, что я придумал, и квадраты идеально выровнены.

HTML

<canvas id="myCanvas"></canvas> 

CSS

#myCanvas { 
    width: 250px; 
    height: 250px; 
} 

JavaScript

var $canvas = $("#myCanvas"), 
    ctx = $canvas[0].getContext("2d"); 

ctx.canvas.width = $canvas.width(); 
ctx.canvas.height = $canvas.height(); 

function Grid(ctx) { 
    this._ctx = ctx; 
    this._lines = []; 
    this._table = []; 
    this._tableScale = 10; 
    this._createLookupTable(); 
} 
Grid.prototype._createLookupTable = function() { 
    this._table = []; 
    for (var y = 0; y < Math.ceil(ctx.canvas.height/this._tableScale); y++) { 
     this._table[y] = []; 
     for (var x = 0; x < Math.ceil(ctx.canvas.width/this._tableScale); x++) 
      this._table[y][x] = null; 
    } 
}; 
Grid.prototype._updateLookupTable = function(line) { 
    var x0 = line.from[0], 
     y0 = line.from[1], 
     x1 = line.to[0], 
     y1 = line.to[1], 
     dx = Math.abs(x1 - x0), 
     dy = Math.abs(y1 - y0), 
     sx = (x0 < x1) ? 1 : -1, 
     sy = (y0 < y1) ? 1 : -1, 
     err = dx - dy; 
    while(true) { 
     this._table[Math.floor(y0/10)][Math.floor(x0/10)] = line; 
     if ((x0 == x1) && (y0 == y1)) break; 
     var e2 = 2 * err; 
     if (e2 >- dy) { err -= dy; x0 += sx; } 
     if (e2 < dx) { err += dx; y0 += sy; } 
    }  
}; 
Grid.prototype.hitTest = function(x, y) { 
    var ctx = this._ctx, 
     hoverLine = this._table[Math.floor(y/10)][Math.floor(x/10)]; 
    ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height); 
    this._lines.forEach(function(line) { 
     line.draw(ctx, line === hoverLine ? "red" : "black"); 
    }); 
}; 
Grid.prototype.drawLookupTable = function() { 
    ctx.beginPath(); 
    for (var y = 0; y < this._table.length; y++) 
     for (var x = 0; x < this._table[y].length; x++) { 
      if (this._table[y][x]) 
       ctx.rect(x * 10, y * 10, 10, 10); 
     } 
    ctx.strokeStyle = "rgba(0, 0, 0, 0.2)"; 
    ctx.stroke(); 
}; 
Grid.prototype.addLine = function(line) { 
    this._lines.push(line); 
    this._updateLookupTable(line); 
}; 
Grid.prototype.draw = function() { 
    var ctx = this._ctx; 
    ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height); 
    this._lines.forEach(function(line) { 
     line.draw(ctx); 
    }); 
}; 

function Line(x0, y0, x1, y1) { 
    this.from = [ x0, y0 ]; 
    this.to = [ x1, y1]; 
} 
Line.prototype.draw = function(ctx, style) { 
    ctx.beginPath(); 
    ctx.moveTo(this.from[0], this.from[1]); 
    ctx.lineTo(this.to[0], this.to[1]); 
    ctx.strokeStyle = style || "black"; 
    ctx.stroke(); 
}; 

var grid = new Grid(ctx); 
grid.addLine(new Line(80, 10, 240, 75)); 
grid.addLine(new Line(150, 200, 50, 45)); 
grid.addLine(new Line(240, 10, 20, 150)); 
grid.draw(); 
grid.drawLookupTable(); 

$canvas.on("mousemove", function(e) { 
    grid.hitTest(e.offsetX, e.offsetY); 
    grid.drawLookupTable(); 
}); 

Answer 2

Ваш лучший вариант - обработать положение курсора мыши как маленький круг (например, с радиусом 5 пикселей) и проверить, пересекает ли линия с кругом.

Используйте математику, как описано в этом Q&A

JavaScript

простую функцию для обнаружения пересечения будет:

function lineCircleIntersects(x1, y1, x2, y2, cx, cy, cr) { 
    var dx = x2 - x1, 
     dy = y2 - y1, 
     a = dx * dx + dy * dy, 
     b = 2 * (dx * (x1 - cx) + dy * (y1 - cy)), 
     c = cx * cx + cy * cy, 
     bb4ac; 

    c += x1 * x1 + y1 * y1; 
    c -= 2 * (cx * x1 + cy * y1); 
    c -= cr * cr; 
    bb4ac = b * b - 4 * a * c; 

    return bb4ac >= 0; // true: collision, false: no collision 
} 

Посмотреть работу в этом jsFiddle, но учтите, что это функция также вернет true, если курсор находится на наклоне линии снаружи [x1, y1], [x2, y2]. Я оставлю это вам :)

Вы также можете попробовать line-circle-collision library on github, который должен предоставить вам то, что вы хотите.