intersect

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 24, 2025 License: BSD-3-Clause Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var BentleyOttmannEpsilon = float32(1e-8)

BentleyOttmannEpsilon is the snap rounding grid used by the Bentley-Ottmann algorithm. This prevents numerical issues. It must be larger than Epsilon since we use that to calculate intersections between segments. It is the number of binary digits to keep.

Functions

func And 

func And(p ppath.Path, q ppath.Path) ppath.Path

And returns the boolean path operation of path p AND q, i.e. the intersection of both. It removes all self-intersections, orients all filling paths CCW and all holes CW, and tries to split into subpaths if possible. Note that path p is flattened unless q is already flat. ppath.Path q is implicitly closed. It runs in O((n + k) log n), with n the sum of the number of segments, and k the number of intersections.

func AndPaths 

func AndPaths(ps ppath.Paths, qs ppath.Paths) ppath.Path

AndPaths is the same as And, but faster if paths are already split.

func Bounds 

func Bounds(p ppath.Path) math32.Box2

Bounds returns the exact bounding box rectangle of the path.

func CCW 

func CCW(p ppath.Path) bool

CCW returns true when the path is counter clockwise oriented at its bottom-right-most coordinate. It is most useful when knowing that the path does not self-intersect as it will tell you if the entire path is CCW or not. It will only return the result for the first subpath. It will return true for an empty path or a straight line. It may not return a valid value when the right-most point happens to be a (self-)overlapping segment.

func Contains 

func Contains(p ppath.Path, x, y float32, fillRule ppath.FillRules) bool

Contains returns whether the point (x,y) is contained/filled by the path. This depends on the ppath.FillRules. It uses a ray from (x,y) toward (∞,y) and counts the number of intersections with the path. When the point is on the boundary it is considered to be on the path's exterior.

func Crossings 

func Crossings(p ppath.Path, x, y float32) (int, bool)

Crossings returns the number of crossings with the path from the given point outwards, i.e. the number of times a ray from (x,y) towards (∞,y) intersects the path. Additionally, it returns whether the point is on a path's boundary (which does not count towards the number of crossings).

func CubicBezierCurvatureRadius 

func CubicBezierCurvatureRadius(p0, p1, p2, p3 math32.Vector2, t float32) float32

negative when curve bends CW while following t

func CubicBezierNormal 

func CubicBezierNormal(p0, p1, p2, p3 math32.Vector2, t, d float32) math32.Vector2

return the normal at the right-side of the curve (when increasing t)

func Curvature 

func Curvature(p ppath.Path, seg int, t float32) float32

Curvature returns the curvature of the path at the given segment and t in [0.0,1.0] along that path. It is zero for straight lines and for non-existing segments.

func DivideBy 

func DivideBy(p ppath.Path, q ppath.Path) ppath.Path

DivideBy returns the boolean path operation of path p DIV q, i.e. p divided by q. It removes all self-intersections, orients all filling paths CCW and all holes CW, and tries to split into subpaths if possible. Note that path p is flattened unless q is already flat. ppath.Path q is implicitly closed. It runs in O((n + k) log n), with n the sum of the number of segments, and k the number of intersections.

func DivideByPaths 

func DivideByPaths(ps ppath.Paths, qs ppath.Paths) ppath.Path

DivideByPaths is the same as DivideBy but faster if paths are already split.

func EllipseCurvatureRadius 

func EllipseCurvatureRadius(rx, ry float32, sweep bool, theta float32) float32

func Filling 

func Filling(p ppath.Path, fillRule ppath.FillRules) []bool

Filling returns whether each subpath gets filled or not. Whether a path is filled depends on the ppath.FillRules and whether it negates another path. If a subpath is not closed, it is implicitly assumed to be closed.

func Flatten 

func Flatten(p ppath.Path, tolerance float32) ppath.Path

Flatten flattens all Bézier and arc curves into linear segments and returns a new path. It uses tolerance as the maximum deviation.

func FlattenCubicBezier 

func FlattenCubicBezier(p0, p1, p2, p3 math32.Vector2, d, tolerance float32) ppath.Path

