// SPDX-FileCopyrightText: 2018 Raph Levien

// SPDX-FileCopyrightText: 2024 Dominik Honnef and contributors

//

// SPDX-License-Identifier: MIT

// SPDX-FileAttributionText: https://github.com/linebender/kurbo

// Package curve provides primitives and routines for 2D shapes, curves, and

// paths. It was designed to serve the needs of 2D graphics applications, but it

// is intended to be general enough to be useful for other applications.

//

// # Kurbo

//

// This package is a manual, idiomatic Go port of the [kurbo] Rust crate. Kurbo

// contains several novel approaches to problems in 2D curve design,

// particularly stroke expansion. This package's development will closely follow

// kurbo's.

//

// We may introduce functionality of our own, but this will likely be limited to

// simple features.

//

// # Features

//

// We provide the following notable features:

//

// - Curve fitting (see [FitToBezPath])

// - Stroke expansion (see [StrokePath])

// - Dashing (see [Dash])

// - Curve simplification (see [Simplify])

// - Affine transformations (see [Affine])

// - Approximating cubic Béziers with quadratic splines (see [CubicBez.ApproxQuadSpline])

// - Flattening paths to lines (see [Flatten])

//

// # Shapes, parametric curves, and paths

//

// The three core primitives of this package are shapes, curves, and paths.

//

// [Shape] describes geometric shapes that have a perimeter and a bounding box,

// and that can be converted to a series of path elements. [ClosedShape]

// describes those shapes that additionally have a closed outline (such as

// rectangles, but not lines) and thus have an area and can compute a point's

// [winding number].

//

// This package includes the following shapes:

// - [Arc]

// - [Circle]

// - [CircleSector]

// - [Annulus]

// - [AnnulusSector]

// - [CubicBez]

// - [Ellipse]

// - [Line]

// - [QuadBez]

// - [Rect]

// - [RoundedRect]

// - [Triangle]

//

// [ParametricCurve] describes parametrized curves. These curves can be

// evaluated at t ∈ [0, 1] and return pairs of (x, y) values, commonly

// interpreted as points in a 2D Cartesian coordinate system. The simplest

// parametric curve is the [Line], whose evaluation is a simple linear

// interpolation between its start and end points. More complex curves are the

// quadratic and cubic Béziers, for example.

//

// [PathLengther] is an optional interface implemented by curves that can compute

// their length. [PathLengthSolver] is an optional interface

// implemented by curves that can efficiently solve for t given an arc length.

//

// [FittableCurve] is closely related to [ParametricCurve] and describes

// parametrized curves in a way that allows efficient curve fitting. Using curve

// fitting, arbitrary curves can be approximated with paths. See the example of

// [FitToBezPathOpt] for a custom curve that implements a quartic function and

// that gets approximated by cubic Béziers.

//

// This package includes the following curves:

// - [Line]

// - [CubicBez]

// - [PathSegment] (as it is a wrapper for [Line], [CubicBez], and [QuadBez])

// - [QuadBez]

//

// # Bézier paths

//

// Bézier paths consist of lines and quadratic and cubic Béziers. All shapes can

// represent themselves as Bézier paths, and more complex curves can be

// approximated by them.

//

// [BezPath] represents Bézier paths as a slice of path elements and provides

// methods for building paths as well as for any path manipulation that needs

// access to the collection of path elements. The two other representations are

// iter.Seq[PathElement] and iter.Seq[PathSegment], see the Iterators section

// for more on that.

//

// # Path elements and segments

//

// This package provides two representations for paths: [PathElement] and

// [PathSegment]. Path elements are akin to drawing commands in graphics APIs

// like PostScript, consisting of pen moves ([MoveTo]) and various drawing

// commands ([LineTo], [QuadTo], etc.) Each command moves the current position

// of the pen, which acts as the start position of the following drawing

// command.

//

// Segments, on the other hand, are self-contained descriptions of a portion of

// the path, containing explicit start points.

//

// Using [Elements] and [Segments], you can freely convert between the two

// representations.

//

// The package supports [MoveTo], [LineTo], [QuadTo], [CubicTo], and [ClosePath]

// path elements, and correspondingly has path segments for lines, quadratic

// Béziers, and cubic Béziers.

//

// # Cubic Béziers

//

// The primary curve used by this package is the cubic Bézier. Functions that

// convert shapes to paths do so by approximating them with cubic Béziers (and

// lines). Similarly, curve fitting approximates curves with cubic Béziers (and

