Delaunay + Kruskal 未知零点

Question

我在 delaunay 图上应用 Kruskal 算法后读取边缘时出现奇怪的行为。在显示结果边时，有时某些边的一个点可能是一个点（总是（0,0）），而该点没有被添加到图形点中。有人知道这是从哪里来的吗？

for (i = 0; i < Max; i++)
{
    vertices.push_back(m_boostVector(data[i].x, data.y));
}
dt.insert(vertices.begin(), vertices.end());

for (index = 0, boost::tie(vit, ve) = boost::vertices(ft); vit != ve; vit++, index++)
{
    vertex_id_map[*vit] = index;
}

boost::kruskal_minimum_spanning_tree(dt, std::back_inserter(mst), vertex_index_map(vertex_index_pmap));

for (std::list<edge_descriptor>::iterator it = mst.begin(); it != mst.end(); it++)
{
    Delaunay::Vertex_handle sv = boost::source(*it, ft);
    Delaunay::Vertex_handle tv = boost::target(*it, ft);
}

谢谢

Answer 1

如果您没有过滤无限边，那么您最终可能会访问无限顶点。请参阅以下 section，其中包含一个说明如何执行此操作的示例。

Delaunay + Kruskal 未知零点

Delaunay + Kruskal unknown zero point

boost

cgal