怎么利用js根据坐标判断构成单个多边形是否合法

发布时间：2022-01-10 11:17:26 作者：柒染
来源：亿速云阅读：550

# 怎么利用JS根据坐标判断构成单个多边形是否合法

## 引言

在GIS（地理信息系统）、游戏开发、计算机图形学等领域，判断一组坐标点能否构成合法的简单多边形（Simple Polygon）是一个常见需求。合法多边形需要满足几何学上的基本规则，本文将详细介绍如何使用JavaScript实现这一判断。

---

## 一、什么是合法的简单多边形

合法的简单多边形需满足以下条件：

1. **顶点数量**：至少3个顶点（非共线）
2. **闭合性**：首尾顶点必须重合（或可通过算法自动闭合）
3. **非自相交**：任意两条非相邻边不能相交
4. **非零面积**：所有顶点不能共线

---

## 二、基础验证方法

### 1. 顶点数量检查
```javascript
function checkVertexCount(points) {
  return points.length >= 3;
}

2. 闭合性检查

function isClosed(points) {
  const first = points[0];
  const last = points[points.length - 1];
  return first[0] === last[0] && first[1] === last[1];
}

// 自动闭合多边形（如需要）
function closePolygon(points) {
  if (!isClosed(points)) {
    return [...points, points[0]];
  }
  return points;
}

三、核心算法：判断多边形自相交

1. 线段相交检测算法

使用向量叉积法判断两线段是否相交：

function doSegmentsIntersect(a1, a2, b1, b2) {
  // 向量叉积计算
  const ccw = (p1, p2, p3) => 
    (p3[1] - p1[1]) * (p2[0] - p1[0]) - (p2[1] - p1[1]) * (p3[0] - p1[0]);

  // 快速排斥实验
  if (Math.max(a1[0], a2[0]) < Math.min(b1[0], b2[0]) || 
      Math.max(b1[0], b2[0]) < Math.min(a1[0], a2[0]) ||
      Math.max(a1[1], a2[1]) < Math.min(b1[1], b2[1]) || 
      Math.max(b1[1], b2[1]) < Math.min(a1[1], a2[1])) {
    return false;
  }

  // 跨立实验
  return ccw(a1, a2, b1) * ccw(a1, a2, b2) <= 0 && 
         ccw(b1, b2, a1) * ccw(b1, b2, a2) <= 0;
}

2. 多边形自相交检测

遍历所有非相邻边进行检测：

function hasSelfIntersections(points) {
  const n = points.length;
  for (let i = 0; i < n; i++) {
    const a1 = points[i];
    const a2 = points[(i + 1) % n];
    
    // 跳过相邻边
    for (let j = i + 2; j < n; j++) {
      // 忽略首尾相连的边
      if (i === 0 && j === n - 1) continue;
      
      const b1 = points[j];
      const b2 = points[(j + 1) % n];
      
      if (doSegmentsIntersect(a1, a2, b1, b2)) {
        return true;
      }
    }
  }
  return false;
}

四、零面积多边形检测

1. 共线检测

使用向量叉积判断所有点是否共线：

function arePointsColinear(points) {
  if (points.length < 3) return true;
  
  const [a, b] = points;
  for (let i = 2; i < points.length; i++) {
    const c = points[i];
    // 计算叉积
    const cross = (b[0] - a[0]) * (c[1] - a[1]) - 
                  (b[1] - a[1]) * (c[0] - a[0]);
    if (Math.abs(cross) > Number.EPSILON) {
      return false;
    }
  }
  return true;
}

2. 面积计算

使用Shoelace公式计算多边形面积：

function calculateArea(points) {
  let area = 0;
  const n = points.length;
  
  for (let i = 0; i < n; i++) {
    const j = (i + 1) % n;
    area += points[i][0] * points[j][1];
    area -= points[j][0] * points[i][1];
  }
  
  return Math.abs(area) / 2;
}

五、完整验证流程

function isValidPolygon(points) {
  // 1. 检查顶点数量
  if (!checkVertexCount(points)) {
    console.error("顶点数量不足3个");
    return false;
  }

  // 2. 检查是否闭合（可选，取决于需求）
  if (!isClosed(points)) {
    console.warn("多边形未闭合，将自动闭合");
    points = closePolygon(points);
  }

  // 3. 检查共线性
  if (arePointsColinear(points)) {
    console.error("所有顶点共线，无法构成多边形");
    return false;
  }

  // 4. 检查自相交
  if (hasSelfIntersections(points)) {
    console.error("多边形存在自相交");
    return false;
  }

  // 5. 检查面积（可选）
  const area = calculateArea(points);
  if (area < Number.EPSILON) {
    console.error("多边形面积为零");
    return false;
  }

  return true;
}

六、性能优化建议

空间分区优化：使用四叉树或网格空间索引减少线段相交检测次数
快速拒绝：先进行AABB（轴对齐包围盒）检测
并行计算：在Web Worker中处理大型多边形

// 示例：AABB快速检测
function getBoundingBox(points) {
  let minX = Infinity, minY = Infinity;
  let maxX = -Infinity, maxY = -Infinity;
  
  points.forEach(([x, y]) => {
    minX = Math.min(minX, x);
    minY = Math.min(minY, y);
    maxX = Math.max(maxX, x);
    maxY = Math.max(maxY, y);
  });
  
  return { minX, minY, maxX, maxY };
}

七、实际应用示例

1. 用户绘制多边形验证

const drawnPoints = [[0,0], [5,0], [5,5], [0,5]];

if (isValidPolygon(drawnPoints)) {
  console.log("合法多边形");
} else {
  console.log("非法多边形");
}

2. GeoJSON数据验证

function validateGeoJSONPolygon(geoJson) {
  const coordinates = geoJson.geometry.coordinates[0];
  return isValidPolygon(coordinates);
}

八、常见问题与解决方案

浮点精度问题：

使用Number.EPSILON作为误差范围

function equalWithinTolerance(a, b) {
 return Math.abs(a - b) < Number.EPSILON;
}

退化边问题：

检查是否存在重复顶点

function hasDuplicatePoints(points) {
 const set = new Set(points.map(p => p.join(',')));
 return set.size !== points.length;
}

复杂多边形处理：
- 对于带孔洞的多边形，需要分别验证外环和内环

九、扩展知识

带孔多边形验证：
- 内环必须完全在外环内
- 内环之间不能相交
三维多边形验证：
- 需要判断所有顶点是否共面
- 使用法向量检测

凸多边形检测：

function isConvex(points) {
 const n = points.length;
 let prevCross = 0;


 for (let i = 0; i < n; i++) {
   const a = points[i];
   const b = points[(i+1)%n];
   const c = points[(i+2)%n];


   const cross = (b[0]-a[0])*(c[1]-b[1]) - (b[1]-a[1])*(c[0]-b[0]);


   if (cross !== 0) {
     if (cross * prevCross < 0) return false;
     prevCross = cross;
   }
 }
 return true;
}

十、总结

本文详细介绍了使用JavaScript验证多边形合法性的全套方法，包括： - 基础几何条件检查 - 自相交检测算法 - 零面积判断 - 性能优化技巧 - 实际应用示例

完整的实现代码已包含在文中，读者可直接用于项目开发。对于更复杂的GIS需求，建议使用专业库如Turf.js或JSTS。

注意事项：在实际应用中，应根据具体需求调整验证严格程度，例如游戏开发可能允许自相交，而GIS系统通常要求严格合法多边形。 “`

希望这篇技术文章能满足您的需求！如需调整任何部分或补充更多细节，请随时告知。