Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

# ArcPrecise, an accurate arc

133 views

### jdaw1

Jul 19, 2022, 3:47:27 PM7/19/22
to
The PostScript command `arc` can draw circles, and part circles. Adobe Distiller draws angles ≤90° as a single Bézier cubic.

A Bézier cubic has eight parameters, `curveto` receiving the two from the `currentpoint`, and six from the stack. An arc must go through the correct endpoints, using four parameters. At the endpoints the direction of travel must be tangent to the circle, so each end absorbs another parameter. And, by symmetry, at the two ends the speeds of departure must be the same. ⟹︎ Only one parameter remains to be chosen, being the speed of departure from the endpoints.

For a 90° part of a unit circle, Adobe uses a speed of 0.552. Mathematica shows that the worst error happens at t ≈ 0.18864 (and at one minus this), an angle ≈ 17.39° (and 90° minus this) where the radius is too large by about 212 parts per million. At t = ½, angle = 45°, the radius is too small by −151 parts per million. These values are confirmed by testing with `flattenpath` … `pathforall`.

For a circle of radius 540pt = 7½″ = 190.5mm, plausible on A4 or 8½″×11″, the error is as large as 0.1145pt.

Typically, a ≈0.04mm error doesn’t matter: the eye would not perceive it midst an empty page. But if a circle is being drawn with `arc`, and things placed at its edge (locations computed with `sin` and `cos`), as my software http://github.com/jdaw1/placemat/ does, then these things could be falsely apart by 0.11pt. That isn’t a disaster, but could be a multi-pixel visible imperfection. And an unnecessary imperfection.

This is solved by new PostScript routines `ArcPrecise`, and à la `arcn`, `ArcPreciseN`.

http://www.jdawiseman.com/2022/ArcPrecise.ps
http://www.jdawiseman.com/2022/ArcPrecise.pdf
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_17.png (Adobe error of +212 ppm)
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_73.png (Adobe error of +212 ppm)
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_45.png (Adobe error of −151 ppm)
http://www.jdawiseman.com/2022/ArcPrecise_bitmap_06.png (worst ArcPrecise error, +0.37 ppm)

Output is shown in the PDF and the .png extracts from it. The grey line, width 0.36pt, is a precise circle, made of tiny `lineto`s only ⅛° apart. Underneath is a red line, width 0.60pt, drawn with Adobe’s `arc`, the red diagonals touching its worst radii. On top is a blue line, width 0.12pt, drawn with `ArcPrecise`, short blue lines touching its worst points. The widths are chosen such that, where all are neatly aligned, each stripe of colour has width 0.12pt. Throughout, the grey and the blue are neatly aligned; but the red drifts out by almost 0.12pt, then in, then back out.

Assume curve of angle θ. A speed of Tan[θ/4]·4/3 has the radius precisely correct at the midpoint, t = ½, angle = θ/2. The radius is never too small, and is maximal at t = ½ − ⅙√3 ≈ 0.2113. For θ small and in radians, the maximal radius happens near angle (½ − ⅙√3)·θ ≈ 0.2113 θ, where the radius is too big by ≈ 2⁻¹¹·3⁻³·θ⁶ = (θ^6)/55296.

`ArcPrecise` chooses curves of no more than 30°. For a 30° curve the actual worst error is 0.372662 parts per million; this approximation says π⁶/2579890176 − 1 ≈ 0.372647 ppm. So it is a good approximation to the error.

For a 540pt radius, `ArcPrecise` has a peak error of 0.00020pt. If the smallest error we care about is 0.01pt, half a pixel at 3600d.p.i., that doesn’t happen with radius ≤ 9.46 metres ≈ 31 feet. This is bigger than the PDF standard’s maximum page size of only 200″ = 16⅔ feet = 5.08 metres. Further, PostScript’s arithmetic is single-precision, with a 23-bit mantissa, which is only slightly more accurate than 0.37 ppm. So 30° curves are sufficiently small.

There is also a little neatness in the choice of curve-end angles. If every multiple of 90° is a curve endpoint, then `pathbbox` returns the correct minimal box. So the angle choosing algorithm works as follows. It computes the next multiple of 90°, If that’s ≤30° away, done in one curve; else if ≤60° away, done in two equal-angle curves; otherwise split into three equal-angle curves. Then 30° curves until the final multiple of 90°; the final section, like the first, in at most three equal-angle curves each ≤30°. This means that: curves are all ≤30°; for a non-rotated frame `pathbbox` works optimally; and the number of curves is at most 1 + ⌈|ang₂ − ang₁| ÷ 30°⌉.

The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto.

Comment welcomed.

### jdaw1

Jul 20, 2022, 2:25:22 PM7/20/22
to
> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto.

I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.

### David Newall

Jul 21, 2022, 4:29:38 AM7/21/22
to
On 21/7/22 04:25, jdaw1 wrote:
>> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto.
>
> I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.

Use PS arc: you (often) have to add moveto. Use ArcPrecise: you
(sometimes) have to add lineto. It seems unimportant.

moveto so programmers have no surprises when they use ArcPrecise.

### John Reiser

