在HTML5畫布上檢測由行描述的區域

Question

從HTML5畫布上的2d網格開始。用戶通過繪製點來創建線 - 最多5行。

接下來，用戶可以選擇網格上的另一個任意點，並突出顯示區域。我需要採取這一點，並定義一個多邊形來填充由用戶創建的線描述的區域。

所以我的想法是，我需要檢測圍繞任意點的線條和畫布邊緣，然後繪製一個多邊形。

這裏是爲了幫助理解我的意思（其中系統與兩條線運行）的圖像：

所有狀態是通過使用jCanvas和自定義JavaScript管理。

謝謝！

---

哇...我剛醒來，發現了這些令人難以置信的答案。愛SO。多謝你們。

Answer 1

下面是一個完整可行的解決方案，你可以看到它在運行http://jsfiddle.net/SalixAlba/PhE26/2/ 它使用相當多的算法，我的第一個答案。

// canvas and mousedown related variables 
var canvas = document.getElementById("canvas"); 
var ctx = canvas.getContext("2d"); 
var $canvas = $("#canvas"); 
var canvasOffset = $canvas.offset(); 
var offsetX = canvasOffset.left; 
var offsetY = canvasOffset.top; 
var scrollX = $canvas.scrollLeft(); 
var scrollY = $canvas.scrollTop(); 

// save canvas size to vars b/ they're used often 
var canvasWidth = canvas.width; 
var canvasHeight = canvas.height; 

// list of lines created 
var lines = new Array(); 

// list of all solutions 
var allSolutions = new Array(); 
// solutions round bounding rect 
var refinedSols = new Array(); 
// ordered solutions for polygon 
var polySols = new Array(); 

/////////// The line type 

// A line defined by a x + b y + c = 0 
function Line(a,b,c) { 
    this.a = a; 
    this.b = b; 
    this.c = c; 
} 

// given two points create the line 
function makeLine(x0,y0,x1,y1) { 
    // Line is defined by 
    // (x - x0) * (y1 - y0) = (y - y0) * (x1 - x0) 
    // (y1-y0)*x - (x1-x0)* y + x0*(y1-y0)+y0*(x1-x0) = 0 
    return new Line((y1-y0), (x0-x1), -x0*(y1-y0)+y0*(x1-x0)); 
}; 

Line.prototype.toString = function() { 
    var s = "" + this.a + " x "; 
    s += (this.b >= 0 ? "+ "+this.b : "- "+ (-this.b)); 
    s += " y "; 
    s += (this.c >= 0 ? "+ "+this.c : "- "+ (-this.c)); 
    return s + " = 0"; 
}; 

Line.prototype.draw = function() { 
    var points = new Array(); 
    // find the intersecetions with the boinding box 
    // lhs : a * 0 + b * y + c = 0 
    if(this.b != 0) { 
     var y = -this.c/this.b; 
     if(y >= 0 && y <= canvasHeight) 
      points.push([0,y]); 
    } 
    // rhs : a * canvasWidth + b * y + c = 0 
    if(this.b != 0) { 
     var y = (- this.a * canvasWidth - this.c)/ this.b; 
     if(y >= 0 && y <= canvasHeight) 
      points.push([canvasWidth,y]); 
    } 
    // top : a * x + b * 0 + c = 0 
    if(this.a != 0) { 
     var x = -this.c/this.a; 
     if(x > 0 && x < canvasWidth) 
      points.push([x,0]); 
    } 
    // bottom : a * x + b * canvasHeight + c = 0 
    if(this.a != 0) { 
     var x = (- this.b * canvasHeight - this.c)/ this.a; 
     if(x > 0 && x < canvasWidth) 
      points.push([x,canvasHeight]); 
    } 
    if(points.length == 2) { 
     ctx.moveTo(points[0][0], points[0][1]); 
     ctx.lineTo(points[1][0], points[1][1]); 
    } 
    else 
     console.log(points.toString()); 
} 

