mở rộng đường bezier

Question

Tôi có đường cong Bezier B với điểm S, C1, C2, E và số dương w biểu thị chiều rộng. Có cách nào để nhanh chóng tính toán các điểm kiểm soát của hai đường cong bezier B1, B2 sao cho công cụ giữa B1 và ​​B2 là đường được mở rộng đại diện bởi B?

Chính thức hơn: tính toán các điểm kiểm soát của xấp xỉ Bezier tốt với B1, B2, trong đó B1 = {(x, y) + N (x, y) (w/2) | (x, y) trong C}
B2 = {(x, y) - N (x, y) (w/2) | (x, y) trong C},
trong đó N (x, y) là bình thường của C tại (x, y).

Tôi nói xấp xỉ tốt vì B1, B2 có thể không phải là đường cong đa thức (tôi không chắc chắn nếu chúng là).

Answer 1

Đường song song chính xác của đường cong bezier khá xấu xí từ điểm nhìn toán học (nó yêu cầu đa thức bậc 10).

Điều dễ làm là tính toán mở rộng từ xấp xỉ đa giác của bezier (nghĩa là bạn tính toán các đoạn đường từ bezier và sau đó di chuyển các điểm dọc theo các chuẩn trên hai cạnh của đường cong).

Điều này mang lại kết quả tốt nếu độ dày của bạn không quá lớn so với độ cong ... "song song" thay vào đó là một con quái vật (và thậm chí không dễ dàng tìm ra định nghĩa song song của một đường cong mở khiến mọi người hạnh phúc).

Khi bạn có hai đường polycines cho hai bên, điều bạn có thể làm là tìm một bezier gần đúng nhất cho những đường dẫn đó nếu bạn cần đại diện đó. Một lần nữa tôi nghĩ rằng đối với "trường hợp bình thường" (đó là những đường mỏng hợp lý), ngay cả chỉ một vòng cung bezier cho mỗi bên phải khá chính xác (lỗi nhỏ hơn nhiều so với độ dày của đường kẻ).

EDIT: Thật vậy, sử dụng một vòng cung bezier trông tồi tệ hơn nhiều so với tôi mong đợi ngay cả đối với trường hợp hợp lý bình thường. Tôi đã thử cũng sử dụng hai vòng tròn bezier cho mỗi bên và kết quả là tốt hơn nhưng vẫn không hoàn hảo. Lỗi là tất nhiên nhỏ hơn nhiều so với độ dày của dòng vì vậy trừ khi dòng rất dày nó có thể là một lựa chọn hợp lý. Trong hình dưới đây nó hiển thị một bezier dày (với mỗi điểm dày), một xấp xỉ bằng cách sử dụng một vòng cung bezier duy nhất cho mỗi bên và một xấp xỉ bằng cách sử dụng hai vòng cung bezier cho mỗi bên.

EDIT 2: Theo yêu cầu tôi thêm mã tôi đã sử dụng để có được những hình ảnh; nó trong python và chỉ yêu cầu Qt. Mã này không có nghĩa là để được đọc bởi những người khác vì vậy tôi đã sử dụng một số thủ thuật mà có lẽ tôi sẽ không sử dụng trong mã sản xuất thực tế. Thuật toán cũng rất kém hiệu quả nhưng tôi không quan tâm đến tốc độ (điều này có nghĩa là một chương trình một lần để xem ý tưởng đó có hiệu quả hay không).

# 
# 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) 
    p= 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