chain

package
v1.1.3 Latest Latest
Warning

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

 Go to latest Published: Aug 30, 2022 License: LGPL-2.1 Imports: 8 Imported by: 0

Documentation

Overview

Package chain Define Monotone Chains,it is a way of partitioning the segments of a linestring to allow for fast searching of intersections.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Overlaps 

func Overlaps(p1, p2, q1, q2 matrix.Matrix, overlapTolerance float64) bool

Overlaps Tests whether the envelope of a section of the chain overlaps (intersects) the envelope of a section of another target chain. This test is efficient due to the monotonicity property of the sections (i.e. the envelopes can be are determined from the section endpoints rather than a full scan).

Types

type CorrelationNodeResult added in v1.1.0 

type CorrelationNodeResult [][]*IntersectionCorrelationNode

CorrelationNodeResult ...

type IntersectionCollinear 

type IntersectionCollinear struct {
	Intersections relate.IntersectionPointLine
	Edge          matrix.LineMatrix
	// contains filtered or unexported fields
}

IntersectionCollinear Finds intersections between line segments , and adds them.

func (*IntersectionCollinear) IsDone 

func (ii *IntersectionCollinear) IsDone() bool

IsDone Always process all intersections.

func (*IntersectionCollinear) ProcessIntersections 

func (ii *IntersectionCollinear) ProcessIntersections(
	e0 matrix.LineMatrix, segIndex0 int,
	e1 matrix.LineMatrix, segIndex1 int)

ProcessIntersections This method is called by clients to process intersections for two segments being intersected. Note that some clients (such as <code>MonotoneChain</code>s) may optimize away this call for segment pairs which they have determined do not intersect

func (*IntersectionCollinear) Result 

func (ii *IntersectionCollinear) Result() interface{}

Result returns result.

type IntersectionCollinearDifference 

type IntersectionCollinearDifference struct {
	Edge matrix.LineMatrix
	// contains filtered or unexported fields
}

IntersectionCollinearDifference Finds interior intersections between line segments , and adds them.

func (*IntersectionCollinearDifference) IsDone 

func (ii *IntersectionCollinearDifference) IsDone() bool

IsDone Always process all intersections

func (*IntersectionCollinearDifference) ProcessIntersections 

func (ii *IntersectionCollinearDifference) ProcessIntersections(
	e0 matrix.LineMatrix, segIndex0 int,
	e1 matrix.LineMatrix, segIndex1 int)

ProcessIntersections This method is called by clients to process intersections for two segments being intersected. Note that some clients (such as <codeProcessIntersections>MonotoneChain</code>s) may optimize away this call for segment pairs which they have determined do not intersect

func (*IntersectionCollinearDifference) Result 

func (ii *IntersectionCollinearDifference) Result() interface{}

Result returns result.

type IntersectionCorrelation added in v1.1.0 

type IntersectionCorrelation struct {
	Edge, Edge1 matrix.LineMatrix
	// contains filtered or unexported fields
}

IntersectionCorrelation Finds intersections between line segments , and adds them.

func (*IntersectionCorrelation) IsDone added in v1.1.0 

func (ii *IntersectionCorrelation) IsDone() bool

IsDone Always process all intersections

func (*IntersectionCorrelation) ProcessIntersections added in v1.1.0 

func (ii *IntersectionCorrelation) ProcessIntersections(
	e0 matrix.LineMatrix, segIndex0 int,
	e1 matrix.LineMatrix, segIndex1 int)

ProcessIntersections This method is called by clients to process intersections for two segments being intersected. Note that some clients (such as <code>MonotoneChain</code>s) may optimize away this call for segment pairs which they have determined do not intersect

func (*IntersectionCorrelation) Result added in v1.1.0 

func (ii *IntersectionCorrelation) Result() interface{}

Result returns result.

type IntersectionCorrelationNode added in v1.1.0 

type IntersectionCorrelationNode struct {
	//Pos             int
	InterNode       matrix.Matrix
	CorrelationNode matrix.LineMatrix
}

IntersectionCorrelationNode ...

func (*IntersectionCorrelationNode) String added in v1.1.0 

func (ic *IntersectionCorrelationNode) String() string

type IntersectionFinderAdder 

type IntersectionFinderAdder struct {
	Intersections relate.IntersectionPointLine
}

IntersectionFinderAdder Finds intersections between line segments , and adds them.

func (*IntersectionFinderAdder) IsDone 

func (ii *IntersectionFinderAdder) IsDone() bool

IsDone Always process all intersections

