根据已知坐标数组构造简单多边形

问题

给定平面中n个点所组成的集合，将它们连接起来形成一条简单的封闭路径。所谓简单路径，是指边与边无交叉。

zoom-img

思路

取x坐标最大的点A（如果最大x坐标的点不止一个，则取Y坐标最小的点），依次计算A点与其余各点的连线与水平线之间夹角的正切值，然后按照正切值排序，依次连接排序后的各点即组成一个简单图形。

原理

其它所有点都在A点的左侧，所有夹角的范围为-Pi/2~Pi/2，单调递增函数。

zoom-img

代码实现

// 经纬度坐标
const pointsList = [[95,30],[85,25],[99,23],[112,20],[108,13],[82,23]];
function sortPolygonPoints (pointsList) {
  // 获取最右侧的坐标（经度值最大）
  let rightPoint = pointsList[0];
  let maxLong = 0;
  for (let i = 0; i < pointsList.length; i++) {
    const [long, _] = pointsList[i];
    if (long > maxLong) {
      maxLong = long;
      rightPoint = pointsList[i];
    }
  }
  // 定义数组存放坐标和对应正切值
  const pointsArray = [];
  for (let i = 0; i < pointsList.length; i++) {
    const [long, lat] = pointsList[i];
    let tanX;
    if (long === rightPoint[0] && lat === rightPoint[1]) {
      tanX = Number.MAX_SAFE_INTEGER;
    } else {
      tanX = (lat - rightPoint[1]) / (long - rightPoint[0]);
    }
    pointsArray.push({ point: pointsList[i], tanX });
  }

  pointsArray.sort((a, b) => a.tanX - b.tanX);
  return pointsArray.map(({ point }) => point);
}
sortPolygonPoints(pointsList);

上述代码中sortPolygonPoints函数返回的数组各项依次连接，即可生成一个简单多边形。

以上就是本文的全部内容，感谢阅读。