通过删除不必要的点和堆叠形状来优化矢量图像
Ath*_*ari 7 algorithm vector-graphics mathematical-optimization path-finding
我需要优化带有由贝塞尔线构造的填充形状的矢量图像。输入图像以及形状分离后的外观：
我想通过删除不必要的线条并依靠形状堆叠来保留外观来优化图像，但顶点要少得多。结果形状应如下所示：
这个问题可能可以分解为单独的步骤：
检测堆叠线。这或多或少是简单的：计算沿线的点，沿它们找到顶点。如果顶点堆叠起来，它就变得微不足道了。
寻找穿过其他形状的填充区域的贝塞尔路径。可能已经存在这样的算法，但我不知道。（我在这里真的需要帮助。）而且还不清楚要采用什么形状。也许我应该解决所有的可能性并进行比较。一旦我了解了它，它可能会变得更清楚。（欢迎提供提示/建议。）
找到最佳的堆叠顺序以使顶点数量最少。对于像我这样不太热衷于算法的人来说，这听起来很痛苦，但这似乎是通过不同“路径”的顶点数量的某种最小化，所以可以做到。（如我错了请纠正我。）
如果一个形状中有一个洞，这可能意味着里面的所有东西都会堆叠在它的上面，所以这是一个单独的简单情况，不需要额外的计算。
总的来说，第二点似乎是最有（唯一？）问题的，所以我需要在正确的方向上推动。
就示例图像而言，如何找到绿色形状的潜在遮挡部分穿过蓝色形状（以及可选的黄色形状）的贝塞尔路径，反之亦然，让蓝色形状穿过绿色形状？我不需要路径是最短的，我需要它的顶点最少。
本质上，我需要找到这些具有最少顶点数的路径。请随意忽略其余内容，将其视为不相关的上下文。
我在这里看到了多个本身就很困难的问题。一些想法：
\n直接使用 B\xc3\xa9zier 曲线似乎很困难。我的建议是用多边形或一对多边形来近似它们，一个是采样的，一个是内切的。如果是后者，您\xe2\x80\x99将需要考虑曲线的二阶导数来确定它\xe2\x80\x99是凸的还是凹的，或者它是否从一个过渡到另一个（如果所以）。
\n曲线方向可以识别孔。如果边界曲线的方向使得右侧位于形状内部，则逆时针曲线表示孔。对于简单的 B\xc3\xa9zier 形状，包含相应顺时针边界部分的每个形状都必须堆叠在前面。简单多边形的顺时针/逆时针方向可以通过有符号面积来测试。
\n曲线简化是一个最短路径问题， but the metric is not Euclidean. Suppose that we know the stacking order of some simple polygons. Given one of these polygons P, we form the polygon Q consisting of the union of P and every polygon in front of P that intersects it. We want to continuously deform the parts of the boundary of P that lie in the interior of Q so as to minimize the number of edges. For each part, we should be able to simulate a breadth-first search from one endpoint to the other in the implicit infinite graph via visibility algorithms.
\n优化堆叠顺序感觉是 NP 困难的。 I haven\xe2\x80\x99t worked out a reduction; this is just my gut feeling as a credentialed algorithm designer knowing that a seemingly simpler ordering problem \xe2\x80\x93 feedback arc set \xe2\x80\x93 is NP-hard, and that simple polygons offer a lot of freedom for constructing gadgets. My suggestion in practice would be to compute the convex hull of each polygon and declare that the order of two polygons whose hulls do not intersect does not matter. Take the complement of this graph and enumerate its orientations that do not contain a cycle (there are efficient algorithms for this). For each orientation, perform a topological sort to extend it to a total order and then optimize the curves accordingly. If this is still too expensive, I\xe2\x80\x99d reach for a genetic algorithm, specifically BRKGA with the natural decoder (each chromosome contains one number per shape; sort the shapes by number).
\n- @Athari方向：https://cs.stackexchange.com/questions/24171/algorithm-to-find-all-acycl-orientations-of-a-graph。尽可能远：https://en.wikipedia.org/wiki/Medial_axis。可见性：https://en.wikipedia.org/wiki/Visibility_polygon。 (2认同)