see Flat, precise flattening of cubic Bézier path and offset curves, by T.F. Hain et al., 2005, https://www.sciencedirect.com/science/article/pii/S0097849305001287 see https://github.com/Manishearth/stylo-flat/blob/master/gfx/2d/Path.cpp for an example implementation or https://docs.rs/crate/lyon_bezier/0.4.1/source/src/flatten_cubic.rs p0, p1, p2, p3 are the start points, two control points and the end points respectively. With flatness defined as the maximum error from the orinal curve, and d the half width of the curve used for stroking (positive is to the right).

func FlattenEllipticArc 

func FlattenEllipticArc(start math32.Vector2, rx, ry, phi float32, large, sweep bool, end math32.Vector2, tolerance float32) ppath.Path

func FlattenQuadraticBezier 

func FlattenQuadraticBezier(p0, p1, p2 math32.Vector2, tolerance float32) ppath.Path

func FlattenSmoothCubicBezier 

func FlattenSmoothCubicBezier(p *ppath.Path, p0, p1, p2, p3 math32.Vector2, d, tolerance float32)

split the curve and replace it by lines as long as (maximum deviation <= tolerance) is maintained

func Gridsnap 

func Gridsnap(p math32.Vector2, spacing float32) math32.Vector2

Gridsnap snaps point to a grid with the given spacing.

func IntersectionCircleCircle 

func IntersectionCircleCircle(c0 math32.Vector2, r0 float32, c1 math32.Vector2, r1 float32) (math32.Vector2, math32.Vector2, bool)

https://math32.stackexchange.com/questions/256100/how-can-i-find-the-points-at-which-two-circles-intersect https://gist.github.com/jupdike/bfe5eb23d1c395d8a0a1a4ddd94882ac

func IntersectionRayCircle 

func IntersectionRayCircle(l0, l1, c math32.Vector2, r float32) (math32.Vector2, math32.Vector2, bool)

https://mathworld.wolfram.com/Circle-LineIntersection.html

func IntersectionRayLine 

func IntersectionRayLine(a0, a1, b0, b1 math32.Vector2) (math32.Vector2, bool)

func IsFlat 

func IsFlat(p ppath.Path) bool

IsFlat returns true if the path consists of solely line segments, that is only MoveTo, ppath.LineTo and Close commands.

func Length 

func Length(p ppath.Path) float32

Length returns the length of the path in millimeters. The length is approximated for cubic Béziers.

func Not 

func Not(p ppath.Path, q ppath.Path) ppath.Path

Not returns the boolean path operation of path p NOT q, i.e. the difference of both. It removes all self-intersections, orients all filling paths CCW and all holes CW, and tries to split into subpaths if possible. Note that path p is flattened unless q is already flat. ppath.Path q is implicitly closed. It runs in O((n + k) log n), with n the sum of the number of segments, and k the number of intersections.

func NotPaths 

func NotPaths(ps ppath.Paths, qs ppath.Paths) ppath.Path

NotPaths is the same as ppath.Path.Not, but faster if paths are already split.

func Or 

func Or(p ppath.Path, q ppath.Path) ppath.Path

Or returns the boolean path operation of path p OR q, i.e. the union of both. It removes all self-intersections, orients all filling paths CCW and all holes CW, and tries to split into subpaths if possible. Note that path p is flattened unless q is already flat. ppath.Path q is implicitly closed. It runs in O((n + k) log n), with n the sum of the number of segments, and k the number of intersections.

func OrPaths 

func OrPaths(ps ppath.Paths, qs ppath.Paths) ppath.Path

OrPaths is the same as ppath.Path.Or, but faster if paths are already split.

func Settle 

func Settle(p ppath.Path, fillRule ppath.FillRules) ppath.Path

Settle returns the "settled" path. It removes all self-intersections, orients all filling paths CCW and all holes CW, and tries to split into subpaths if possible. Note that path p is flattened unless q is already flat. ppath.Path q is implicitly closed. It runs in O((n + k) log n), with n the sum of the number of segments, and k the number of intersections.

