在坐标之间绘制多边形，避免交叉。

Question

我有一个由鼠标单击canvas产生的坐标数组。请参考JS fiddle。

var pointsArray = [];

通过点击事件，这个数组被push了x和y值。

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

我遍历points数组，并在当前点和前一个点之间画一条线。

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。我该如何解决呢？我的第一反应告诉我要按照从上到下、从左到右的顺序对点进行排序，然后再绘制。

- Kyle

---

只是为了澄清，这些线条并不是根据用户的点击顺序绘制的，对吧？ - Dinesh

正确。必须仅形成单个多边形，而不是基于点击序列。 - Kyle

假设你有(0,0), (0,1), (1,1), (1,0)这四个点。如果你按照这个顺序点击它们，你会看到一个正方形。但是如果你按照以下顺序点击它们(0,0), (1,1), (1,0), (0,1)，在这种情况下预期的结果是什么？还是同样的正方形？或者因为交叉而跳过了(1,0)，最终结果将成为三角形(0,0), (1,1), (0,1)？你能发一个fiddle吗？也许尝试实验会更容易... - ROMANIA_engineer

当调用drawPolygon时，应该是相同的正方形。没有任何点被“删除”。 - Kyle

它是凸多边形吗？拥有x个不同的点（x≥3），使用给定的点集，您可以得到许多凹多边形...（想象一下您有一个六边形并且您“切掉”了一片->有6片可以“切掉”。编辑：哦，我明白了。如果它是凹的，则顺序将是“点击”顺序。 - ROMANIA_engineer

@helpYou https://jsfiddle.net/8jpk4gr2/ - Kyle

Answer 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：根据角度对点进行排序

• 扩展点对象以接受角度参数。
• 遍历点数组。
• 计算相对于中心点的角度。
• 基于角度对数组进行排序。

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

方法如下：

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);
  }
}

然后您需要使用自定义排序函数基于角度对点进行排序。只需在数组上使用标准的sort()方法并提供自己的函数，该函数将使用点对象的角度属性：

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>

- user1693593

---

@SimonPlus，你是如何绘制这些点的？一些像这个和这个的测试看起来运行良好（随机绘制点）。 - user1693593

@SimonPlus 是的，有一些情况下质心算法无法正确居中。我在答案中提到了这一点，它没有包含在演示中，但是通过所呈现的代码，我认为您将能够进行额外的步骤。我可以添加一个只使用平均值的示例，并将其作为演示结果添加到最后…给我几分钟。 - user1693593

@SimonPlus 好的，我整理了答案，将重点放在这个解决方案上（对于未来的读者，如果有人感兴趣，质心方法可以在编辑历史记录中找到）。 - user1693593

Answer 2

多边形可以按顺时针或逆时针方向定义。

要将您的“随机”点击排序为顺时针顺序：

1. 找到您的多边形的“中心”。这是x和y的算术平均值。

2. 计算从中心点到每个用户点的所有角度。您可以使用 Math.atan2(differenceInYs,differenceInXs); 来完成此操作。

3. 按其在＃2中计算的角度升序排列点。

现在，您的点形成一个顺时针多边形。

- markE