代码： 全选
以下是一個 JavaScript 方法，用於判斷兩個多邊形是否有邊相交。方法會遍歷兩個多邊形的所有邊，並使用前述的線段相交算法進行檢查。如果發現相交，則立即返回 `true`；否則，檢查完所有邊後返回 `false`。這裡還加入了公差 `z`，用於處理浮點數計算的精度問題（例如判斷點是否在線上時的近似處理）。
```javascript
// 判斷單一線段是否相交（帶公差 z）
function doSegmentsIntersect(x0, y0, x1, y1, x2, y2, x3, y3, z) {
// 計算叉積
function crossProduct(x1, y1, x2, y2, x3, y3) {
return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}
// 檢查範圍是否重疊
function overlap(min1, max1, min2, max2) {
return min1 - z <= max2 && min2 - z <= max1;
}
const d1 = crossProduct(x0, y0, x1, y1, x2, y2);
const d2 = crossProduct(x0, y0, x1, y1, x3, y3);
const d3 = crossProduct(x2, y2, x3, y3, x0, y0);
const d4 = crossProduct(x2, y2, x3, y3, x1, y1);
// 一般情況：符號相反表示相交（考慮公差 z）
if ((d1 > z && d2 < -z) || (d1 < -z && d2 > z)) {
if ((d3 > z && d4 < -z) || (d3 < -z && d4 > z)) {
return true;
}
}
// 共線情況：所有叉積接近 0（在公差 z 內）
if (Math.abs(d1) <= z && Math.abs(d2) <= z && Math.abs(d3) <= z && Math.abs(d4) <= z) {
const minX1 = Math.min(x0, x1);
const maxX1 = Math.max(x0, x1);
const minY1 = Math.min(y0, y1);
const maxY1 = Math.max(y0, y1);
const minX2 = Math.min(x2, x3);
const maxX2 = Math.max(x2, x3);
const minY2 = Math.min(y2, y3);
const maxY2 = Math.max(y2, y3);
return overlap(minX1, maxX1, minX2, maxX2) && overlap(minY1, maxY1, minY2, maxY2);
}
return false;
}
// 判斷兩個多邊形是否有邊相交
function doPolygonsIntersect(polygonA, polygonB, z = 1e-10) {
// 將多邊形轉為邊的起點和終點數組
const edgesA = [];
const edgesB = [];
// 多邊形 A 的邊
for (let i = 0; i < polygonA.length; i++) {
const next = (i + 1) % polygonA.length; // 閉合多邊形
edgesA.push({
x0: polygonA[i][0],
y0: polygonA[i][1],
x1: polygonA[next][0],
y1: polygonA[next][1]
});
}
// 多邊形 B 的邊
for (let i = 0; i < polygonB.length; i++) {
const next = (i + 1) % polygonB.length; // 閉合多邊形
edgesB.push({
x0: polygonB[i][0],
y0: polygonB[i][1],
x1: polygonB[next][0],
y1: polygonB[next][1]
});
}
// 遍歷所有邊對，檢查是否相交
for (const edgeA of edgesA) {
for (const edgeB of edgesB) {
if (doSegmentsIntersect(
edgeA.x0, edgeA.y0, edgeA.x1, edgeA.y1,
edgeB.x0, edgeB.y0, edgeB.x1, edgeB.y1,
z
)) {
return true; // 一旦發現相交，立即返回 true
}
}
}
return false; // 無相交邊
}
// 測試範例
const polygonA = [[0, 0], [2, 0], [2, 2], [0, 2]]; // 矩形
const polygonB = [[1, 1], [3, 1], [3, 3], [1, 3]]; // 另一矩形，相交
const polygonC = [[3, 3], [5, 3], [5, 5], [3, 5]]; // 不相交
console.log(doPolygonsIntersect(polygonA, polygonB, 1e-10)); // true
console.log(doPolygonsIntersect(polygonA, polygonC, 1e-10)); // false
```
### 代碼說明
1. **`doSegmentsIntersect`**：
- 修改了之前的線段相交函數，加入公差 `z`，用於處理浮點數精度問題。
- 當叉積的絕對值小於 `z` 時，視為 0（共線）；大於 `z` 或小於 `-z` 用於符號判斷。
- 共線時，使用範圍檢查，並在比較時考慮公差。
2. **`doPolygonsIntersect`**：
- 輸入：兩個多邊形的頂點數組（格式為 `[[x0, y0], [x1, y1], ...]`）和公差 `z`（默認為 `1e-10`）。
- 將多邊形分解為邊的集合，考慮閉合（首尾相連）。
- 雙重循環遍歷兩個多邊形的所有邊對，調用 `doSegmentsIntersect` 檢查是否相交。
- 一旦發現相交，立即返回 `true`；否則遍歷完後返回 `false`。
3. **公差 `z`**：
- 用於處理浮點數計算的誤差，例如點是否在線上的判斷。
- 默認值 `1e-10` 適用於大多數情況，可根據需要調整。
### 測試案例
- `polygonA` 和 `polygonB` 是兩個相交的矩形，返回 `true`。
- `polygonA` 和 `polygonC` 是不相交的矩形，返回 `false`。
這個方法高效且穩定，適用於任意凸或凹多邊形的邊相交檢測。