Lineポイントが互いに接続されてシェイプを形成するかどうかを決定するアルゴリズム

Question

キャンバス上で（HTML5を使用して）シェイプを描いています。描画された場合（JavaScript、jqueryで）決定する必要があります。 （三角形、四角形など）を形成することができます。これは、ペイントツールと同様に、これらの図形を色で塗りつぶすことを目的としています。

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