1

Start with a 2d grid on an HTML5 canvas. The user creates lines by plotting points - up to 5 lines.

Next, the user can select another arbitrary point on the grid, and the region is highlighted. I need to take that point and define a polygon to fill the region described by the lines created by the user.

So my thought is, I need to detect the lines and canvas edges that surround the arbitrary point, and then draw a polygon.

Here is an image to help understand what I mean (where the system is functioning with two lines):

enter image description here

All the state is managed by using jCanvas and custom Javascript.

Thanks!


Wow... I just woke up and found these incredible answers. Love SO. Thanks guys.

4

3 回答 3

4

您可以使用泛色填充为由用户定义的线限定的单击区域着色。

  1. 让用户在画布上画线。

  2. 当用户点击以线条为界的区域时,用颜色填充该区域。

注意:您必须在画布下方绘制网格线,否则这些网格线将充当填充算法的边界,您将只填充网格单元格。您可以使用 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(不透明度)。

// 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];

因此,您可以像这样跳转到鼠标下方任意像素的红色元素:

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

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

您可以通过获取接下来的 4 个像素数组元素来获取所有 4 个 r,g,b,a 值

var r = fillData.data[pixelPos];
var g = fillData.data[pixelPos + 1];
var b = fillData.data[pixelPos + 2];
var a = fillData.data[pixelPos + 3];
于 2014-03-27T06:36:32.853 回答
2

这是一个完整的工作解决方案,您可以在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();
于 2014-03-27T11:54:00.520 回答
1

您的第一步是找到这两行。有多种描述线条的方式:传统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 >= 0a2 * 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;
   }
 }

}

如果你想真正得到一个变得非常困难的多边形。您想找到由您的不等式定义的可行区域。这是Linear_programming中的一个经典问题,它们可能是一个可以解决这个问题的库。

可能是一个草图算法。假设行的形式为 'ax + by + 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
于 2014-03-26T22:23:16.353 回答