func (*IntersectionFinderAdder) ProcessIntersections 

func (ii *IntersectionFinderAdder) ProcessIntersections(
	e0 matrix.LineMatrix, segIndex0 int,
	e1 matrix.LineMatrix, segIndex1 int)

ProcessIntersections This method is called by clients to process intersections for two segments being intersected. Note that some clients (such as <code>MonotoneChain</code>s) may optimize away this call for segment pairs which they have determined do not intersect

func (*IntersectionFinderAdder) Result 

func (ii *IntersectionFinderAdder) Result() interface{}

Result returns result.

type IntersectionInterior 

type IntersectionInterior struct {
	Intersections relate.IntersectionPointLine
}

IntersectionInterior Finds interior intersections between line segments , and adds them.

func (*IntersectionInterior) IsDone 

func (ii *IntersectionInterior) IsDone() bool

IsDone Always process all intersections

func (*IntersectionInterior) ProcessIntersections 

func (ii *IntersectionInterior) ProcessIntersections(
	e0 matrix.LineMatrix, segIndex0 int,
	e1 matrix.LineMatrix, segIndex1 int)

ProcessIntersections This method is called by clients to process intersections for two segments being intersected. Note that some clients (such as <code>MonotoneChain</code>s) may optimize away this call for segment pairs which they have determined do not intersect

func (*IntersectionInterior) Result 

func (ii *IntersectionInterior) Result() interface{}

Result returns result.

type IntersectionNodeOfLine added in v1.1.0 

type IntersectionNodeOfLine []*IntersectionNodeResult

IntersectionNodeOfLine overlay point array.

func (IntersectionNodeOfLine) Len added in v1.1.0 

func (ipl IntersectionNodeOfLine) Len() int

Len ...

func (IntersectionNodeOfLine) Less added in v1.1.0 

func (ipl IntersectionNodeOfLine) Less(i, j int) bool

Less ...

func (IntersectionNodeOfLine) Swap added in v1.1.0 

func (ipl IntersectionNodeOfLine) Swap(i, j int)

Swap ...

type IntersectionNodeResult added in v1.1.0 

type IntersectionNodeResult struct {
	Pos       int
	End       int
	InterNode relate.IntersectionPoint
	Line      matrix.LineSegment
	OtherLine matrix.LineSegment
	OtherEdge matrix.LineMatrix
}

IntersectionNodeResult ...

type Intersector 

type Intersector interface {
	// This func is called by clients of interface to process
	// intersections for two segments of the lineSegments being intersected.
	ProcessIntersections(
		e0 matrix.LineMatrix, segIndex0 int,
		e1 matrix.LineMatrix, segIndex1 int)

	// Reports whether the client of this class needs to continue testing all intersections in an arrangement.
	IsDone() bool

	// Result return results.
	Result() interface{}
}

Intersector Processes possible intersections detected. detects that two SegmentStrings <i>might</i> intersect.

type MergeCorrelation added in v1.1.1 

type MergeCorrelation struct {
	Edge, Edge1 matrix.LineMatrix
	// contains filtered or unexported fields
}

MergeCorrelation Finds intersections between line segments , and adds them.

func (*MergeCorrelation) IsDone added in v1.1.1 

func (ii *MergeCorrelation) IsDone() bool

IsDone Always process all intersections

func (*MergeCorrelation) ProcessIntersections added in v1.1.1 

func (ii *MergeCorrelation) ProcessIntersections(
	e0 matrix.LineMatrix, segIndex0 int,
	e1 matrix.LineMatrix, segIndex1 int)

ProcessIntersections This method is called by clients to process intersections for two segments being intersected. Note that some clients (such as <code>MonotoneChain</code>s) may optimize away this call for segment pairs which they have determined do not intersect

func (*MergeCorrelation) Result added in v1.1.1 

func (ii *MergeCorrelation) Result() interface{}

Result returns result.

type MonotoneChain 

type MonotoneChain struct {
	Edge       matrix.LineMatrix
	Start, End int
	Env        *envelope.Envelope
	Context    interface{}
	ID         int // useful for optimizing chain comparisons
}

MonotoneChain Monotone Chains are a way of partitioning the segments of a linestring to allow for fast searching of intersections. They have the following properties: 

the segments within a monotone chain never intersect each other
he envelope of any contiguous subset of the segments in a monotone chain
is equal to the envelope of the endpoints of the subset.

func Chains 

func Chains(edge matrix.LineMatrix) []*MonotoneChain

Chains Computes a list of the MonotoneChains for a list of coordinates.

func ChainsContext 

