javascript - 在坐标之间绘制多边形，防止相交

Question

JS fiddle

我有一个坐标数组，通过在 canvas 上单击鼠标来填充。

var pointsArray = [];

此数组 是使用点击事件推送ed x 和y 值。

pointsArray.push({x: xVal, y: yVal});

我迭代点数组并在当前点和之前的点之间画一条线。

function drawPolygon(points) {
    //check arguments for null values
    if(!points)
        return false;

    var i;
    for(i = 0; i < points.length; i++)
        drawLine(points[i-1], points[i]);

    //draw the final line
    drawLine(points[i-1], points[0]);
}

drawLine 看起来像这样:

function drawLine(point1, point2) {
    //check arguments for null values
    if(!point1 || !point2)
        return false;

    context.beginPath();
    context.moveTo(point1.x, point1.y);
    context.lineTo(point2.x, point2.y);
    context.stroke();
}

不幸的是，根据用户点击的顺序，我可以让线条相交，但我不希望这样:http://i.imgur.com/3gaHRTa.png我将如何解决这个问题？我的第一直觉告诉我在 array 中从上到下、从左到右对点进行排序，然后绘制。

Answer 1

第 1 步:使用点的平均位置找到多边形的中心

此函数将在给定图形中的所有点的情况下找到中心，与顺序无关:

function findCenter(points) {

  var x = 0, y = 0, i, len = points.length;

  for (i = 0; i < len; i++) {
    x += points[i].x;
    y += points[i].y;
  }
  return {x: x / len, y: y / len};   // return average position
}

显示多边形中心点的演示

/**
 * Created by knguyen on 4/13/2015.
 */
var pointsArray = [];
var canvas = document.getElementById("myCanvas");
var context = canvas.getContext("2d");

function Point(x, y) {
    this.x = x;
    this.y = y;
}

function drawDot(e) {
    var position = getMousePosition(canvas, e);
    posx = position.x;
    posy = position.y;

    storeCoordinate(posx, posy);

    context.fillStyle = "#F00";
    context.fillRect(posx, posy, 6, 6);
}

function getMousePosition(c, e) {
    var rect = canvas.getBoundingClientRect();
    return {x: e.clientX - rect.left, y: e.clientY - rect.top}
}
function storeCoordinate(xVal, yVal) {pointsArray.push(new Point(xVal, yVal))}

$("#solve").click(
    function() {
      var p = findCenter(pointsArray);
      context.fillStyle = "green";
      context.fillRect(p.x, p.y, 4, 4);
    }
);

function findCenter(points) {

  var x = 0, y = 0, i, len = points.length;

  for (i = 0; i < len; i++) {
    x += points[i].x;
    y += points[i].y;
  }
  return {x: x / len, y: y / len};   // return average position
}

#myCanvas {border: 1px solid #000}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<canvas id="myCanvas" width="400" height="300" onclick="drawDot(event)"></canvas>
<div>
  <button type="button" class="btn btn-default" id="solve">Show center point</button>
</div>

第 2 步:根据 Angular 对点进行排序

• 扩展点对象以也采用 Angular 参数。
• 遍历点数组
• 计算相对于中心点的 Angular
• 根据 Angular 对数组进行排序

要找到 Angular ，只需计算相对于中心点的 Angular 即可。

方法如下:

function findAngles(c, points) {

  var i, len = points.length, p, dx, dy;

  for (i = 0; i < len; i++) {
    p = points[i];
    dx = p.x - c.x;
    dy = p.y - c.y;
    p.angle = Math.atan2(dy, dx);
  }
}

然后您必须使用自定义排序函数根据 Angular 对点进行排序。只需在数组上使用标准的 sort() 方法并提供您自己的函数，该函数将使用点对象的 Angular 属性:

pointsArray.sort(function(a, b) {
  if (a.angle > b.angle) return 1;
  else if (a.angle < b.angle) return -1;
  return 0;
});

然后在所有点之间画一条线。

工作演示

var pointsArray = [];
var canvas = document.getElementById("myCanvas");
var context = canvas.getContext("2d");

function Point(x, y) {
    this.x = x;
    this.y = y;
    this.angle = 0;
}

canvas.onclick = drawDot;
function drawDot(e) {
    var position = getMousePosition(canvas, e);
    posx = position.x;
    posy = position.y;
    storeCoordinate(posx, posy);
    context.fillStyle = "#F00";
    context.fillRect(posx-3, posy-3, 6, 6);
}

function getMousePosition(c, e) {
    var rect = canvas.getBoundingClientRect();
    return {x: e.clientX - rect.left, y: e.clientY - rect.top}
}
function storeCoordinate(xVal, yVal) {pointsArray.push(new Point(xVal, yVal))}

$("#solve").click(
    function() {

      // find center
      var cent = findCenter(pointsArray);
      context.fillStyle = "green";
      context.fillRect(cent.x-3, cent.y-3, 6, 6);
      
      // find angles
      findAngles(cent, pointsArray);
      
      // sort based on angle using custom sort
      pointsArray.sort(function(a, b) {
        return (a.angle >= b.angle) ? 1 : -1
      });
            
      // draw lines
      context.beginPath();
      context.moveTo(pointsArray[0].x, pointsArray[0].y);
      for(var i = 0; i < pointsArray.length; i++) {
        context.lineTo(pointsArray[i].x, pointsArray[i].y);
      }
      context.strokeStyle = "#00f";
      context.closePath();
      context.stroke();
    }
);

function findCenter(points) {
  var x = 0, y = 0, i, len = points.length;
  for (i = 0; i < len; i++) {
    x += points[i].x;
    y += points[i].y;
  }
  return {x: x / len, y: y / len};   // return average position
}

function findAngles(c, points) {
  var i, len = points.length, p, dx, dy;
  for (i = 0; i < len; i++) {
    p = points[i];
    dx = p.x - c.x;
    dy = p.y - c.y;
    p.angle = Math.atan2(dy, dx);
  }
}

$("#reset").click(
  function() {
      context.clearRect(0, 0, canvas.width, canvas.height); //clear the canvas
      pointsArray = []; //clear the array
  }
);

#myCanvas {border: 1px solid #000}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<canvas id="myCanvas" width="400" height="300"></canvas>
<div><button id="solve">Draw Polygon</button><button id="reset">Reset</button></div>