填充闭合2D曲线的算法 [英] Algorithm to Fill In a Closed 2D Curve

问题描述

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

I need to find a way of drawing the inside of a closed 2D curve. This curve is actually created using a bicubic Bezier curve, but that's not important I believe.

目前，绘制的形状中应该没有孔".这样就可以完全填充它了.似乎受约束的Delaunay三角剖分是可行的方法?但是似乎有不同的方法可以做到这一点.我正在寻找一种快速简单的解决方案(但将实现使之正常运行所需的功能).

At the moment there should be no "holes" within the drawn shape. So it will just be totally filled in. It seems like constrained Delaunay triangulation would be the way to go? But there seems to be different ways of doing this. I am looking for a quick and simple solution (but will implement what's needed to make it working).

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

Programs such as Illustrator have that sort of feature (or SVG -- with the option fill).

我正在寻找:

• 做到这一点的技术
• 将我指向说明算法的论文/文档
• 某个地方有SVG渲染器的源代码吗?

• 该应用程序使用OpenGL.我自己画曲线.只需找到一种填充方式即可.
• 形状可以是凹形或凸形

推荐答案

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

Polygons can be filled using the Scanline method. The principle is easy: move an horizontal line and keep a list of the edges it meets. It is called the active list. Then join the intersections from left to right, in pairs. When the edges are sorted by increasing ordinate, the update of the active list from one scanline to the next can be done efficiently.

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

This works with concave/convex polygons and polygons with holes, and even crossed ones.

要填充贝塞尔曲线路径，可以将其展平，即将其变为多边的多边形.

To fill a Bezier path, you can flatten it, i.e. turn it to a polygon of many sides.

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

A direct approach is also possible, based on the scanline idea: first decompose the Bezier curves in monotone sections, i.e. portions that meet on horizontal line only once. This can be done analytically for cubic Beziers by detecting the curve maxima and minima (the equation is quadratic).

现在，知道每边有一个交点，就可以将曲线多边形完全视为多边形.计算交点有一个微妙的地方.但是，由于您知道Bezier弧线(相同端点之间的线段)非常近似，并且可以从一条扫描线到下一条扫描线递增地更新相交点，因此这一事实得到了缓解.

Now you can treat the curvilinear polygon exactly as a polygon, knowing that you have one intersection per side. There is a slightly delicate point, computing the intersection. But this is eased by the fact that you know a good approximation of the Bezier arc (the line segment between the same endpoints), and you can update the intersection incrementally, from one scanline to the next.

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

On the picture, the original endpoints appear in blue. Splitting endoints have been added to obtain monotone sections (the other control points are omitted). The dotted lines shows the polygon that approximates the shape and has the same topology (same active list, same number of intersections with the scanlines).

这篇关于填充闭合2D曲线的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！