// Evalute the defining function for a line 
Line.prototype.test = function(x,y) { 
    return this.a * x + this.b * y + this.c; 
} 

// Find the intersection of two lines 
Line.prototype.intersect = function(line2) { 
    // need to solve 
    // a1 x + b1 y + c1 = 0 
    // a2 x + b2 y + c2 = 0 
    var det = this.a * line2.b - this.b * line2.a; 
    if(Math.abs(det) < 1e-6) return null; 
    // (x) = 1 (b2 -b1) (-c1) 
    // () = --- (   ) ( ) 
    // (y) det (-a2 a1) (-c2) 
    var x = (- line2.b * this.c + this.b * line2.c)/det; 
    var y = ( line2.a * this.c - this.a * line2.c)/det; 
    var sol = { x: x, y: y, line1: this, line2: line2 }; 
    return sol; 
} 

//// General methods 

// Find all the solutions of every pair of lines 
function findAllIntersections() { 
    allSolutions.splice(0); // empty 
    for(var i=0;i<lines.length;++i) { 
     for(var j=i+1;j<lines.length;++j) { 
      var sol = lines[i].intersect(lines[j]); 
      if(sol!=null) 
       allSolutions.push(sol); 
     } 
    } 
} 

// refine solutions so we only have ones inside the feasible region 
function filterSols(targetX,targetY) { 
    refinedSols.splice(0); 
    // get the sign on the test point for each line 
    var signs = lines.map(function(line){ 
     return line.test(targetX,targetY);}); 
    for(var i=0;i<allSolutions.length;++i) { 
     var sol = allSolutions[i]; 
     var flag = true; 
     for(var j=0;j<lines.length;++j) { 
      var l=lines[j]; 
      if(l==sol.line1 || l==sol.line2) continue; 
      var s = l.test(sol.x,sol.y); 
      if((s * signs[j]) < 0) 
       flag = false; 
     } 
     if(flag) 
      refinedSols.push(sol); 
    } 
} 

// build a polygon from the refined solutions 
function buildPoly() { 
    polySols.splice(0); 
    var tempSols = refinedSols.map(function(x){return x}); 
    if(tempSols.length<3) return null; 
    var curSol = tempSols.shift(); 
    var curLine = curSol.line1; 
    polySols.push(curSol); 
    while(tempSols.length>0) { 
     var found=false; 
     for(var i=0;i<tempSols.length;++i) { 
      var sol=tempSols[i]; 
      if(sol.line1 == curLine) { 
       curSol = sol; 
       curLine = sol.line2; 
       polySols.push(curSol); 
       tempSols.splice(i,1); 
       found=true; 
       break; 
      } 
      if(sol.line2 == curLine) { 
       curSol = sol; 
       curLine = sol.line1; 
       polySols.push(curSol); 
       tempSols.splice(i,1); 
       found=true; 
       break; 
      } 
     } 
     if(!found) break; 
    } 
} 

// draw 
function draw() { 
    console.log("drawlines"); 
    ctx.clearRect(0, 0, canvas.width, canvas.height) 

    if(polySols.length>2) { 
     ctx.fillStyle = "Orange"; 
     ctx.beginPath(); 
     ctx.moveTo(polySols[0].x,polySols[0].y); 
     for(var i=1;i<polySols.length;++i) 
      ctx.lineTo(polySols[i].x,polySols[i].y); 
     ctx.closePath(); 
     ctx.fill(); 
    } 

    ctx.lineWidth = 5; 
    ctx.beginPath(); 
    lines.forEach(function(line, index, array) {console.log(line.toString()); line.draw();}); 

    ctx.fillStyle = "Blue"; 
    ctx.fillRect(x0-4,y0-4,8,8); 
    ctx.fillRect(x1-4,y1-4,8,8); 
    ctx.stroke(); 

    ctx.beginPath(); 
    ctx.fillStyle = "Red"; 
    allSolutions.forEach(function(s,i,a){ctx.fillRect(s.x-5,s.y-5,10,10);}); 

    ctx.fillStyle = "Green"; 
    refinedSols.forEach(function(s,i,a){ctx.fillRect(s.x-5,s.y-5,10,10);}); 
    ctx.stroke(); 

} 