func SettlePaths 

func SettlePaths(ps ppath.Paths, fillRule ppath.FillRules) ppath.Path

SettlePaths is the same as Settle, but faster if paths are already split.

func SplitAt 

func SplitAt(p ppath.Path, ts ...float32) []ppath.Path

SplitAt splits the path into separate paths at the specified intervals (given in millimeters) along the path.

func Windings 

func Windings(p ppath.Path, x, y float32) (int, bool)

Windings returns the number of windings at the given point, i.e. the sum of windings for each time a ray from (x,y) towards (∞,y) intersects the path. Counter clock-wise intersections count as positive, while clock-wise intersections count as negative. Additionally, it returns whether the point is on a path's boundary (which counts as being on the exterior).

func XMonotone 

func XMonotone(p ppath.Path) ppath.Path

XMonotone replaces all Bézier and arc segments to be x-monotone and returns a new path, that is each path segment is either increasing or decreasing with X while moving across the segment. This is always true for line segments.

func Xor 

func Xor(p ppath.Path, q ppath.Path) ppath.Path

Xor returns the boolean path operation of path p XOR q, i.e. the symmetric difference of both. It removes all self-intersections, orients all filling paths CCW and all holes CW, and tries to split into subpaths if possible. Note that path p is flattened unless q is already flat. ppath.Path q is implicitly closed. It runs in O((n + k) log n), with n the sum of the number of segments, and k the number of intersections.

func XorPaths 

func XorPaths(ps ppath.Paths, qs ppath.Paths) ppath.Path

XorPaths is the same as Xor, but faster if paths are already split.

Types

type Intersection 

type Intersection struct {
	math32.Vector2            // coordinate of intersection
	T              [2]float32 // position along segment [0,1]
	Dir            [2]float32 // direction at intersection [0,2*pi)
	Tangent        bool       // intersection is tangent (touches) instead of secant (crosses)
	Same           bool       // intersection is of two overlapping segments (tangent is also true)
}

Intersection is an intersection between two path segments, e.g. Line x Line. Note that an intersection is tangent also when it is at one of the endpoints, in which case it may be tangent for this segment but may or may not cross the path depending on the adjacent segment. Notabene: for quad/cube/ellipse aligned angles at the endpoint for non-overlapping curves are deviated slightly to correctly calculate the value for Into, and will thus not be aligned

func RayIntersections 

func RayIntersections(p ppath.Path, x, y float32) []Intersection

RayIntersections returns the intersections of a path with a ray starting at (x,y) to (∞,y). An intersection is tangent only when it is at (x,y), i.e. the start of the ray. The parameter T along the ray is zero at the start but NaN otherwise. Intersections are sorted along the ray. This function runs in O(n) with n the number of path segments.

func (Intersection) Equals 

func (z Intersection) Equals(o Intersection) bool

func (Intersection) Into 

func (z Intersection) Into() bool

Into returns true if first path goes into the left-hand side of the second path, i.e. the second path goes to the right-hand side of the first path.

func (Intersection) String 

func (z Intersection) String() string

type Intersections 

type Intersections []Intersection

func IntersectionSegment 

func IntersectionSegment(zs Intersections, a0 math32.Vector2, a ppath.Path, b0 math32.Vector2, b ppath.Path) Intersections

intersect for path segments a and b, starting at a0 and b0. Note that all intersection functions return up to two intersections.

func (Intersections) Has 

func (zs Intersections) Has() bool

Has returns true if there are secant/tangent intersections.

func (Intersections) HasSecant 

func (zs Intersections) HasSecant() bool

HasSecant returns true when there are secant intersections, i.e. the curves intersect and cross (they cut).

func (Intersections) HasTangent 

func (zs Intersections) HasTangent() bool

HasTangent returns true when there are tangent intersections, i.e. the curves intersect but don't cross (they touch).

type SweepEvents 

type SweepEvents []*SweepPoint

SweepEvents is a heap priority queue of sweep events.

func (*SweepEvents) AddPathEndpoints 

