贝塞尔路径加宽 [英] bezier path widening
问题描述
我有一条贝塞尔曲线 B，其中包含点 S、C1、C2、E 和一个代表宽度的正数 w.有没有办法快速计算两条贝塞尔曲线B1、B2的控制点，使得B1和B2之间的东西就是B表示的加宽路径?
更正式地:计算 B1、B2 的良好 Bezier 近似的控制点，其中B1 = {(x,y) + N(x,y)(w/2) |(x,y) 在 C}
B2 = {(x,y) - N(x,y)(w/2) |(x,y) in C},
其中 N(x,y) 是法线在 (x,y) 处的 C.
我说的是很好的近似值，因为 B1、B2 可能不是多项式曲线(我不确定它们是否是).
从数学的角度来看，贝塞尔曲线的精确平行是相当丑陋的(它需要 10 次多项式).
很容易做的是根据贝塞尔曲线的多边形近似计算加宽(即您从贝塞尔曲线计算线段，然后沿着曲线两侧的法线移动点).
如果您的厚度与曲率相比不是太大，这会给出很好的结果......远平行"本身就是一个怪物(甚至不容易找到什么是平行线的定义)一条能让每个人都开心的开放曲线).
一旦你的两侧有两条多段线，你可以做的是为这些路径找到一个最好的近似贝塞尔曲线，如果你需要那种表示的话.再一次，我认为对于正常情况"(即相当细的线)，即使只有一条贝塞尔曲线的两侧也应该非常准确(误差应该远小于线的粗细).
编辑:确实，即使在合理的正常情况下，使用单个贝塞尔曲线看起来也比我预期的要糟糕得多.我还尝试在每一侧使用两个贝塞尔弧，结果更好但仍然不完美.误差当然远小于线条的粗细，所以除非线条很粗，否则它可能是一个合理的选择.在下图中，它显示了加厚的贝塞尔曲线(每点加厚)，每边使用单个贝塞尔弧的近似值和每边使用两个贝塞尔弧的近似值.
EDIT 2:根据要求，我添加了用于获取图片的代码；它在 python 中，只需要 Qt.这段代码不应该被其他人阅读，所以我使用了一些可能不会在实际生产代码中使用的技巧.算法也非常低效，但我不在乎速度(这是一个一次性程序，看看这个想法是否可行).
<代码>## 此代码是在 ego-pumping 会话期间编写的# www.stackoverflow.com，同时尝试回复一个有趣的# 问题.随心所欲，但不要怪我# 不做*你*认为它应该做的事情，或者即使不做# *我*说它应该做什么.##当然欢迎评论...## 安德烈6502"格里菲尼## 要求:Qt 和 PyQt#导入系统从 PyQt4.Qt 导入 *QW = QWidget等级 = 5定义平均值(a，b):"""两个(x, y)点的平均值"""xa, ya = axb, yb = b返回 ((xa + xb)*0.5, (ya + yb)*0.5)def bez3split(p0, p1, p2,p3):"""给定贝塞尔三次弧的控制点，计算上半场控制点"""p01 = 平均(p0，p1)p12 = 平均(p1，p2)p23 = 平均(p2，p3)p012 = 平均(p01，p12)p123 = 平均(p12，p23)p0123 = 平均(p012，p123)返回 [(p0, p01, p012, p0123),(p0123, p123, p23, p3)]def bez3(p0, p1, p2, p3, levels=bezlevels):"""使用固定的建立贝塞尔三次弧近似半细分数."""如果级别 <= 0:返回 [p0, p3]别的:(a0, a1, a2, a3), (b0, b1, b2, b3) = bez3split(p0, p1, p2, p3)返回 (bez3(a0, a1, a2, a3, levels-1) +bez3(b0, b1, b2, b3, levels-1)[1:])defthickPath(pts, d):"""给定折线和距离计算近似值两条单边偏移曲线，并将其作为两个返回与输入的顶点数相同的折线.注意:快速而肮脏的方法，只是对每个使用正常"顶点计算为垂直于线段连接上一个和下一个顶点.不检查自相交(这些发生在局部曲率的距离太大)，没有检查用于退化输入(例如多个点)."""l1 = []l2 = []对于 xrange(len(pts)) 中的 i:i0 = max(0, i - 1) # 前一个索引i1 = min(len(pts) - 1, i + 1) # 下一个索引x, y = pts[i]x0, y0 = pts[i0]x1, y1 = pts[i1]dx = x1 - x0dy = y1 - y0L = (dx**2 + dy**2) ** 0.5nx = - d*dy/Lny = d*dx/Ll1.append((x - nx, y - ny))l2.append((x + nx, y + ny))返回 l1, l2def dist2(x0, y0, x1, y1):两点之间的平方距离"返回 (x1 - x0)**2 + (y1 - y0)**2定义距离(x0，y0，x1，y1):两点之间的距离"返回 ((x1 - x0)**2 + (y1 - y0)**2) ** 0.5def ibez(pts, levels=bezlevels):"""逆贝塞尔计算.给定一个点列表，计算一个点的控制点近似于它们的三次贝塞尔弧."""## 笔记:## 这是一个非常具体的例程，只有效# 如果输入是从计算中获得的# 具有级别"细分级别的贝塞尔弧# 因为计算距离是最大的# *对应点*的距离.# 请注意，对于来自输入的大"变化# 原来的贝塞尔曲线我不认为是真的# 曲线曲线匹配的最佳参数也将# 最小化对应的最大距离#点.对于更一般的输入更一般# 需要路径路径错误估计.## 最小化算法是对两者的逐步下降# 中间控制点以大约的步长开始# 输入长度的 1/10 到大约 1/1000.# 它又慢又丑，但不需要依赖和# 只是一堆代码行，所以我使用了它.## 注意这里有一个封闭形式的解法来寻找# 给定起始和的最佳贝塞尔近似值# 结束点和中间参数列表# 值和点，这个公式也可以是# 用于实现更快更准确# 一般情况下的逆贝塞尔曲线.# 如果你关心逆贝塞尔问题那么# 我很确定有更聪明的方法.## 这里使用的最小化很具体，很慢# 并没有那么准确.这不是生产质量的代码.# 你被警告了.## 从直线贝塞尔弧开始(当然不是# 最好的选择，但这只是一个玩具).x0, y0 = pts[0]x3, y3 = pts[-1]x1, y1 = (x0*3 + x3)/4.0, (y0*3 + y3)/4.0x2, y2 = (x0 + x3*3)/4.0, (y0 + y3*3)/4.0L = sum(dist(*(pts[i] + pts[i-1])) for i in xrange(len(pts) - 1))步长 = L/10限制 = 步数/100# 最小化函数 = max((a[i] - b[i])**2)定义错误(x0，y0，x1，y1，x2，y2，x3，y3):返回 max(dist2(*(x+p)) for x, p in zip(pts, bez3((x0, y0), (x1, y1),(x2, y2), (x3, y3),级别)))而步骤 >限制:最好 = 无对于 (-step, 0, step) 中的 dx1:对于 (-step, 0, step) 中的 dy1:对于 (-step, 0, step) 中的 dx2:对于 (-step, 0, step) 中的 dy2:e = 错误(x0，y0，x1+dx1, y1+dy1,x2+dx2, y2+dy2,x3, y3)如果最好是 None 或 e <最佳[0] * 0.9999:最佳 = e、dx1、dy1、dx2、dy2e, dx1, dy1, dx2, dy2 = 最好如果 (dx1, dy1, dx2, dy2) == (0, 0, 0, 0):# 我们达到了这一步的最小值 =>提炼步 *= 0.5别的:#我们还在继续x1 += dx1y1 += dy1x2 += dx2y2 += dy2返回 [(x0, y0), (x1, y1), (x2, y2), (x3, y3)]定义聚(pts):将 (x, y) 点列表转换为 QPolygonF)"返回 QPolygonF(map(lambda p: QPointF(*p), pts))类查看器(QW):def __init__(self, parent):QW.__init__(self, parent)self.pts = [(100, 100), (200, 100), (200, 200), (100, 200)]self.tracking = None # 鼠标拖动回调self.ibez = 0 # 加粗算法选择器定义大小提示(自我):返回 QSize(900, 700)def wheelEvent(self, e):# 移动轮子之间的变化# - 原始多边形加厚# - 单弧加厚# - 双弧加厚self.ibez = (self.ibez + 1) % 3自我更新()defpaintEvent(self, e):dc = QPainter(自我)dc.setRenderHints(QPainter.Antialiasing)# 首先构建曲线和多边形加厚pts = bez3(*self.pts)l1, l2 =thickPath(pts, 15)# 如果需要，应用逆贝塞尔计算如果 self.ibez == 1:# 单弧l1 = bez3(*ibez(l1))l2 = bez3(*ibez(l2))elif self.ibez == 2:# 双弧l1 = (bez3(*ibez(l1[:len(l1)/2+1], bezlevels-1)) +bez3(*ibez(l1[len(l1)/2:], bezlevels-1))[1:])l2 = (bez3(*ibez(l2[:len(l2)/2+1], bezlevels-1)) +bez3(*ibez(l2[len(l2)/2:], bezlevels-1))[1:])# 绘制结果dc.setBrush(QBrush(QColor(0, 255, 0)))dc.drawPolygon(poly(l1 + l2[::-1]))dc.drawPolyline(poly(pts))dc.drawPolyline(poly(self.pts))# 绘制控制点dc.setBrush(QBrush(QColor(255, 0, 0)))dc.setPen(QPen(Qt.NoPen))对于 x, y 在 self.pts 中:dc.drawEllipse(QRectF(x-3, y-3, 6, 6))# 显示已经使用的算法dc.setPen(QPen(QColor(0, 0, 0)))dc.drawText(20, 20,[多边形"、单弧"、双弧"][self.ibez])def mousePressEvent(self, e):# 找到最近的控制点i = min(range(len(self.pts)),key=lambda i: (e.x() - self.pts[i][0])**2 +(e.y() - self.pts[i][1])**2)# 设置鼠标拖动回调self.tracking = lambda p: self.pts.__setitem__(i, p)def mouseMoveEvent(self, e):如果自我跟踪:self.tracking((e.x(), e.y()))自我更新()def mouseReleaseEvent(self, e):self.tracking = 无# Qt 样板类 MyDialog(QDialog):def __init__(self, parent):QDialog.__init__(self, parent)self.ws = 查看者(自我)L = QVBoxLayout(self)L.addWidget(self.ws)self.setModal(真)自我展示()app = QApplication([])aa = MyDialog(无)aa.exec_()aa = 无
I have a bezier curve B with points S, C1, C2, E, and a positive number w representing width. Is there a way of quickly computing the control points of two bezier curves B1, B2 such that the stuff between B1 and B2 is the widened path represented by B?
More formally: compute the control points of good Bezier approximations to B1, B2, where
B1 = {(x,y) + N(x,y)(w/2) | (x,y) in C}
B2 = {(x,y) - N(x,y)(w/2) | (x,y) in C},
where N(x,y) is the normal
of C at (x,y).
I say good approximations because B1, B2 might not be polynomial curves (I'm not sure if they are).
The exact parallel of a bezier curve is quite ugly from a mathematical point of view (it requires 10th-degree polynomials).
What is easy to do is compute a widening from a polygonal approximation of the bezier (that is you compute line segments from the bezier and then move the points along the normals on the two sides of the curve).
This gives good results if your thickness isn't too big compared to the curvature... a "far parallel" instead is a monster on its own (and it's not even easy to find a definition of what is a parallel of an open curve that would make everyone happy).
Once you have two polylines for the two sides what you can do is finding a best approximating bezier for those paths if you need that representation. Once again I think that for "normal cases" (that is reasonably thin lines) even just a single bezier arc for each of the two sides should be quite accurate (the error should be much smaller than the thickness of the line).
EDIT: Indeed using a single bezier arc looks much worse than I would have expected even for reasonably normal cases. I tried also using two bezier arcs for each side and the result are better but still not perfect. The error is of course much smaller than the thickness of the line so unless lines are very thick it could be a reasonable option. In the following picture it's shown a thickened bezier (with per-point thickening), an approximation using a single bezier arc for each side and an approximation using two bezier arcs for each side.
EDIT 2: As requested I add the code I used to get the pictures; it's in python and requires only Qt. This code wasn't meant to be read by others so I used some tricks that probably I wouldn't use in real production code. The algorithm is also very inefficient but I didn't care about speed (this was meant to be a one-shot program to see if the idea works).
#
# This code has been written during an ego-pumping session on
# www.stackoverflow.com, while trying to reply to an interesting
# question. Do whatever you want with it but don't blame me if
# doesn't do what *you* think it should do or even if doesn't do
# what *I* say it should do.
#
# Comments of course are welcome...
#
# Andrea "6502" Griffini
#
# Requirements: Qt and PyQt
#
import sys
from PyQt4.Qt import *
QW = QWidget
bezlevels = 5
def avg(a, b):
"""Average of two (x, y) points"""
xa, ya = a
xb, yb = b
return ((xa + xb)*0.5, (ya + yb)*0.5)
def bez3split(p0, p1, p2,p3):
"""
Given the control points of a bezier cubic arc computes the
control points of first and second half
"""
p01 = avg(p0, p1)
p12 = avg(p1, p2)
p23 = avg(p2, p3)
p012 = avg(p01, p12)
p123 = avg(p12, p23)
p0123 = avg(p012, p123)
return [(p0, p01, p012, p0123),
(p0123, p123, p23, p3)]
def bez3(p0, p1, p2, p3, levels=bezlevels):
"""
Builds a bezier cubic arc approximation using a fixed
number of half subdivisions.
"""
if levels <= 0:
return [p0, p3]
else:
(a0, a1, a2, a3), (b0, b1, b2, b3) = bez3split(p0, p1, p2, p3)
return (bez3(a0, a1, a2, a3, levels-1) +
bez3(b0, b1, b2, b3, levels-1)[1:])
def thickPath(pts, d):
"""
Given a polyline and a distance computes an approximation
of the two one-sided offset curves and returns it as two
polylines with the same number of vertices as input.
NOTE: Quick and dirty approach, just uses a "normal" for every
vertex computed as the perpendicular to the segment joining
the previous and next vertex.
No checks for self-intersections (those happens when the
distance is too big for the local curvature), and no check
for degenerate input (e.g. multiple points).
"""
l1 = []
l2 = []
for i in xrange(len(pts)):
i0 = max(0, i - 1) # previous index
i1 = min(len(pts) - 1, i + 1) # next index
x, y = pts[i]
x0, y0 = pts[i0]
x1, y1 = pts[i1]
dx = x1 - x0
dy = y1 - y0
L = (dx**2 + dy**2) ** 0.5
nx = - d*dy / L
ny = d*dx / L
l1.append((x - nx, y - ny))
l2.append((x + nx, y + ny))
return l1, l2
def dist2(x0, y0, x1, y1):
"Squared distance between two points"
return (x1 - x0)**2 + (y1 - y0)**2
def dist(x0, y0, x1, y1):
"Distance between two points"
return ((x1 - x0)**2 + (y1 - y0)**2) ** 0.5
def ibez(pts, levels=bezlevels):
"""
Inverse-bezier computation.
Given a list of points computes the control points of a
cubic bezier arc that approximates them.
"""
#
# NOTE:
#
# This is a very specific routine that only works
# if the input has been obtained from the computation
# of a bezier arc with "levels" levels of subdivisions
# because computes the distance as the maximum of the
# distances of *corresponding points*.
# Note that for "big" changes in the input from the
# original bezier I dont't think is even true that the
# best parameters for a curve-curve match would also
# minimize the maximum distance between corresponding
# points. For a more general input a more general
# path-path error estimation is needed.
#
# The minimizing algorithm is a step descent on the two
# middle control points starting with a step of about
# 1/10 of the lenght of the input to about 1/1000.
# It's slow and ugly but required no dependencies and
# is just a bunch of lines of code, so I used that.
#
# Note that there is a closed form solution for finding
# the best bezier approximation given starting and
# ending points and a list of intermediate parameter
# values and points, and this formula also could be
# used to implement a much faster and accurate
# inverse-bezier in the general case.
# If you care about the problem of inverse-bezier then
# I'm pretty sure there are way smarter methods around.
#
# The minimization used here is very specific, slow
# and not so accurate. It's not production-quality code.
# You have been warned.
#
# Start with a straight line bezier arc (surely not
# the best choice but this is just a toy).
x0, y0 = pts[0]
x3, y3 = pts[-1]
x1, y1 = (x0*3 + x3) / 4.0, (y0*3 + y3) / 4.0
x2, y2 = (x0 + x3*3) / 4.0, (y0 + y3*3) / 4.0
L = sum(dist(*(pts[i] + pts[i-1])) for i in xrange(len(pts) - 1))
step = L / 10
limit = step / 100
# Function to minimize = max((a[i] - b[i])**2)
def err(x0, y0, x1, y1, x2, y2, x3, y3):
return max(dist2(*(x+p)) for x, p in zip(pts, bez3((x0, y0), (x1, y1),
(x2, y2), (x3, y3),
levels)))
while step > limit:
best = None
for dx1 in (-step, 0, step):
for dy1 in (-step, 0, step):
for dx2 in (-step, 0, step):
for dy2 in (-step, 0, step):
e = err(x0, y0,
x1+dx1, y1+dy1,
x2+dx2, y2+dy2,
x3, y3)
if best is None or e < best[0] * 0.9999:
best = e, dx1, dy1, dx2, dy2
e, dx1, dy1, dx2, dy2 = best
if (dx1, dy1, dx2, dy2) == (0, 0, 0, 0):
# We got to a minimum for this step => refine
step *= 0.5
else:
# We're still moving
x1 += dx1
y1 += dy1
x2 += dx2
y2 += dy2
return [(x0, y0), (x1, y1), (x2, y2), (x3, y3)]
def poly(pts):
"Converts a list of (x, y) points to a QPolygonF)"
return QPolygonF(map(lambda p: QPointF(*p), pts))
class Viewer(QW):
def __init__(self, parent):
QW.__init__(self, parent)
self.pts = [(100, 100), (200, 100), (200, 200), (100, 200)]
self.tracking = None # Mouse dragging callback
self.ibez = 0 # Thickening algorithm selector
def sizeHint(self):
return QSize(900, 700)
def wheelEvent(self, e):
# Moving the wheel changes between
# - original polygonal thickening
# - single-arc thickening
# - double-arc thickening
self.ibez = (self.ibez + 1) % 3
self.update()
def paintEvent(self, e):
dc = QPainter(self)
dc.setRenderHints(QPainter.Antialiasing)
# First build the curve and the polygonal thickening
pts = bez3(*self.pts)
l1, l2 = thickPath(pts, 15)
# Apply inverse bezier computation if requested
if self.ibez == 1:
# Single arc
l1 = bez3(*ibez(l1))
l2 = bez3(*ibez(l2))
elif self.ibez == 2:
# Double arc
l1 = (bez3(*ibez(l1[:len(l1)/2+1], bezlevels-1)) +
bez3(*ibez(l1[len(l1)/2:], bezlevels-1))[1:])
l2 = (bez3(*ibez(l2[:len(l2)/2+1], bezlevels-1)) +
bez3(*ibez(l2[len(l2)/2:], bezlevels-1))[1:])
# Draw results
dc.setBrush(QBrush(QColor(0, 255, 0)))
dc.drawPolygon(poly(l1 + l2[::-1]))
dc.drawPolyline(poly(pts))
dc.drawPolyline(poly(self.pts))
# Draw control points
dc.setBrush(QBrush(QColor(255, 0, 0)))
dc.setPen(QPen(Qt.NoPen))
for x, y in self.pts:
dc.drawEllipse(QRectF(x-3, y-3, 6, 6))
# Display the algorithm that has been used
dc.setPen(QPen(QColor(0, 0, 0)))
dc.drawText(20, 20,
["Polygonal", "Single-arc", "Double-arc"][self.ibez])
def mousePressEvent(self, e):
# Find closest control point
i = min(range(len(self.pts)),
key=lambda i: (e.x() - self.pts[i][0])**2 +
(e.y() - self.pts[i][1])**2)
# Setup a callback for mouse dragging
self.tracking = lambda p: self.pts.__setitem__(i, p)
def mouseMoveEvent(self, e):
if self.tracking:
self.tracking((e.x(), e.y()))
self.update()
def mouseReleaseEvent(self, e):
self.tracking = None
# Qt boilerplate
class MyDialog(QDialog):
def __init__(self, parent):
QDialog.__init__(self, parent)
self.ws = Viewer(self)
L = QVBoxLayout(self)
L.addWidget(self.ws)
self.setModal(True)
self.show()
app = QApplication([])
aa = MyDialog(None)
aa.exec_()
aa = None
这篇关于贝塞尔路径加宽的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
