Algorithm to determine if Line points are connected to each other and form a Shape

Question

I am drawing on shape on canvas(using HTML5) and need to determine(in javascript, jquery) if drawn Line Points (x,y cordinates) connect or intersect each other and form some shape(like triangle, square etc.). The purpose of this is to fill these shapes with colors, just like painting tools.

Have read few articles like http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/ but did not clearly understand if this can be used as solution for this problem.

Please suggest and algorithm to determine, if line points are connected to each other and form shapes.

Thanks,

score 3 · Accepted Answer · answered Dec 12 '17 at 08:57

Here are some links which has some required guidance for what I was looking out. Sharing the details here can be helpful for others looking for similar info.

https://gist.github.com/lengstrom/8499382

extract from jsfiddle http://jsfiddle.net/justin_c_rounds/Gd2S2/light/

function checkLineIntersection(line1StartX, line1StartY, line1EndX, line1EndY, line2StartX, line2StartY, line2EndX, line2EndY) {
// if the lines intersect, the result contains the x and y of the intersection (treating the lines as infinite) and booleans for whether line segment 1 or line segment 2 contain the point
var denominator, a, b, numerator1, numerator2, result = {
    x: null,
    y: null,
    onLine1: false,
    onLine2: false
};
denominator = ((line2EndY - line2StartY) * (line1EndX - line1StartX)) - ((line2EndX - line2StartX) * (line1EndY - line1StartY));
if (denominator == 0) {
    return result;
}
a = line1StartY - line2StartY;
b = line1StartX - line2StartX;
numerator1 = ((line2EndX - line2StartX) * a) - ((line2EndY - line2StartY) * b);
numerator2 = ((line1EndX - line1StartX) * a) - ((line1EndY - line1StartY) * b);
a = numerator1 / denominator;
b = numerator2 / denominator;

// if we cast these lines infinitely in both directions, they intersect here:
result.x = line1StartX + (a * (line1EndX - line1StartX));
result.y = line1StartY + (a * (line1EndY - line1StartY));
/*
    // it is worth noting that this should be the same as:
    x = line2StartX + (b * (line2EndX - line2StartX));
    y = line2StartX + (b * (line2EndY - line2StartY));
    */
// if line1 is a segment and line2 is infinite, they intersect if:
if (a > 0 && a < 1) {
    result.onLine1 = true;
}
// if line2 is a segment and line1 is infinite, they intersect if:
if (b > 0 && b < 1) {
    result.onLine2 = true;
}
// if line1 and line2 are segments, they intersect if both of the above are true
return result;
};

Test if two lines intersect - JavaScript function

Algorithm to determine if Line points are connected to each other and form a Shape

1 Answers1