CGAL 安排：计算折线与网格的有序交集
CGAL arrangements: compute the ordered intersection of a polyline with a grid
给定一条通用折线和一个正交网格，我想计算一条更简单的折线，其顶点位于网格上 edges/vertices。这可能看起来像这样：
Left: A dense polyline as input, Right: A coarser polyline whose vertices lie on the intersection of the input polyline with the grid edges/vertices
（抱歉图像 link，但堆栈溢出显然不允许我在获得 10 个学分之前嵌入图片）。
网格始终是正交的，但其顶点不一定具有整数坐标，因为一些 x 或 y 线可能具有由先前的几何交集计算定义的坐标。初始曲线可以表示为多段线（尽管也有贝塞尔曲线支持会很好），不一定是 x-monotone，它也可能沿着整个边缘与网格相交。
我的第一个想法是用我添加的网格线和曲线调用 CGAL::compute_subcurves(..)。我希望得到一个多段线列表，每条多段线由原始网格的一个面内的最大多段组成。实际上，即使输入由折线组成，输出由单调折线组成，我也会得到一个分隔线段的列表。这些还包括网格线段和多段线线段，并且这些线段未根据需要按 "walking on the curve segments" 排序以计算有序交点。如果它们是有序的，一个解决方案是迭代地检查它们并检查哪个与原始网格相交，然后保存这些点。
我想到的另一个选择是从网格线的排列开始，逐渐添加折线段，并有一个通知机制通知我在其内部成对不相交的新边缘，但在这种情况下边缘相交的多段线是网格的原始边缘我不会收到通知，我会错过它。递增地添加段和检查冲突似乎也并不简单，因为排列 API do_intersect(..) 似乎最多 return 一个点，而给定的段输入折线可能很容易与拐角处的两条网格线相交，甚至完全位于网格段上。
我可能遗漏了一些简单的解决方案。有人可以给我指点，或者一些 api 可能对这里有帮助的电话吗？
编辑：可能存在混淆。网格是正交的，但不一定是规则的，并且可能具有无法全局缩放为整数的坐标，例如 here.
使用Arrangement_with_history_2（而不是Arrangement_2）；参见 https://doc.cgal.org/latest/Arrangement_on_surface_2/classCGAL_1_1Arrangement__with__history__2.html。计算排列后，您可以使用点定位来定位排列中多段线的端点。然后，对于每一个，您都可以轻松地遵循原始曲线。如果您关心性能，您可以尝试（至少）增量插入网格线。另一种选择是扩展半边记录并分别插入网格线和每条折线。使用适当的观察器，您可以标记与给定折线唯一对应的生成的半边。我认为您甚至可以通过在插入多段线之前定位多段线的两个端点之一，然后将结果位置提供给（增量）插入函数来保存额外的点位置。
给定一条通用折线和一个正交网格，我想计算一条更简单的折线，其顶点位于网格上 edges/vertices。这可能看起来像这样：
Left: A dense polyline as input, Right: A coarser polyline whose vertices lie on the intersection of the input polyline with the grid edges/vertices
（抱歉图像 link，但堆栈溢出显然不允许我在获得 10 个学分之前嵌入图片）。
网格始终是正交的，但其顶点不一定具有整数坐标，因为一些 x 或 y 线可能具有由先前的几何交集计算定义的坐标。初始曲线可以表示为多段线（尽管也有贝塞尔曲线支持会很好），不一定是 x-monotone，它也可能沿着整个边缘与网格相交。
我的第一个想法是用我添加的网格线和曲线调用 CGAL::compute_subcurves(..)。我希望得到一个多段线列表，每条多段线由原始网格的一个面内的最大多段组成。实际上，即使输入由折线组成，输出由单调折线组成，我也会得到一个分隔线段的列表。这些还包括网格线段和多段线线段，并且这些线段未根据需要按 "walking on the curve segments" 排序以计算有序交点。如果它们是有序的，一个解决方案是迭代地检查它们并检查哪个与原始网格相交，然后保存这些点。
我想到的另一个选择是从网格线的排列开始，逐渐添加折线段，并有一个通知机制通知我在其内部成对不相交的新边缘，但在这种情况下边缘相交的多段线是网格的原始边缘我不会收到通知，我会错过它。递增地添加段和检查冲突似乎也并不简单，因为排列 API do_intersect(..) 似乎最多 return 一个点，而给定的段输入折线可能很容易与拐角处的两条网格线相交，甚至完全位于网格段上。
我可能遗漏了一些简单的解决方案。有人可以给我指点，或者一些 api 可能对这里有帮助的电话吗？
编辑：可能存在混淆。网格是正交的，但不一定是规则的，并且可能具有无法全局缩放为整数的坐标，例如 here.
使用Arrangement_with_history_2（而不是Arrangement_2）；参见 https://doc.cgal.org/latest/Arrangement_on_surface_2/classCGAL_1_1Arrangement__with__history__2.html。计算排列后，您可以使用点定位来定位排列中多段线的端点。然后，对于每一个，您都可以轻松地遵循原始曲线。如果您关心性能，您可以尝试（至少）增量插入网格线。另一种选择是扩展半边记录并分别插入网格线和每条折线。使用适当的观察器，您可以标记与给定折线唯一对应的生成的半边。我认为您甚至可以通过在插入多段线之前定位多段线的两个端点之一，然后将结果位置提供给（增量）插入函数来保存额外的点位置。