Re: How to get X/Y-extent of a bezier-curve?

[David Kastrup]

Thomas Morley <address@hidden> writes:

> 2015-10-06 14:49 GMT+02:00 David Kastrup <address@hidden>:
>> Thomas Morley <address@hidden> writes:
>>
>>> Hi all,
>>>
>>> I'm going to write a generic bow-stencil.
>>> Below you'll find a boiled down example.
>>>
>>> The main problem: how to determine the correct extents.
>>> Looks like I need to calculate the actual X/Y-extents of the resulting
>>> bezier-curve.
>>> Though, obviously my maths-skills are not sufficient.
>>
>> Oh, that's a nuisance.
>>
>>> Any hints?
>>
>> I'd just call make-path-stencil and use the bounding box results from
>> that.  No need to reinvent the wheel.
>
> Yep.
> Using make-path-stencil is much more straight-forward.
> Thanks.
>
> If someone interested, I'll attach an image with an excerpt of my test-suite.
>
> I plan to replace make-parenthesis-stencil and to implement
> https://sourceforge.net/p/testlilyissues/issues/3088/
>
>>
>> While this particular wheel could likely profit from a do-over with more
>> of a view towards efficiency and numerical robustness, there is no point
>> in code duplication.
>
> I think we could replace the body of current
> make-bezier-sandwich-stencil with make-path-stencil.
> But obviously you think about some deeper modification.
> Could you give some details?

No, not really.  When I tabled this issue, I thought that
make-bezier-sandwich was dead for some reason but I think that it's used
in several places such as (obviously related) slurs.  And I found it
awkward to use the undertie as the basic shape and derive parentheses
via rotation.  And I thought this was essentially user-level code
needing significant modification.

All in all, I had a significant number of misconceptions about the work
involved with completing this issue and even though becoming gradually
aware of them I never picked up that dropped ball again.

It should be reasonably low-hanging fruit.

With regard to my comments to make-path-stencil's operation, the numeric
code is just not what I like.

If you take a look at the following, it is quite inefficient since it
repeats a lot of calculations instead of assigning partial results to
let-bound variables.  It also uses the straight PQ formula whereas the
usual way to avoid numerical inaccuracies is to use the PQ formula only
for the zero where the sign of the +/- does not lead to cancellation and
get the other zero via Viata's rule.

(define (bezier-part-min-max x1 x2 x3 x4)
  ((lambda (x) (list (reduce min 10000 x) (reduce max -10000 x)))
   (map
    (lambda (x)
      (+ (* x1 (expt (- 1 x) 3))
         (+ (* 3 (* x2 (* (expt (- 1 x) 2) x)))
            (+ (* 3 (* x3 (* (- 1 x) (expt x 2))))
               (* x4 (expt x 3))))))
    (if (< (+ (expt x2 2) (+ (expt x3 2) (* x1 x4)))
           (+ (* x1 x3) (+ (* x2 x4) (* x2 x3))))
        (list 0.0 1.0)
        (filter
         (lambda (x) (and (>= x 0) (<= x 1)))
         (append
          (list 0.0 1.0)
          (map (lambda (op)
                 (if (not (eqv? 0.0
                                (exact->inexact (- (+ x1 (* 3 x3)) (+ x4 (* 3 
x2))))))
                     ;; Zeros of the bezier curve
                     (/ (+ (- x1 (* 2 x2))
                           (op x3
                               (sqrt (- (+ (expt x2 2)
                                           (+ (expt x3 2) (* x1 x4)))
                                        (+ (* x1 x3)
                                           (+ (* x2 x4) (* x2 x3)))))))
                        (- (+ x1 (* 3 x3)) (+ x4 (* 3 x2))))
                     ;; Apply L'hopital's rule to get the zeros if 0/0
                     (* (op 0 1)
                        (/ (/ (- x4 x3) 2)
                           (sqrt (- (+ (* x2 x2)
                                       (+ (* x3 x3) (* x1 x4)))
                                    (+ (* x1 x3)
                                       (+ (* x2 x4) (* x2 x3)))))))))
               (list + -))))))))


-- 
David Kastrup