var x0 = -10; 
var y0 = -10; 
var x1 = -10; 
var y1 = -10; 
var clickCount = 0; // hold the number of clicks 

// Handle mouse clicks 
function handleMouseDown(e) { 
    e.preventDefault(); 

    // get the mouse position 
    var x = parseInt(e.clientX - offsetX); 
    var y = parseInt(e.clientY - offsetY); 

    if(clickCount++ % 2 == 0) { 
     // store the position 
     x0 = x; 
     y0 = y; 
     x1 = -10; 
     y1 = -10; 
     filterSols(x,y); 
     buildPoly(); 
     draw(); 
    } 
    else { 
     x1 = x; 
     y1 = y; 
     var line = makeLine(x0,y0,x,y); 
     lines.push(line); 
     findAllIntersections(); 
     draw(); 
    }  
} 

$("#canvas").mousedown(function (e) { 
    handleMouseDown(e); 
}); 


// add the lines for the bounding rectangle 
lines.push(
    new Line(1, 0, -50), // first line is x - 50 >= 0 
    new Line(-1, 0, 250), // first line is -x + 250 >= 0 
    new Line(0, 1, -50), // first line is y - 50 >= 0 
    new Line(0,-1, 250)); // first line is -y + 250 >= 0 

findAllIntersections(); 
draw(); 

Answer 2

您的第一步是找到兩條線。有多種描述線條的方式：傳統的y=m x + c，隱式的形式a x+b y+c=0，參數形式(x,y) = (x0,y0) + t(dx,dy)。可能最有用的是隱式形式，因爲它可以描述垂直線。

如果您有兩個點（x1，y1）和（x2，y2），則該線可以作爲y=y1 + (x-x1) (y2-y1)/(x2-x1)給出。或(y-y1) * (x2-x1) = (x-x1)*(y2-y1)。

您可以對由四點定義的兩條線進行此操作。

要真正繪製區域，您需要找到線條相交的點，這是標準求解兩個線性方程問題，您可能在高中時做過這個問題。您還需要找到線條穿越您所在地區邊界的點。這很容易找到，因爲您可以將邊界的x或y值放入方程中並找到其他座標。您可能還需要在框的角​​落添加一個點。

將需要一些邏輯來確定你想要的四個可能的段中的哪一個。

對於多行，您可以將其視爲一組不等式。你需要計算線的方程式，如a1 * x + b1 * y + c1 >= 0，a2 * x + b2 * y + c2 <= 0 ......稱這些E1，E2，......不平等將取決於你想要的線的哪一側。 （它從原始問題中不清楚你將如何解決這個問題。）

最簡單的方法使用基於像素的技術。循環遍歷圖像中的像素，如果滿足所有不等式，則設置像素。

var myImageData = context.createImageData(width, height); 
for(var x=xmin;i<xmax;++i) { 
    for(var y=ymin;j<ymax;++j) { 
    if((a1 * x + b1 * y + c1 >= 0) && 
     (a2 * x + b2 * y + c2 >= 0) && 
     ... 
     (a9 * x + b9 * y + c9 >= 0)) 
    { 
     var index = ((y-ymin)*width + (x-xmin))*4; // index of first byte of pixel 
     myImageData.data[index] = redValInside; 
     myImageData.data[index+1] = greenValInside; 
     myImageData.data[index+2] = blueValInside; 
     myImageData.data[index+3] = alphaValInside; 
    } else { 
     var index = ((y-ymin)*width + (x-xmin))*4; // index of first byte of pixel 
     myImageData.data[index] = redValOutside; 
     myImageData.data[index+1] = greenValOutside; 
     myImageData.data[index+2] = blueValOutside; 
     myImageData.data[index+3] = alphaValOutside; 
    } 
} 

}

如果你想真正得到變得相當困難的多邊形。你想找到你的不平等所定義的Feasible region。這是Linear_programming中的一個經典問題，它們可能是一個解決這個問題的庫。