Jul 21, 2022, 10:17:26 AM7/21/22
to
On 7/20/22 11:25, jdaw1 wrote:
>> The build-in routines start with a line from a currentpoint, if there is one. This is annoying. Consider an annulus: there’s a line between the inner and outer circles, avoiding which requires a manual moveto. `ArcPrecise` and `ArcPreciseN` prevent this annoyance by starting, always, with a moveto, never a lineto.
>
> I think this is an error. What if the user wants a rounded rectangle. That isn’t possible if `ArcPrecise` starts with a `moveto`. Perhaps there could be an extra parameter, code, usually being one of {moveto}, {lineto}, {pop pop}. Advice welcomed.

Advice: 'ArcPrecise' should have the same API as 'arc'. Why? When I see
an image that I want to improve by using ArcPrecise instead of arc, then
I want the *option* to interpose a global dictionary which defines 'arc'
as 'ArcPrecise', and have better arcs be the only change to the image.
I might not have access to the innards of the rest of the Postscript code;
it might not be possible to use a text editor to change all calls on "arc".

### jdaw1

Jul 21, 2022, 3:02:40 PM7/21/22
to
> so programmers have no surprises when they use ArcPrecise.

Good desideratum.

I’m coming to the view that ArcPrecise should have an extra parameter, which could be one of three values:
✪ `/l` ⟹︎ `arc`-style `lineto`;
✪ `/m` ⟹︎ `moveto`, especially useful if previous command was `closepath`;
✪ `/n` ⟹︎ nothing, presumably because the currentpoint is already the start of the curve.

The compulsory extra parameter prevents surprises.

> Advice: 'ArcPrecise' should have the same API as 'arc'.

Good desideratum. And
`/arc {/l ArcPrecise} def`
would work as you require.

Would this extra final parameter, `/l` | `/m` | `/n`, satisfy everybody?

### luser droog

Jul 21, 2022, 5:31:22 PM7/21/22
to
I lean towards endorsing this view, but I don't hold the opinion very strongly.
Having a drop-in replacement is very useful. Having a considered and improved
behavior based on the common use cases is very useful. I'm not sure how
to weigh these benefits against each other.

For the implementation side -- apart from the policy decision -- mimicking
the existing API of `arc` can be pretty short and sweet:

% x0 y0
{ lineto } stopped { moveto } if

This leads to the question: how can you (most) easily get the starting point
out of `arc` or `ArcPrecise` (were it to follow this convention) in order to
call `moveto` first to eliminate the line segment (erhm, make its length zero)?

If you call `arc` or `ArcPrecise` with an angular difference of zero, it ought
to result in adding to the path just that initial point, right? Then you'd just
need a crazy function to rewrite the path where the very last `lineto` is
changed to a `moveto`. Too ugly for me to want to write it right now, but
feels possible to write.

The extra parameter idea is nice. Extra parameterization is the obvious
way to select variant behaviors. Whether it "looks nice" is a subjective
judgement.

### jdaw1

Jul 21, 2022, 6:00:19 PM7/21/22
to
> { lineto } stopped { moveto } if

Nice. I was testing `currentpoint` with `stopped`: this is more concise. Thank you.

### jdaw1

Jul 21, 2022, 6:24:18 PM7/21/22
to

> A speed of Tan[θ/4]·4/3 has the radius precisely correct at the midpoint

If θ = 90°, then the speed is Tan[22½°]·4/3 = (√2 − 1)·4/3 ≈ 0.55228474983, which is only an edge bigger than Adobe’s fixed value of 0.552.

### jdaw1

Jul 22, 2022, 3:58:03 AM7/22/22
to
Is it the best name? Is an error fo 0.37 ppm ‘precise’, or merely ‘accurate’? Should it be ArcAccurate?

### Phil Wakely

Jul 22, 2022, 4:42:18 AM7/22/22
to
On Friday, 22 July 2022 at 08:58:03 UTC+1, jdaw1 wrote:
> Is it the best name? Is an error fo 0.37 ppm ‘precise’, or merely ‘accurate’? Should it be ArcAccurate?
Are you achieving a more accurate result by calculating with greater precision, or by using a better method? Increased precision usually increases accuracy (exception cases aside), but accuracy can often be improved without increasing precision using better approaches or calculation sequence adjustment (typically to maintain improved precision through the calculation especially with limited precision variables). Both "Accurate" and "Precise" would nominally require qualification or quantification (how precise or accurate); ArcImproved could also work.

### Phil Wakely

Jul 22, 2022, 4:52:33 AM7/22/22
to
Really it should be ArcImprovedAccuracy; but I suspect that may be too long for most people's taste.

### jdaw1

Jul 22, 2022, 5:03:12 PM7/22/22
to

### jdaw1

Jul 24, 2022, 12:02:26 PM7/24/22
to
https://github.com/jdaw1/placemat/blob/main/PostScript/placemat.ps
with commit
https://github.com/jdaw1/placemat/commit/77143c29d01f9352a53fa98361cf4589cace92e8
For the latest version, look in that .ps, searching for “ArcAccurateBoth” or “B23RW2QpIjU”.