On a HTML canvas I have multiple points starting from 1 to N, this is basically a connect the dots application and is activated on touchstart.

There is validation so that they can only connect the dots from 1 and go to 2 (.. n). The issue is that right now is there is no validation that the line is a straight line and I am looking for an algorithm to do this, Here is what I have thought so far

1. For 2 points (x1,y1) to (x2,y2) get all the coordinates by finding the slope and using the formula y = mx + b
2. on touchmove get the x,y co-oridnates and make sure it is one of the points from the earlier step and draw a line else do not draw the line.

Is there a better way to do this or are there any different approaches that I can take ?

On a HTML canvas I have multiple points starting from 1 to N, this is basically a connect the dots application and is activated on touchstart.

There is validation so that they can only connect the dots from 1 and go to 2 (.. n). The issue is that right now is there is no validation that the line is a straight line and I am looking for an algorithm to do this, Here is what I have thought so far

1. For 2 points (x1,y1) to (x2,y2) get all the coordinates by finding the slope and using the formula y = mx + b
2. on touchmove get the x,y co-oridnates and make sure it is one of the points from the earlier step and draw a line else do not draw the line.

Is there a better way to do this or are there any different approaches that I can take ?

• javascript
• algorithm
• geometry

• 1 To clarify: do you want to connect the dots yourself, or do you want to make sure the user has connected the dots properly? – Tikhon Jelvis Commented May 6, 2011 at 23:40
• @Tikhon Jelvis I want to make sure the user has connected the dots – user94437 Commented May 7, 2011 at 0:35
• Well, to do that, you can just use my answer, going through all of the user's coordinates and calling isValid on them. You might want to give the user a bit of leeway because drawing a 100% straight line is difficult. – Tikhon Jelvis Commented May 7, 2011 at 0:38

2 Answers 2

Edit: I originally misunderstood the question, it seems.

As far as validating the path: I think it would be easier just to have a function that determines whether a point is valid than calculating all of the values beforehand. Something like:

function getValidatorForPoints(x1, y1, x2, y2) {
    var slope = (y2 - y1) / (x2 - x1);
    return function (x, y) {
        return (y - y1) == slope * (x - x1);
    }
}

Then, given two points, you could do this:

var isValid = getValidatorForPoints(x1, y1, x2, y2);
var x = getX(), y = getY();// getX and getY get the user's new point.
if (isValid(x, y)) {
    // Draw
}

This approach also gives you some flexibility—you could always modify the function to be less precise to acmodate people who don't quite draw a straight line but are tolerably close.

Precision: As mentioned in my ment, you can change the way the function behaves to make it less exacting. I think a good way to do this is as follows:

Right now, we are using the formula (y - y1) == slope * (x - x1). This is the same as (slope * (x - x1)) - (y - y1) == 0. We can change the zero to some positive number to make it accept points "near" the valid line as so:

Math.abs((slope * (x - x1)) - (y - y1)) <= n

Here n changes how close the point has to be to the line in order to count.

I'm pretty sure this works as advertised and helps account for people's drawing the line a little crooked, but somebody should double check my math.

function drawGraphLine(x1, y1, x2, y2, color) {

    var dist = Math.ceil(Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
    var angle = Math.atan2(y2-y1, x2-x1)*180/Math.PI;
    var xshift = dist - Math.abs(x2-x1);
    var yshift = Math.abs(y1-y2)/2;

    var div = document.createElement('div');
    div.style.backgroundColor = color;
    div.style.position = 'absolute';
    div.style.left = (x1 - xshift/2) + 'px';
    div.style.top = (Math.min(y1,y2) + yshift) + 'px';
    div.style.width = dist+'px';
    div.style.height = '3px';
    div.style.WebkitTransform = 'rotate('+angle+'deg)';
    div.style.MozTransform = 'rotate('+angle+'deg)';

}

// By Tomer Almog