// lines). This is done because cubic Béziers hit the sweet spot of

// expressiveness and computability.

//

// However, we also provide functions for working with quadratic Béziers,

// including approximating cubic Béziers with quadratic Béziers. This

// functionality is particularly useful for font design, as TrueType fonts

// (unlike OpenType) use quadratic Béziers.

//

// # Direction of the y-axis

//

// This package is agnostic to whether the y-axis points up or down. Positive

// angles are defined such that when going in the positive x direction, they

// point towards positive y. The same applies to oriented area, winding numbers,

// curvature, etc. For y-up coordinate systems, this results in counterclockwise

// traversal, while for y-down coordinate systems it results in clockwise

// traversal.

//

// A = (1, 1)

// B = (4, 1)

// C = (4, 4)

// D = (1, 4)

//

// y-up │ y-down

// y │

// ^ │ 0-------------------------> x

// | │ |

// | │ | A +------->-------+ B

// | D +-------<-------+ C │ | | |

// | | | │ | ^ v

// | v ^ │ | | |

// | | | │ | D +-------<-------+ C

// | A +------->-------+ B │ |

// | │ v

// 0-------------------------> x │ y

// │

//

// You can also use [FlipY] (followed by a translation of the origin) to convert

// between y-up and y-down.

//

// We try to avoid using the terms "top" and "bottom" when referring to edges of

// shapes, as these are only meaningful when specifying the direction of the

// y-axis.

//

// # Oriented area / signed area

//

// The Area method on shapes returns their oriented area. The oriented area of a

// closed shape is its enclosed area, with the sign depending on the order of

// traversal. In a y-down coordinate system, the area is positive for clockwise

// traversal, while in a y-up one, it is positive for anticlockwise traversal.

//

// When open shapes, such as [CubicBez], implement this method, they compute

// their contribution to the overall area of a closed shape, such as a

// closed [BezPath] made up of multiple curves.

//

// The oriented area is also commonly called the signed area, but we wanted

// to avoid confusion with the definition from calculus, where the signed

// area of a curve is the area between the curve and the x-axis. This is not

// the case here.

//

// # Literature

//

// This package makes use of the following ideas:

// - [A Primer on Bézier Curves]

// - [Algorithm 1010: Boosting Efficiency in Solving Quartic Equations with No Compromise in Accuracy] by Orellana and De Michele

// - [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality] by Oliveira and Takahashi

// - [Approximate a circle with cubic Bézier curves] by Spencer Mortensen

// - [Calculating Area of Closed Curves in ℝ²]

// - [Fitting cubic Bézier curves] by Raph Levien

// - [Flattening quadratic Béziers] by Raph Levien

// - [Green's theorem]

// - [How to solve a cubic equation, revisited] by Christoph Peters

// - [Parallel curves of cubic Béziers] by Raph Levien

// - [Simplifying Bézier paths] by Raph Levien

// - https://github.com/Pomax/BezierInfo-2/issues/238

//

// [A Primer on Bézier Curves]: https://pomax.github.io/bezierinfo/

// [Algorithm 1010: Boosting Efficiency in Solving Quartic Equations with No Compromise in Accuracy]: https://cristiano-de-michele.netlify.app/publication/orellana-2020/orellana-2020.pdf

// [An Enhancement of the Bisection Method Average Performance Preserving Minmax Optimality]: https://dl.acm.org/doi/10.1145/3423597

// [Approximate a circle with cubic Bézier curves]: https://spencermortensen.com/articles/bezier-circle/

// [Fitting cubic Bézier curves]: https://raphlinus.github.io/curves/2021/03/11/bezier-fitting.html

// [Flattening quadratic Béziers]: https://raphlinus.github.io/graphics/curves/2019/12/23/flatten-quadbez.html

// [Green's theorem]: https://en.wikipedia.org/wiki/Green%27s_theorem

// [How to solve a cubic equation, revisited]: https://momentsingraphics.de/CubicRoots.html

// [Parallel curves of cubic Béziers]: https://raphlinus.github.io/curves/2022/09/09/parallel-beziers.html

// [Simplifying Bézier paths]: https://raphlinus.github.io/curves/2023/04/18/bezpath-simplify.html

// [Calculating Area of Closed Curves in ℝ²]: http://ich.deanmcnamee.com/graphics/2016/03/30/CurveArea.html

// [kurbo]: https://github.com/linebender/kurbo

// [winding number]: https://en.wikipedia.org/wiki/Winding_number

package curve