填充闭合二维曲线的算法

Question

我需要找到一种绘制封闭的2D曲线内部的方法.这条曲线实际上是使用双三次贝塞尔曲线创建的,但我认为这并不重要.

此刻绘制的形状内不应有"洞".所以它将被完全填补.似乎受限制的Delaunay三角测量将是要走的路？但似乎有不同的方法来做到这一点.我正在寻找一个快速而简单的解决方案(但将实现使其工作所需的内容).

像Illustrator这样的程序具有这种功能(或SVG - 带有选项填充).

我在寻找:

• 这样做的技巧
• 请指出解释算法的纸张/文档
• 是某个SVG渲染器的源代码？

编辑:

• 该应用程序使用OpenGL.我自己绘制曲线.只需要找到一种填充它们的方法.
• 形状可以是凹形或凸形

Answer 1

可以使用Scanline方法填充多边形.原理很简单:移动水平线并保持其遇到的边缘列表.它被称为活动列表.然后成对地从左到右连接交叉点.当通过增加纵坐标对边进行排序时,可以有效地完成从一条扫描线到下一条扫描线的活动列表的更新.

这适用于凹/凸多边形和带孔的多边形,甚至是交叉的多边形.

要填充Bezier路径,可以将其展平,即将其转换为多边形的多边形.

基于扫描线的想法,直接方法也是可能的:首先在单调部分中分解贝塞尔曲线,即仅在水平线上相遇一次的部分.这可以通过检测曲线最大值和最小值(方程是二次的)来分析地对于三次贝塞尔曲线来完成.

现在,您可以将曲线多边形精确地视为多边形,因为您知道每边有一个交点.计算交叉点时有一点点微妙.但是,通过您知道Bezier弧(相同端点之间的线段)的良好近似,您可以从一条扫描线到下一条扫描线逐步更新交点.

在图片上,原始端点显示为蓝色.已添加分裂的endoints以获得单调部分(省略其他控制点).虚线表示近似于形状并具有相同拓扑的多边形(相同的活动列表,与扫描线的交叉点数相同).