Is there a more optimal way to choose lines than the Bresenham algorithm?

Question

Is there a more optimal way to choose lines than the Bresenham algorithm?

In my HTML canvas project, I am currently drawing lines using a 2d-array that represents blocks of 10x10 pixels. I use Bresenham's algorithm to store line-ids in this array so that I can determine which line is selected.

While this method works, I find that it lacks precision. When I overlay a representation of the array on my canvas, I notice that many of the 10x10 blocks are not completely filled even though the line crosses them:

Is there a more accurate solution to ensure that all grid blocks the actual line passes through are captured?

javascript canvas bresenham

Answer 1

Answer №1

It seems like there may have been a mistake in the rounding process when populating the lookup table using the Bresenham algorithm, or perhaps the coordinates were scaled incorrectly before executing the algorithm.

You can view my solution and see that the squares are perfectly aligned in this jsFiddle.

HTML

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

CSS

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

JavaScript

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

// Remaining JavaScript code for grid creation, line rendering, and event handling...

Answer 2

It seems like there may have been a mistake in the rounding process when populating the lookup table using the Bresenham algorithm, or perhaps the coordinates were scaled incorrectly before executing the algorithm.

You can view my solution and see that the squares are perfectly aligned in this jsFiddle.

HTML

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

CSS

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

JavaScript

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

// Remaining JavaScript code for grid creation, line rendering, and event handling...

Answer 3

Answer №2

Consider the mouse cursor position as a miniature circle, such as one with a 5px radius, and determine if it intersects with the line.

Refer to this Q&A for the mathematical explanation.

JavaScript

A basic function to identify intersection:

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
}

View it in action on this jsFiddle, but be aware that this function may also indicate a collision if the cursor lies on the line's slope outside [x1, y1], [x2, y2]. This decision is yours to make :)

You can explore the line-circle-collision library on GitHub for further assistance.

Answer 4

Consider the mouse cursor position as a miniature circle, such as one with a 5px radius, and determine if it intersects with the line.

Refer to this Q&A for the mathematical explanation.

JavaScript

A basic function to identify intersection:

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
}

View it in action on this jsFiddle, but be aware that this function may also indicate a collision if the cursor lies on the line's slope outside [x1, y1], [x2, y2]. This decision is yours to make :)

You can explore the line-circle-collision library on GitHub for further assistance.

Is there a more optimal way to choose lines than the Bresenham algorithm?

Answer №1

Answer №2

Similar questions

Leveraging the combination of <Form>, jQuery, Sequelize, and SQL for authentication and navigation tasks

leveraging dependency injection to retrieve a function in JavaScript

Instructions on how to activate scrolling for a div element that becomes visible upon clicking a button

listening for events on nested classes

Add integer to an array of strings

How can strings of dates be arranged in MM/DD/YYYY order?

Define the content and appearance of the TD element located at the x (column) and y (row) coordinates within a table

The error TS2339 is indicating that there is no property called myProperty on the type SetStateAction<User>

It can be challenging to manage numerous if-else conditions in JQuery

Tips for handling a JSON payload retrieved through a POST request

Bypass license and credit comments when compressing JavaScript with YUIcompressor

Is there a possibility of encountering an endless update loop within a component's render function?

Webpack in Vuejs does not have access to the keys defined in dev.env.js file

What is the best way to trigger an event in VueJS?

Display array values in JavaScript from different arrays

Issues with triggering the success block in AngularJS and Node.js Express when using $http.get

Activate the Keypress event to update the input value in React upon pressing the Enter

JavaScript - Retrieve the name of an object from a separate array

Conceal or remove disabled years in Angular Material datepicker

Personalize Badge Component