func (q *SweepEvents) AddPathEndpoints(p ppath.Path, seg int, clipping bool) int

func (*SweepEvents) Fix 

func (q *SweepEvents) Fix(i int)

func (SweepEvents) Init 

func (q SweepEvents) Init()

func (SweepEvents) Less 

func (q SweepEvents) Less(i, j int) bool

func (*SweepEvents) Pop 

func (q *SweepEvents) Pop() *SweepPoint

func (SweepEvents) Print 

func (q SweepEvents) Print(w io.Writer)

func (*SweepEvents) Push 

func (q *SweepEvents) Push(item *SweepPoint)

func (SweepEvents) String 

func (q SweepEvents) String() string

func (SweepEvents) Swap 

func (q SweepEvents) Swap(i, j int)

func (*SweepEvents) Top 

func (q *SweepEvents) Top() *SweepPoint

type SweepNode 

type SweepNode struct {
	*SweepPoint
	// contains filtered or unexported fields
}

func (*SweepNode) Next 

func (n *SweepNode) Next() *SweepNode

func (*SweepNode) Prev 

func (n *SweepNode) Prev() *SweepNode

func (*SweepNode) Print 

func (n *SweepNode) Print(w io.Writer)

type SweepPoint 

type SweepPoint struct {
	// initial data
	math32.Vector2 // position of this endpoint
	// contains filtered or unexported fields
}

func (*SweepPoint) CompareH 

func (a *SweepPoint) CompareH(b *SweepPoint) int

func (*SweepPoint) CompareV 

func (a *SweepPoint) CompareV(b *SweepPoint) int

func (*SweepPoint) InResult 

func (s *SweepPoint) InResult(op pathOp, fillRule ppath.FillRules) uint8

func (*SweepPoint) InterpolateY 

func (s *SweepPoint) InterpolateY(x float32) float32

func (*SweepPoint) LessH 

func (a *SweepPoint) LessH(b *SweepPoint) bool

func (*SweepPoint) Reverse 

func (s *SweepPoint) Reverse()

func (*SweepPoint) SplitAt 

func (s *SweepPoint) SplitAt(z math32.Vector2) (*SweepPoint, *SweepPoint)

func (*SweepPoint) String 

func (s *SweepPoint) String() string

func (*SweepPoint) ToleranceEdgeY 

func (s *SweepPoint) ToleranceEdgeY(xLeft, xRight float32) (float32, float32)

ToleranceEdgeY returns the y-value of the SweepPoint at the tolerance edges given by xLeft and xRight, or at the endpoints of the SweepPoint, whichever comes first.

type SweepStatus 

type SweepStatus struct {
	// contains filtered or unexported fields
}

TODO: test performance versus (2,4)-tree (current LEDA implementation), (2,16)-tree (as proposed by S. Naber/Näher in "Comparison of search-tree data structures in LEDA. Personal communication" apparently), RB-tree (likely a good candidate), and an AA-tree (simpler implementation may be faster). Perhaps an unbalanced (e.g. Treap) works well due to the high number of insertions/deletions.

func (*SweepStatus) Clear 

func (s *SweepStatus) Clear()

func (*SweepStatus) Find 

func (s *SweepStatus) Find(item *SweepPoint) *SweepNode

Find returns the node equal to item. May return nil.

func (*SweepStatus) FindPrevNext 

func (s *SweepStatus) FindPrevNext(item *SweepPoint) (*SweepNode, *SweepNode)

func (*SweepStatus) First 

func (s *SweepStatus) First() *SweepNode

func (*SweepStatus) Insert 

func (s *SweepStatus) Insert(item *SweepPoint) *SweepNode

func (*SweepStatus) InsertAfter 

func (s *SweepStatus) InsertAfter(n *SweepNode, item *SweepPoint) *SweepNode

func (*SweepStatus) Last 

func (s *SweepStatus) Last() *SweepNode

func (*SweepStatus) Remove 

func (s *SweepStatus) Remove(n *SweepNode)

func (*SweepStatus) String 

func (s *SweepStatus) String() string

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.