algorithm - 通过将多边形拖动为画笔来编辑矢量图像

Question

目标是通过像多边形画笔一样在屏幕上拖动鼠标来进行简单的矢量图像编辑，创建 Minkowski sum画笔和鼠标的路径。新的多边形将从任何先前存在的不同颜色的多边形中减去，并与任何现有的相同颜色的多边形合并。

计划是将每次鼠标移 Action 为从鼠标先前位置到当前位置的线段，计算该线段上的 Minkowski 和，然后使用 Weiler–Atherton clipping algorithm更新现有多边形以包含 Minkowski 和。

如果 Weiler–Atherton 为每次鼠标移动运行似乎可能会导致 UI 延迟，我们计划通过将其放入另一个线程来延迟该步骤，该线程可能需要时间来 catch 最新的鼠标移动，或者保存所有 Weiler–Atherton 计算直到绘图完成，然后在保存时将其作为批量操作执行。我们担心这可能会导致大量重叠多边形的积累，以至于 UI 会延迟渲染所有多边形所需的时间。

问题是:上面的计划是Inkscape和其他严肃的矢量图形编辑软件执行此操作的方式吗？这似乎是一个疯狂的计划，无论是算法的技巧还是计算的复杂性。专家会做什么？

正在考虑的另一个选项:使用简单的光栅操作进行绘画，然后将光栅转换为矢量图像作为最后一步。从光栅到矢量的转换似乎不亚于 Weiler–Atherton，而且最终输出的质量可能会受到影响，但它会是更好的选择吗？

Answer 1

当用户按住鼠标键绘图时，你可以记住所有的鼠标移动线段，并同时将画笔*线 Minkowski 和渲染为屏幕分辨率位图。

您可以使用位图绘制屏幕，​​直到用户释放按钮。届时，您可以计算所有线段 Minkowski 总和的并集，并将生成的形状添加到您的绘图中。

要同时计算这么多形状的并集，最好使用某种扫描线算法。您应该能够在 O(N log N) 或线性时间内完成这项工作，这不会造成任何明显的延迟。