确定线点是否相互连接并形成形状的算法

Question

我在 canvas 上绘制形状（使用 HTML5）并且需要确定（在 javascript、jquery 中）是否绘制线点 (x,y坐标）相互连接或相交形成某种形状（如三角形、正方形等）。这样做的目的是给这些形状填充颜色，就像绘画工具一样。

读过几篇类似http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/的文章，但不清楚这是否可以用作解决此问题的方法。

请建议和算法来确定，如果线点相互连接并形成形状。

谢谢，

Answer 1

这里有一些链接，其中包含一些我所寻找内容的必要指导。在此处分享详细信息可能会对其他寻找类似信息的人有所帮助。

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

从 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

javascript

algorithm

graph-algorithm