CHATchatgpt：javascript檢測兩個多邊形是否交涉

ejsoon · 帖子由 **ejsoon** » 2024年 7月 22日 14:12

要用 JavaScript 代码判定两个多边形是否相交（干涉），可以采用以下方法之一。这里我将使用边界框检测（Bounding Box Test）作为基础，并结合点在多边形内的检测方法。

首先，我们定义两个多边形的顶点坐标数组：

```javascript
// 五边形的顶点坐标
const polygon1 = [
{ x: 30, y: 80 },
{ x: 60, y: 110 },
{ x: 90, y: 100 },
{ x: 80, y: 60 },
{ x: 40, y: 40 }
];

// 六边形的顶点坐标
const polygon2 = [
{ x: 20, y: 30 },
{ x: 60, y: 20 },
{ x: 100, y: 40 },
{ x: 110, y: 80 },
{ x: 70, y: 100 },
{ x: 30, y: 70 }
];
```

### 方法一：边界框检测 + 点在多边形内检测

1. **边界框检测**：首先计算两个多边形的边界框，判断它们是否相交。

```javascript
// 边界框检测函数
function boundingBoxIntersect(poly1, poly2) {
// 计算多边形1的边界框
let minX1 = Math.min(...poly1.map(p => p.x));
let maxX1 = Math.max(...poly1.map(p => p.x));
let minY1 = Math.min(...poly1.map(p => p.y));
let maxY1 = Math.max(...poly1.map(p => p.y));

// 计算多边形2的边界框
let minX2 = Math.min(...poly2.map(p => p.x));
let maxX2 = Math.max(...poly2.map(p => p.x));
let minY2 = Math.min(...poly2.map(p => p.y));
let maxY2 = Math.max(...poly2.map(p => p.y));

// 检测边界框是否相交
if (maxX1 < minX2 || maxX2 < minX1 || maxY1 < minY2 || maxY2 < minY1) {
return false; // 边界框不相交
}

return true; // 边界框相交
}
```

2. **点在多边形内检测**：如果边界框相交，则进一步检测点是否在多边形内部。

```javascript
// 点在多边形内检测函数
function pointInPolygon(point, polygon) {
let x = point.x;
let y = point.y;
let inside = false;
for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
let xi = polygon.x, yi = polygon.y;
let xj = polygon[j].x, yj = polygon[j].y;
let intersect = ((yi > y) != (yj > y)) &&
(x < (xj - xi) * (y - yi) / (yj - yi) + xi);
if (intersect) inside = !inside;
}
return inside;
}

// 检测两个多边形是否相交
function polygonsIntersect(poly1, poly2) {
// 先进行边界框检测
if (!boundingBoxIntersect(poly1, poly2)) {
return false;
}

// 检测 poly1 中的任意顶点是否在 poly2 中
for (let i = 0; i < poly1.length; i++) {
if (pointInPolygon(poly1, poly2)) {
return true;
}
}

// 检测 poly2 中的任意顶点是否在 poly1 中
for (let i = 0; i < poly2.length; i++) {
if (pointInPolygon(poly2, poly1)) {
return true;
}
}

return false; // 如果没有找到相交的点，则两个多边形不相交
}

// 测试两个多边形是否相交
console.log(polygonsIntersect(polygon1, polygon2)); // 输出 true 或 false
```

这段代码先利用 `boundingBoxIntersect` 函数检测两个多边形的边界框是否相交，如果边界框相交，则进一步使用 `pointInPolygon` 函数检测任意一个多边形的顶点是否在另一个多边形内部，从而确定是否相交。

### 方法二：分离轴定理（SAT）

另一种方法是使用分离轴定理（Separating Axis Theorem, SAT），它更复杂一些但在某些情况下可以提供更准确的结果。这里不具体展示代码，但可以参考分离轴定理的算法实现来进行多边形相交的判定。

以上是基于JavaScript的两种常用方法来判定两个多边形是否相交。

ejsoon · 帖子由 **ejsoon** » 2024年 7月 22日 14:14

代码：全选

// Polygon 1 vertices
const polygon1 = [
  { x: 30, y: 80 },
  { x: 60, y: 110 },
  { x: 90, y: 100 },
  { x: 80, y: 60 },
  { x: 40, y: 40 }
];

// Polygon 2 vertices
const polygon2 = [
  { x: 20, y: 30 },
  { x: 60, y: 20 },
  { x: 100, y: 40 },
  { x: 110, y: 80 },
  { x: 70, y: 100 },
  { x: 30, y: 70 }
];

// Function to check bounding box intersection
function boundingBoxIntersect(poly1, poly2) {
  // Calculate the bounding box of polygon 1
  let minX1 = Math.min(...poly1.map(p => p.x));
  let maxX1 = Math.max(...poly1.map(p => p.x));
  let minY1 = Math.min(...poly1.map(p => p.y));
  let maxY1 = Math.max(...poly1.map(p => p.y));

  // Calculate the bounding box of polygon 2
  let minX2 = Math.min(...poly2.map(p => p.x));
  let maxX2 = Math.max(...poly2.map(p => p.x));
  let minY2 = Math.min(...poly2.map(p => p.y));
  let maxY2 = Math.max(...poly2.map(p => p.y));

  // Check if bounding boxes intersect
  if (maxX1 < minX2 || maxX2 < minX1 || maxY1 < minY2 || maxY2 < minY1) {
    return false; // Bounding boxes do not intersect
  }
  
  return true; // Bounding boxes intersect
}

// Function to check if a point is inside a polygon
function pointInPolygon(point, polygon) {
  let x = point.x;
  let y = point.y;
  let inside = false;
  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    let xi = polygon[i].x, yi = polygon[i].y;
    let xj = polygon[j].x, yj = polygon[j].y;
    let intersect = ((yi > y) != (yj > y)) &&
                    (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
    if (intersect) inside = !inside;
  }
  return inside;
}

// Function to check if two polygons intersect
function polygonsIntersect(poly1, poly2) {
  // First perform bounding box check
  if (!boundingBoxIntersect(poly1, poly2)) {
    return false;
  }

  // Check if any vertex of poly1 is inside poly2
  for (let i = 0; i < poly1.length; i++) {
    if (pointInPolygon(poly1[i], poly2)) {
      return true;
    }
  }

  // Check if any vertex of poly2 is inside poly1
  for (let i = 0; i < poly2.length; i++) {
    if (pointInPolygon(poly2[i], poly1)) {
      return true;
    }
  }

  return false; // If no intersection found, polygons do not intersect
}

// Test if the two polygons intersect
console.log(polygonsIntersect(polygon1, polygon2)); // Output true or false

ejsoon · 帖子由 **ejsoon** » 2024年 7月 22日 17:50

當某個點 \( (x, y) \) 繞原點逆時針旋轉 \( a \) 度時，其坐標的變化可以用以下公式表示：

\[ (x', y') = (x \cos a - y \sin a, x \sin a + y \cos a) \]

這裡，\( (x', y') \) 是旋轉後點的新坐標，\( (x, y) \) 是原始點的坐標，\( a \) 是旋轉的角度（單位是度）。

如果 \( a \) 是正數，表示逆時針旋轉；如果 \( a \) 是負數，表示順時針旋轉。

CHATchatgpt：javascript檢測兩個多邊形是否交涉

CHATchatgpt：javascript檢測兩個多邊形是否交涉

Re: CHATchatgpt：javascript檢測兩個多邊形是否交涉

繞原點轉動

在线用户