這可能是草圖算法。假設線在形式「一個X + B Y + C> = 0」

// find all solutions for intersections of the lines 
var posibleSols = new Array(); 
for(var line1 : all lines) { 
    for(var line2 : all lines) { 
    var point = point of intersection of line1 and line2 
    point.lineA = line1; // store the two lines for later use 
    point.lineB = line2; 
    } 
} 

// refine solutions so we only have ones inside the feasible region 
var refinedSols = new Array(); 
for(var i=0;i<posibleSols.length;++i) { 
    var soln = possibleSols[i]; 
    var flag = true; // flag to tell if the line passes 
    for(var line : all lines) { 
    if(line == soln.line1 || line == soln.line2) continue; // don't test on lines for this point 
    if(line.a * point.x + line.b * point.b + line.c < 0) { 
     flag = false; // failed the test 
    } 
    } 
    if(flag) 
    refinedSols.push(sol); // if it passed all tests add it to the solutions 
} 

// final step is to go through the refinedSols and find the vertices in order 
var result = new Array(); 
var currentSol = refinedSols[0]; 
result.push(currentSol); 
var currentLine = startingSol.lineA; 
refinedSols.splice(0,1); // remove soln from array 
while(refinedSols.length>0) { 
    // fine a solution on the other end of currentLine 
    var nextSol; 
    for(var i=0;i< refinedSols.length;++i) { 
    nextSol = refinedSols[i]; 
    if(nextSol.lineA == currentLine) { 
     currentSol = nextSol; 
     currentLine = nextSol.lineA; 
     result.push(currentSol); 
     refinedSols.splice(i,1); // remove this from list 
     break; 
    } 
    else if(nextSol.lineB == currentLine) { 
     currentSol = nextSol; 
     currentLine = nextSol.lineB; 
     result.push(currentSol); 
     refinedSols.splice(i,1); // remove this from list 
     break; 
    } 
    } 
    // done you can now make a polygon from the points in result 

Answer 3

可以使用洪水填充到由用戶定義的線爲邊界的顏色點擊區域。

1. 讓用戶在畫布上畫線。

2. 當用戶單擊由線限定的區域時，使用顏色填充該區域。

注意：您必須繪製網格線在畫布下方，否則這些網格線將作爲邊界此時，floodFill算法，您將只需填寫一個網格單元。您可以使用CSS在您的畫布下對圖像進行分層或使用單獨的畫布繪製網格線。

這裏的起始示例代碼和一個演示：http://jsfiddle.net/m1erickson/aY4Xs/

<!doctype html> 
<html> 
<head> 
<link rel="stylesheet" type="text/css" media="all" href="css/reset.css" /> <!-- reset css --> 
<script type="text/javascript" src="http://code.jquery.com/jquery.min.js"></script> 
<style> 
    body{ background-color: ivory; } 
    #canvas{border:1px solid red;} 
</style> 
<script> 
$(function(){ 

    // canvas and mousedown related variables 
    var canvas=document.getElementById("canvas"); 
    var ctx=canvas.getContext("2d"); 
    var $canvas=$("#canvas"); 
    var canvasOffset=$canvas.offset(); 
    var offsetX=canvasOffset.left; 
    var offsetY=canvasOffset.top; 
    var scrollX=$canvas.scrollLeft(); 
    var scrollY=$canvas.scrollTop(); 

    // save canvas size to vars b/ they're used often 
    var canvasWidth=canvas.width; 
    var canvasHeight=canvas.height; 

    // define the grid area 
    // lines can extend beyond grid but 
    // floodfill wont happen outside beyond the grid 
    var gridRect={x:50,y:50,width:200,height:200} 

    drawGridAndLines(); 

    // draw some test gridlines 
    function drawGridAndLines(){ 
     ctx.clearRect(0,0,canvas.width,canvas.height) 
     // Important: the lineWidth must be at least 5 
     // or the floodfill algorithm will "jump" over lines 
     ctx.lineWidth=5; 
     ctx.strokeRect(gridRect.x,gridRect.y,gridRect.width,gridRect.height); 
     ctx.beginPath(); 
     ctx.moveTo(75,25); 
     ctx.lineTo(175,275); 
     ctx.moveTo(25,100); 
     ctx.lineTo(275,175); 
     ctx.stroke(); 
    } 

    // save the original (unfilled) canvas 
    // so we can reference where the black bounding lines are 
    var strokeData = ctx.getImageData(0, 0, canvasWidth, canvasHeight); 

    // fillData contains the floodfilled canvas data 
    var fillData = ctx.getImageData(0, 0, canvasWidth, canvasHeight); 


    // Thank you William Malone for this great floodFill algorithm! 
    // http://www.williammalone.com/articles/html5-canvas-javascript-paint-bucket-tool/ 
    ////////////////////////////////////////////// 

    function floodFill(startX, startY, startR, startG, startB) { 
     var newPos; 
     var x; 
     var y; 
     var pixelPos; 
     var neighborLeft; 
     var neighborRight; 
     var pixelStack = [[startX, startY]]; 

     while (pixelStack.length) { 

     newPos = pixelStack.pop(); 
     x = newPos[0]; 
     y = newPos[1]; 

     // Get current pixel position 
     pixelPos = (y * canvasWidth + x) * 4; 

     // Go up as long as the color matches and are inside the canvas 
     while (y >= 0 && matchStartColor(pixelPos, startR, startG, startB)) { 
      y -= 1; 
      pixelPos -= canvasWidth * 4; 
     } 

     pixelPos += canvasWidth * 4; 
     y += 1; 
     neighborLeft = false; 
     neighborRight = false; 

     // Go down as long as the color matches and in inside the canvas 
     while (y <= (canvasHeight-1) && matchStartColor(pixelPos, startR, startG, startB)) { 
      y += 1; 

      fillData.data[pixelPos]  = fillColor.r; 
      fillData.data[pixelPos + 1] = fillColor.g; 
      fillData.data[pixelPos + 2] = fillColor.b; 
      fillData.data[pixelPos + 3] = 255; 


      if (x > 0) { 
      if (matchStartColor(pixelPos - 4, startR, startG, startB)) { 
       if (!neighborLeft) { 
       // Add pixel to stack 
       pixelStack.push([x - 1, y]); 
       neighborLeft = true; 
       } 
      } else if (neighborLeft) { 
       neighborLeft = false; 
      } 
      } 

      if (x < (canvasWidth-1)) { 
      if (matchStartColor(pixelPos + 4, startR, startG, startB)) { 
       if (!neighborRight) { 
       // Add pixel to stack 
       pixelStack.push([x + 1, y]); 
       neighborRight = true; 
       } 
      } else if (neighborRight) { 
       neighborRight = false; 
      } 
      } 

      pixelPos += canvasWidth * 4; 
     } 
     } 
    } 

    function matchStartColor(pixelPos, startR, startG, startB) { 

     // get the color to be matched 
     var r = strokeData.data[pixelPos], 
     g = strokeData.data[pixelPos + 1], 
     b = strokeData.data[pixelPos + 2], 
     a = strokeData.data[pixelPos + 3]; 

     // If current pixel of the outline image is black-ish 
     if (matchstrokeColor(r, g, b, a)) { 
     return false; 
     } 

     // get the potential replacement color 
     r = fillData.data[pixelPos]; 
     g = fillData.data[pixelPos + 1]; 
     b = fillData.data[pixelPos + 2]; 

     // If the current pixel matches the clicked color 
     if (r === startR && g === startG && b === startB) { 
     return true; 
     } 

     // If current pixel matches the new color 
     if (r === fillColor.r && g === fillColor.g && b === fillColor.b) { 
     return false; 
     } 

     return true; 
    } 

    function matchstrokeColor(r, g, b, a) { 
     // never recolor the initial black divider strokes 
     // must check for near black because of anti-aliasing 
     return (r + g + b < 100 && a === 255); 
    } 

    // Start a floodfill 
    // 1. Get the color under the mouseclick 
    // 2. Replace all of that color with the new color 
    // 3. But respect bounding areas! Replace only contiguous color. 
    function paintAt(startX, startY) { 

     // get the clicked pixel's [r,g,b,a] color data 
     var pixelPos = (startY * canvasWidth + startX) * 4, 
     r = fillData.data[pixelPos], 
     g = fillData.data[pixelPos + 1], 
     b = fillData.data[pixelPos + 2], 
     a = fillData.data[pixelPos + 3]; 

     // this pixel's already filled 
     if (r === fillColor.r && g === fillColor.g && b === fillColor.b) { 
     return; 
     } 

     // this pixel is part of the original black image--don't fill 
     if (matchstrokeColor(r, g, b, a)) { 
     return; 
     } 

     // execute the floodfill 
     floodFill(startX, startY, r, g, b); 

     // put the colorized data back on the canvas 
     ctx.putImageData(fillData, 0, 0); 
    } 

    // end floodFill algorithm 
    ////////////////////////////////////////////// 


    // get the pixel colors under x,y 
    function getColors(x,y){ 
     var data=ctx.getImageData(x,y,1,1).data; 
     return({r:data[0], g:data[1], b:data[2], a:data[3] }); 
    } 

    // create a random color object {red,green,blue} 
    function randomColorRGB(){ 
     var hex=Math.floor(Math.random()*16777215).toString(16); 
     var r=parseInt(hex.substring(0,2),16); 
     var g=parseInt(hex.substring(2,4),16); 
     var b=parseInt(hex.substring(4,6),16); 
     return({r:r,g:g,b:b});  
    } 

    function handleMouseDown(e){ 
     e.preventDefault(); 

     // get the mouse position 
     x=parseInt(e.clientX-offsetX); 
     y=parseInt(e.clientY-offsetY); 

     // don't floodfill outside the gridRect 
     if(
      x<gridRect.x+5 || 
      x>gridRect.x+gridRect.width || 
      y<gridRect.y+5 || 
      y>gridRect.y+gridRect.height 
    ){return;} 

     // get the pixel color under the mouse 
     var px=getColors(x,y); 

     // get a random color to fill the region with 
     fillColor=randomColorRGB(); 

     // floodfill the region bounded by black lines 
     paintAt(x,y,px.r,px.g,px.b); 
    } 

    $("#canvas").mousedown(function(e){handleMouseDown(e);}); 

}); // end $(function(){}); 
</script> 
</head> 
<body> 
    <h4>Click in a region within the grid square.</h4> 
    <canvas id="canvas" width=300 height=300></canvas> 
</body> 
</html> 

[關於getImageData信息和像素陣列]

context.getImageData().data獲取表示R，G，B的陣列&畫布指定區域的值（在本例中，我們選擇了整個畫布）。左上像素（0,0）是數組中的第一個元素。

每個像素由數組中的4個順序元素表示。

第一個數組元素包含紅色成分（0-255），下一個元素包含藍色，下一個包含藍色，下一個包含綠色，下一個包含alpha（不透明度）。通過獲取未來4

// pixelPos is the position in the array of the first of 4 elements for pixel (mouseX,mouseY) 

var pixelPos = (mouseY * canvasWidth + mouseX) * 4 

，你可以得到所有4個R，G，B，A值：

// pixel 0,0 
red00=data[0]; 
green00=data[1]; 
blue00=data[2]; 
alpha00=data[3]; 

// pixel 1,0 
red10=data[4]; 
green10=data[5]; 
blue10=data[6]; 
alpha10=data[7]; 

因此，你跳轉到任何像素的紅色元素的鼠標下這樣像素數組元素

var r = fillData.data[pixelPos]; 
var g = fillData.data[pixelPos + 1]; 
var b = fillData.data[pixelPos + 2]; 
var a = fillData.data[pixelPos + 3];