?

import { FaceNode } from "chili";
import {IDocument,IEdge,Logger,ShapeNode,XYZ
} from "chili-core";
import { Graph } from "graphlib";
function pointToString(point: XYZ): string {return `${point.x.toFixed(0)}-${point.y.toFixed(0)}-${point.z.toFixed(0)}`;}
function buildGraphFromEdges(edges: IEdge[]
): { graph: Graph; edgeIndexMap: Map<string, number[]> } {const graph = new Graph({ directed: false });const edgeIndexMap = new Map<string, number[]>();edges.forEach((edge, index) => {const start = pointToString(edge.curve().startPoint());const end = pointToString(edge.curve().endPoint());graph.setEdge(start, end);if (!edgeIndexMap.has(start)) edgeIndexMap.set(start, []);if (!edgeIndexMap.has(end)) edgeIndexMap.set(end, []);edgeIndexMap.get(start)!.push(index);edgeIndexMap.get(end)!.push(index);});return { graph, edgeIndexMap };
}
function findCyclesWithEdgeIndices(graph: Graph,edgeIndexMap: Map<string, number[]>
): { nodeCycles: string[][]; edgeCycles: number[][] } {const nodeCycles: string[][] = [];const edgeCycles: number[][] = [];const addedCycles = new Set<string>(); // 新增：用于記錄已添加的環路徑for (const start of graph.nodes()) {const stack: { current: string; path: string[]; visited: Set<string> }[] = [];stack.push({ current: start, path: [], visited: new Set() });while (stack.length > 0) {const { current, path, visited } = stack.pop()!;if (visited.has(current)) continue;const newPath = [...path, current];const newVisited = new Set(visited);newVisited.add(current);const neighbors = graph.neighbors(current) || [];for (const neighbor of neighbors) {if (newPath.length > 1 && newPath[newPath.length - 2] === neighbor) {continue;}if (neighbor === start && newPath.length >= 3) {// 構造唯一標識符并判斷是否重復const cycleKey = [...newPath].sort().join('-');if (!addedCycles.has(cycleKey)) {nodeCycles.push(newPath);addedCycles.add(cycleKey); // 標記為已添加// 提取邊索引邏輯const edgeIndices = new Set<number>();for (let i = 0; i < newPath.length; i++) {const a = newPath[i];const b = newPath[(i + 1) % newPath.length];const indicesA = edgeIndexMap.get(a) || [];const indicesB = edgeIndexMap.get(b) || [];const common = indicesA.filter((idx) => indicesB.includes(idx));common.forEach((idx) => edgeIndices.add(idx));}edgeCycles.push([...edgeIndices]);}} else if (!newVisited.has(neighbor)) {stack.push({current: neighbor,path: newPath,visited: newVisited,});}}}}return { nodeCycles, edgeCycles };
}
function isPointsCoplanar(points: XYZ[]): boolean {if (points.length <= 3) return true; // 3個點或更少一定共面const p0 = points[0];const p1 = points[1];const p2 = points[2];// 計算平面的法向量const v1 =new XYZ(p1.x - p0.x,p1.y - p0.y,p1.z - p0.z) ;const v2 =new XYZ(p2.x - p0.x,p2.y - p0.y,p2.z - p0.z ) ;const normal = crossProduct(v1, v2);// 平面方程 ax + by + cz + d = 0const a = normal.x;const b = normal.y;const c = normal.z;const d = -(a * p0.x + b * p0.y + c * p0.z);for (let i = 3; i < points.length; i++) {const p = points[i];const distance = Math.abs(a * p.x + b * p.y + c * p.z + d);if (distance > Number.EPSILON) {return false; // 點不共面}}return true;
}// 向量叉乘
function crossProduct(v1: XYZ, v2: XYZ): XYZ {const xyz=new XYZ(  v1.y * v2.z - v1.z * v2.y,v1.z * v2.x - v1.x * v2.z,v1.x * v2.y - v1.y * v2.x,)return xyz;
}
function addUniquePoint(point: XYZ, set: Set<string>, list: XYZ[]) {const key = `${point.x},${point.y},${point.z}`;if (!set.has(key)) {set.add(key);list.push(point);}
}
// 提取邊中的點
function extractPointsFromEdges(edges: IEdge[]): XYZ[] {const pointsSet = new Set<string>();const pointsList: XYZ[] = [];edges.forEach(edge => {const start = edge.curve().startPoint();const end = edge.curve().endPoint();addUniquePoint(start, pointsSet, pointsList);addUniquePoint(end, pointsSet, pointsList);});return pointsList;
}
export function face_rebuild(document: IDocument): void {const models=document.selection.getSelectedNodes().map((x) => x as ShapeNode).filter((x) => {if (x === undefined) return false;let shape = x.shape.value;if (shape === undefined) return false;return true;});document.selection.clearSelection();const edges = models.map((x) => x.shape.value.copy()) as IEdge[];  const { graph, edgeIndexMap } = buildGraphFromEdges(edges);
const { nodeCycles, edgeCycles } = findCyclesWithEdgeIndices(graph, edgeIndexMap);
const addedCycles = new Set<string>(); // 用于跟蹤已添加的環
const validEdgeCycles = edgeCycles.filter((cycle, i) => nodeCycles[i].length >= 4);
Logger.info("Edge Cycles:", validEdgeCycles);for (let i = 0; i < validEdgeCycles .length; i++) {const edgeCycle = validEdgeCycles [i];const nodeCycle = nodeCycles[i];// 提取該環涉及的所有邊const cycleEdges = edgeCycle.map(index => edges[index]);// 判斷這些邊是否共面const points = extractPointsFromEdges(cycleEdges);const isCoplanar = isPointsCoplanar(points);if (isCoplanar) {document.addNode(new FaceNode(document, cycleEdges));} else {Logger.info(`Skipped non-coplanar cycle (edges: ${edgeCycle.join(",")}):`, nodeCycle.join(" → "));}
}}