func ChainsContext(edge matrix.LineMatrix, context interface{}) []*MonotoneChain

ChainsContext Computes a list of the MonotoneChains for a list of coordinates,attaching a context data object to each.

func (*MonotoneChain) ComputeOverlaps 

func (m *MonotoneChain) ComputeOverlaps(mc *MonotoneChain, mco overlapAction)

ComputeOverlaps Determines the line segments in two chains which may overlap, and passes them to an overlap action.

func (*MonotoneChain) ComputeOverlapsTolerance 

func (m *MonotoneChain) ComputeOverlapsTolerance(mc *MonotoneChain, overlapTolerance float64, mco overlapAction)

ComputeOverlapsTolerance Determines the line segments in two chains which may overlap, 

using an overlap distance tolerance, and passes them to an overlap action.

func (*MonotoneChain) Envelope 

func (m *MonotoneChain) Envelope() *envelope.Envelope

Envelope Gets the envelope of the chain.

func (*MonotoneChain) EnvelopeExpansion 

func (m *MonotoneChain) EnvelopeExpansion(expansionDistance float64) *envelope.Envelope

EnvelopeExpansion Gets the envelope for this chain,expanded by a given distance.

func (*MonotoneChain) LineSegment 

func (m *MonotoneChain) LineSegment(index int, ls *matrix.LineSegment) *matrix.LineSegment

LineSegment Gets the line segment starting at <code>index</code>

func (*MonotoneChain) OverlapsMonotoneChain 

func (m *MonotoneChain) OverlapsMonotoneChain(
	start0, end0 int,
	mc *MonotoneChain,
	start1, end1 int,
	overlapTolerance float64) bool

OverlapsMonotoneChain Tests whether the envelope of a section of the chain overlaps (intersects) the envelope of a section of another target chain. This test is efficient due to the monotonicity property of the sections (i.e. the envelopes can be are determined from the section endpoints rather than a full scan).

func (*MonotoneChain) Select 

func (m *MonotoneChain) Select(searchEnv *envelope.Envelope, mcs *MonotoneChainSelectAction)

Select Determine all the line segments in the chain whose envelopes overlap the searchEnvelope, and process them.

type MonotoneChainOverlapAction 

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

MonotoneChainOverlapAction The action for the internal iterator for performing overlap queries on a MonotoneChain

func (*MonotoneChainOverlapAction) Overlap 

func (m *MonotoneChainOverlapAction) Overlap(mc1 *MonotoneChain, start1 int, mc2 *MonotoneChain, start2 int)

Overlap This function can be overridden if the original chains are needed.

type MonotoneChainSelectAction 

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

MonotoneChainSelectAction The action for the internal iterator for performing envelope select queries on a MonotoneChain

func (*MonotoneChainSelectAction) Select 

func (m *MonotoneChainSelectAction) Select(mc *MonotoneChain, startIndex int)

Select This method is overridden to process a segment in the context of the parent chain.

type SegmentMutualIntersector 

type SegmentMutualIntersector struct {
	SegmentMutual matrix.LineMatrix
}

SegmentMutualIntersector Intersects two sets of SegmentString.

func (*SegmentMutualIntersector) AddToMonoChains 

func (s *SegmentMutualIntersector) AddToMonoChains(segMatrix matrix.LineMatrix, context interface{}, monoChains []*MonotoneChain) []*MonotoneChain

AddToMonoChains ...

func (*SegmentMutualIntersector) IntersectChains 

func (s *SegmentMutualIntersector) IntersectChains(monoChains []*MonotoneChain, testChains []*MonotoneChain, segInt Intersector)

IntersectChains ...

func (*SegmentMutualIntersector) Process 

func (s *SegmentMutualIntersector) Process(segStrings matrix.LineMatrix, segInt Intersector)

Process the given collection of SegmentStrings and the set of indexed segments.

type SegmentOverlapAction 

type SegmentOverlapAction struct {
	*MonotoneChainOverlapAction
	// contains filtered or unexported fields
}

SegmentOverlapAction implement OverlapAction.

func (*SegmentOverlapAction) Overlap 

func (s *SegmentOverlapAction) Overlap(mc1 *MonotoneChain, start1 int, mc2 *MonotoneChain, start2 int)

Overlap This function can be overridden if the original chains are needed.

type SelectAction 

type SelectAction interface {
	// This function can be overridden if the original chains are needed.
	Select(mc1 *MonotoneChain, startIndex int)
}

SelectAction The action for the internal iterator for performing envelope select queries on a MonotoneChain

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.