提问人：George Reith 提问时间：11/9/2023 最后编辑：George Reith 更新时间：11/10/2023 访问量：37
从线段生成晶格图
Generating a lattice graph from line segments
问：
我有两个矩形，我试图在它们之间找到一条视觉上令人愉悦的纯直线路线。
为此，我想生成以下格子/网格作为图形结构（连接到其他顶点的顶点列表），以便我可以在其上运行像 Djikstra 这样的寻路算法：
这是通过填充每个矩形以获得一个新矩形（上面的红色和蓝色）来获得的，并取这些新矩形的边界框（绿色）。然后从矩形每边的中心投射光线，并细分这些矩形接触的线条。
但是，我在研究如何以有效的方式将此晶格生成为图形结构时遇到了麻烦。
理想情况下，我正在寻找一种算法和数据结构，使我能够逐条线段构建图形线段，将现有线段（边）细分为新线段相交的地方。
答：
0赞
George Reith
11/10/2023
#1
我通过以不同的方式解决这个问题找到了解决方案。我没有用线思考，而是从线的起点和终点以及它们的交叉点收集了所有点。
然后，我将每个唯一点作为节点添加到图形中。
然后，我为我所有节点中所有唯一的 X 值中的每一个都做了一个集合，并为 Y 值做了另一个集合。
我按升序对这些集合进行了排序。
然后，我遍历了 X 和 Y 值的每个可能组合（搜索空间很小，因为创建交点的所有线都是正交的）。
当我找到一个节点时，我向后迭代 X 值，直到我命中另一个节点并链接它们，然后对 Y 值执行相同的操作。
这是我生成的代码：
function pointId(x: number, y: number) {
return `${x},${y}`;
}
function pointsToGraph(points: Point[]) {
const xValues: Set<number> = new Set();
const yValues: Set<number> = new Set();
const graph = createGraph<{ point: Point }>();
points.forEach((point) => {
const [x, y] = point;
xValues.add(x);
yValues.add(y);
graph.addNode(pointId(x, y), { point });
});
const sortedXValues = Array.from(xValues).sort((a, b) => a - b);
const sortedYValues = Array.from(yValues).sort((a, b) => a - b);
for (let i = 0; i < sortedYValues.length; i++) {
for (let j = 0; j < sortedXValues.length; j++) {
const x = sortedXValues[j];
const y = sortedYValues[i];
const currentId = pointId(x, y);
// eslint-disable-next-line no-continue
if (!graph.hasNode(currentId)) continue;
for (let k = j - 1; k >= 0; k--) {
const previousXId = pointId(sortedXValues[k], y);
if (graph.hasNode(previousXId)) {
graph.addLink(previousXId, currentId);
break;
}
}
for (let k = i - 1; k >= 0; k--) {
const previousYId = pointId(x, sortedYValues[k]);
if (graph.hasNode(previousYId)) {
graph.addLink(previousYId, currentId);
break;
}
}
}
}
return graph;
}
评论