多了一個面少了一個面

問題應該是出在取點沒有按edge順序導致面不準確

---

---

8條邊輸出了10條

完美

import { FaceNode } from "chili";
import {IDocument,IEdge,Logger,ShapeNode,XYZ
} from "chili-core";
import { Graph } from "graphlib";
function pointToString(point: XYZ): string {return `${point.x.toFixed(1)}-${point.y.toFixed(1)}-${point.z.toFixed(1)}`;}
function buildGraphFromEdges(edges: IEdge[]
): { graph: Graph; edgeIndexMap: Map<string, number[]> } {const graph = new Graph({ directed: false });const edgeIndexMap = new Map<string, number[]>();const edgePairSet = new Map<string, number>(); // 新增：記錄已添加的邊對edges.forEach((edge, index) => {const start = pointToString(edge.curve().startPoint());const end = pointToString(edge.curve().endPoint());// 構建唯一鍵，保證無向邊的唯一性（無論起點終點順序）const key = [start, end].sort().join('|');// 如果該邊對已經存在，則不再重復添加圖邊if (!edgePairSet.has(key)) {graph.setEdge(start, end);edgePairSet.set(key, index);}// 維護每個點對應的邊索引if (!edgeIndexMap.has(start)) edgeIndexMap.set(start, []);if (!edgeIndexMap.has(end)) edgeIndexMap.set(end, []);edgeIndexMap.get(start)!.push(index);edgeIndexMap.get(end)!.push(index);});return { graph, edgeIndexMap };
}
function findCyclesWithEdgeIndices(graph: Graph,edgeIndexMap: Map<string, number[]>
): { nodeCycles: string[][]; edgeCycles: number[][] } {const nodeCycles: string[][] = [];const edgeCycles: number[][] = [];const addedCycles = new Set<string>(); // 記錄已添加的環路徑const usedEdgesInCycles = new Set<string>(); // 記錄所有已被使用的邊組合for (const start of graph.nodes()) {const stack: { current: string; path: string[]; visited: Set<string> }[] = [];stack.push({ current: start, path: [], visited: new Set() });while (stack.length > 0) {const { current, path, visited } = stack.pop()!;if (visited.has(current)) continue;const newPath = [...path, current];const newVisited = new Set(visited);newVisited.add(current);const neighbors = graph.neighbors(current) || [];for (const neighbor of neighbors) {// 跳過回頭路（避免 A → B → A）if (newPath.length > 1 && newPath[newPath.length - 2] === neighbor) {continue;}// 檢查是否回到起點并形成環if (neighbor === start && newPath.length >= 3) {// 構造唯一標識符（排序節點）用于去重const cycleKey = [...newPath].sort().join('-');if (!addedCycles.has(cycleKey)) {nodeCycles.push(newPath);addedCycles.add(cycleKey); // 標記為已添加// 提取邊索引，并確保每條邊只用一次const edgeIndices = new Set<number>();const usedEdgesInThisCycle = new Set<string>(); // 當前環中已使用的邊for (let i = 0; i < newPath.length; i++) {const a = newPath[i];const b = newPath[(i + 1) % newPath.length];// 邊的唯一標識（無向）const edgeKey = [a, b].sort().join('|');// 如果這條邊已經被這個環使用過，則跳過if (usedEdgesInThisCycle.has(edgeKey)) continue;// 獲取共享該邊的索引const indicesA = edgeIndexMap.get(a) || [];const indicesB = edgeIndexMap.get(b) || [];const common = indicesA.filter((idx) => indicesB.includes(idx));if (common.length > 0) {edgeIndices.add(common[0]); // 使用第一個匹配的邊索引usedEdgesInThisCycle.add(edgeKey); // 當前環中標記為已使用usedEdgesInCycles.add(edgeKey);   // 全局標記為已使用}}edgeCycles.push([...edgeIndices]);}} else if (!newVisited.has(neighbor)) {// 繼續深度優先搜索stack.push({current: neighbor,path: newPath,visited: newVisited,});}}}}return { nodeCycles, edgeCycles };
}
function isPointsCoplanar(points: XYZ[]): boolean {if (points.length <= 3) return true; // 3個點或更少一定共面const p0 = points[0];const p1 = points[1];const p2 = points[2];// 計算平面的法向量const v1 =new XYZ(p1.x - p0.x,p1.y - p0.y,p1.z - p0.z) ;const v2 =new XYZ(p2.x - p0.x,p2.y - p0.y,p2.z - p0.z ) ;const normal = crossProduct(v1, v2);// 平面方程 ax + by + cz + d = 0const a = normal.x;const b = normal.y;const c = normal.z;const d = -(a * p0.x + b * p0.y + c * p0.z);for (let i = 3; i < points.length; i++) {const p = points[i];const distance = Math.abs(a * p.x + b * p.y + c * p.z + d);if (distance > Number.EPSILON) {return false; // 點不共面}}return true;
}// 向量叉乘
function crossProduct(v1: XYZ, v2: XYZ): XYZ {const xyz=new XYZ(  v1.y * v2.z - v1.z * v2.y,v1.z * v2.x - v1.x * v2.z,v1.x * v2.y - v1.y * v2.x,)return xyz;
}
function addUniquePoint(point: XYZ, set: Set<string>, list: XYZ[]) {const key = `${point.x},${point.y},${point.z}`;if (!set.has(key)) {set.add(key);list.push(point);}
}
// 提取邊中的點
function extractPointsFromEdges(edges: IEdge[]): XYZ[] {const pointsSet = new Set<string>();const pointsList: XYZ[] = [];edges.forEach(edge => {const start = edge.curve().startPoint();const end = edge.curve().endPoint();addUniquePoint(start, pointsSet, pointsList);addUniquePoint(end, pointsSet, pointsList);});return pointsList;
}
export function face_rebuild(document: IDocument): void {const models=document.selection.getSelectedNodes().map((x) => x as ShapeNode).filter((x) => {if (x === undefined) return false;let shape = x.shape.value;if (shape === undefined) return false;return true;});document.selection.clearSelection();const edges = models.map((x) => x.shape.value.copy()) as IEdge[];  const { graph, edgeIndexMap } = buildGraphFromEdges(edges);
const { nodeCycles, edgeCycles } = findCyclesWithEdgeIndices(graph, edgeIndexMap);
const addedCycles = new Set<string>(); // 用于跟蹤已添加的環
const validEdgeCycles = edgeCycles.filter((cycle, i) => nodeCycles[i].length >= 4);
//Logger.info("Edge Cycles:", validEdgeCycles);for (let i = 0; i < validEdgeCycles .length; i++) {const edgeCycle = validEdgeCycles [i];const nodeCycle = nodeCycles[i];// 提取該環涉及的所有邊const cycleEdges = edgeCycle.map(index => edges[index]);// 判斷這些邊是否共面const points = extractPointsFromEdges(cycleEdges);const isCoplanar = isPointsCoplanar(points);if (isCoplanar) {Logger.info(`Rebuilding face (edges: ${edgeCycle.join(",")}):`, nodeCycle.join(" → "));cycleEdges.map(edge => (Logger.info(`  ${pointToString(edge.curve().startPoint())} → ${pointToString(edge.curve().endPoint())}`)));document.addNode(new FaceNode(document, cycleEdges));} else {//  Logger.info(`Skipped non-coplanar cycle (edges: ${edgeCycle.join(",")}):`, nodeCycle.join(" → "));}
}}