subdivision

package
v0.0.4 Latest Latest
Warning

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

 Go to latest Published: Oct 31, 2023 License: MIT Imports: 25 Imported by: 0

Documentation

Index

Constants

View Source 
const (

	// ErrInvalidStartingVertex is returned when the starting vertex is invalid
	ErrInvalidStartingVertex = errors.String("invalid starting vertex")

	// ErrInvalidEndVertex is returned when the ending vertex is invalid
	ErrInvalidEndVertex = errors.String("invalid ending vertex")

	// ErrCancelled is returned when the activity is cancelled
	ErrCancelled = errors.String("cancelled")

	// ErrCoincidentalEdges is returned when two edges are conincidental and not expected to be
	ErrCoincidentalEdges = errors.String("coincident edges")

	// ErrDidNotFindToFrom is returned when one of the endpoint of an edge is not in the graph,
	// and is expected to be
	ErrDidNotFindToFrom = errors.String("did not find to and from edge")
)
View Source 
const (
	DefaultSRS                     = 0
	TableNameSubdivision           = "subdivisions"
	TableNameSubdivisionEdge       = "subdivision_edges"
	TableNameAssociatedLinestrings = "associated_linestrings"
	TableNameAssociatedPoints      = "associated_points"
	TestDBInsertSDSQL              = `
		INSERT INTO subdivisions (
			name, 
			description, 
			frame
		) VALUES ( ?, ?, ?);
	`
	TestDBInsertEdgeSQL = `
		INSERT INTO subdivision_edges (
			sd_id,
			insert_order,
			is_frame,
			edge
		) VALUES ( ?,?,?,? );
	`
	TestDBInsertLineStringSQL = `
		INSERT INTO associated_linestrings (
			sd_id,
			description,
			function,
			geometry
		) VALUES ( ?,?,?,? );
	`
	TestDBInsertPointSQL = `
		INSERT INTO associated_points(
			sd_id,
			description,
			function,
			geometry
		) VALUES ( ?,?,?,? );
	`

	ErrTestDBNil = errors.String("TestDB is nil")
)
View Source 
const RoundingFactor = 1000

Variables

This section is empty.

Functions

func DumpSubdivision 

func DumpSubdivision(sd *Subdivision)

DumpSubdivision will print each edge in the subdivision

func DumpSubdivisionW 

func DumpSubdivisionW(w io.Writer, sd *Subdivision)

DumpSubdivisionW will write each edge in the subdivision to w

func ErrAssumptionFailed 

func ErrAssumptionFailed() error

ErrAssumptionFailed is an assert of when our assumptions fails, in debug mode it will return and error. In non debug mode it will panic

func FindIntersectingEdges 

func FindIntersectingEdges(order winding.Order, startingEdge, endingEdge *quadedge.Edge) (edges []*quadedge.Edge, err error)

FindIntersectingEdges will find all edges in the graph that would be intersected by the origin of the starting edge and the dest of the endingEdge

func IsFrameEdge 

func IsFrameEdge(frame [3]geom.Point, es ...*quadedge.Edge) bool

IsFrameEdge indicates if the edge is part of the given frame.

func IsFramePoint 

func IsFramePoint(frame [3]geom.Point, pts ...geom.Point) bool

IsFramePoint indicates if at least one of the points is equal to one of the frame points

func IsHardFrameEdge 

func IsHardFrameEdge(frame [3]geom.Point, e *quadedge.Edge) bool

IsHardFrameEdge indicates if the edge is part of the given frame where both vertexes are part of the frame.

func ResolveStartingEndingEdges 

func ResolveStartingEndingEdges(order winding.Order, vertexIndex VertexIndex, start, end geom.Point) (startingEdge, endingEdge *quadedge.Edge, exists bool, err error)

func ToggleDebug 

func ToggleDebug()

func WalkAllEdges 

func WalkAllEdges(se *quadedge.Edge, fn func(e *quadedge.Edge) error) error

WalkAllEdges will call fn for each edge starting with se

func WalkAllTriangles 

func WalkAllTriangles(ctx context.Context, se *quadedge.Edge, fn func(start, mid, end geom.Point) (shouldContinue bool))

Types

type PseudoPolygonPointCollector 

type PseudoPolygonPointCollector struct {
	Start geom.Point
	End   geom.Point
	Order winding.Order
	// contains filtered or unexported fields
}

func (*PseudoPolygonPointCollector) AddEdge 

func (pppc *PseudoPolygonPointCollector) AddEdge(e *quadedge.Edge) error

AddEdge will attempt to add the origin and dest points of the edge to the lower or upper set as required

func (*PseudoPolygonPointCollector) AddPoint 

func (pppc *PseudoPolygonPointCollector) AddPoint(pt geom.Point) error

AddPoint will add the given point to the lower or upper set as required and if it's not a point that has already been seen

func (*PseudoPolygonPointCollector) Edges 

func (pppc *PseudoPolygonPointCollector) Edges(upper bool) ([]geom.Line, error)

Edges returns the triangulated edges for the upper or lower region

func (*PseudoPolygonPointCollector) SharedLine 

func (pppc *PseudoPolygonPointCollector) SharedLine() geom.Line

SharedLine returns the line shared by the set of points, all points should be on one side or the other of this line

type Subdivision 

type Subdivision struct {
	Order winding.Order
	// contains filtered or unexported fields
}

Subdivision describes a quadedge graph that is used for triangulation

func New 

func New(order winding.Order, a, b, c geom.Point) *Subdivision

New initialize a subdivision to the triangle defined by the points a,b,c.

func NewForPoints 

func NewForPoints(ctx context.Context, order winding.Order, points [][2]float64) (sd *Subdivision, err error)

NewForPoints creates a new subdivision for the given points, the points are sorted and duplicate points are not added

func NewSubdivisionFromGeomLines 

func NewSubdivisionFromGeomLines(lines []geom.Line, order winding.Order) *Subdivision

NewSubdivisionFromGeomLines returns a new subdivision made up of the given geom lines. it is assume that all line are connected. If lines are disjointed that it is undefined which disjointed subdivision will be returned

func (*Subdivision) InsertConstraint 

func (sd *Subdivision) InsertConstraint(ctx context.Context, vertexIndex VertexIndex, start, end geom.Point) (err error)

func (*Subdivision) InsertSite 

func (sd *Subdivision) InsertSite(x geom.Point) bool

InsertSite will insert a new point into a subdivision representing a Delaunay triangulation, and fixes the affected edges so that the result is still a Delaunay triangulation. This is based on the pseudocode from Guibas and Stolfi (1985) p.120, with slight modifications and a bug fix.

func (*Subdivision) IsValid 

func (sd *Subdivision) IsValid(ctx context.Context) bool

IsValid will walk the graph making sure it is in a valid state

func (*Subdivision) StartingEdge 

func (sd *Subdivision) StartingEdge() *quadedge.Edge

StartingEdge returns the starting edge of the subdivision, this may change after an InsertSite call.

func (*Subdivision) Triangles 

func (sd *Subdivision) Triangles(includeFrame bool) (triangles [][3]geom.Point, err error)

Triangles will return the triangles in the graph

func (*Subdivision) Validate 

func (sd *Subdivision) Validate(ctx context.Context) error

Validate will run a set of validation tests against the sd to insure the sd was built correctly. This process is very cpu and memory intensive

func (*Subdivision) VertexIndex 

func (sd *Subdivision) VertexIndex() VertexIndex

VertexIndex will calculate and return a VertexIndex that can be used to quickly look up vertexes

func (*Subdivision) WalkAllEdges 

func (sd *Subdivision) WalkAllEdges(fn func(e *quadedge.Edge) error) error

WalkAllEdges will call the provided function for each edge in the subdivision. The walk will be terminated if the function returns an error or ErrCancel. ErrCancel will not result in an error be returned by main function, otherwise the error will be passed on.

type SubdivisionInsertionDump 

type SubdivisionInsertionDump struct {
	Point [2]float64
	SD    *Subdivision
}

func (*SubdivisionInsertionDump) DumpAllEdges 

func (sdid *SubdivisionInsertionDump) DumpAllEdges() string

type TestDB 

type TestDB struct {
	*testingtables.DB
	// contains filtered or unexported fields
}

func OpenTestDB 

func OpenTestDB(filename string) (*TestDB, error)

OpenTestDB will open the gpkg file and read it for reading and writing

func (*TestDB) Get 

func (db *TestDB) Get(id int64) (*Subdivision, error)

Get the subdivision as described by the id

func (*TestDB) Order 

func (db *TestDB) Order(_ int64) (winding.Order, error)

func (*TestDB) PrepareStatements 

func (db *TestDB) PrepareStatements() error

PrepareStatements prepares heavely used statements

func (*TestDB) SubdivisionFrom 

func (db *TestDB) SubdivisionFrom(id int64, name, description string, pts ...geom.Point) (int64, error)

SubdivisionFrom will create a new subdivsion that is a subsection of another subdivision that is described by the points

func (*TestDB) Write 

func (db *TestDB) Write(name, description string, sd *Subdivision) (int64, error)

Write the subdivision to the db with the given name and description

func (*TestDB) WriteContained 

func (db *TestDB) WriteContained(name, description string, sd *Subdivision, start, end geom.Point) (int64, error)

Write the subdivision to the db with the given name and description

func (*TestDB) WriteEdge 

func (db *TestDB) WriteEdge(id int64, function, description string, edge *quadedge.Edge) error

WriteEdge writes a edge that is associated linestring with a subdivision

func (*TestDB) WriteLineString 

func (db *TestDB) WriteLineString(id int64, function, description string, line geom.LineString) error

WriteLineString writes a line string that is associated with a subdivision

func (*TestDB) WritePoint 

func (db *TestDB) WritePoint(id int64, function, description string, point geom.Point) error

WritePoint writes a line string that is associated with a subdivision

type Triangle 

type Triangle struct {
	*quadedge.Edge
}

func NewTriangle 

func NewTriangle(e *quadedge.Edge) Triangle

func (Triangle) AsGeom 

func (t Triangle) AsGeom() (tri geom.Triangle)

AsGeom returns a geom based Triangle

func (Triangle) IntersectsPoint 

func (t Triangle) IntersectsPoint(pt geom.Point) bool

func (Triangle) OppositeTriangle 

func (t Triangle) OppositeTriangle(p geom.Point) (*Triangle, error)

OppositeTriangle returns the triangle opposite to the vertex v 

   +
  /|\
 / | \
/  |  \

v1 + a | b + 

\  |  /
 \ | /
  \|/
   +

If this method is called on triangle a with v1 as the vertex, the result will be triangle b.

func (Triangle) OppositeVertex 

func (t Triangle) OppositeVertex(other Triangle) *geom.Point

OppositeVertex returns the vertex opposite to this triangle. 

   +
  /|\
 / | \
/  |  \

v1 + a | b + v2 

\  |  /
 \ | /
  \|/
   +

If this method is called as a.opposedVertex(b), the result will be vertex v2.

func (Triangle) SharedEdge 

func (t Triangle) SharedEdge(other Triangle) *quadedge.Edge

SharedEdge returns the edge that is shared by both a and b. The edge is returned with triangle a on the left.

  • l /|\ / | \ / | \
  • a | b + \ | / \ | / \|/
  • r

If this method is called as a.sharedEdge(b), the result will be edge lr.

func (Triangle) StartingEdge 

func (t Triangle) StartingEdge() *quadedge.Edge

type VertexIndex 

type VertexIndex map[geom.Point]*quadedge.Edge

VertexIndex is an index of points to an quadedge in the graph this allows one to quickly jump to a group of edges by the origin point of that edge

func NewVertexIndex 

func NewVertexIndex(startingEdge *quadedge.Edge) VertexIndex

NewVertexIndex will return a new vertex index given a starting edge.

func (VertexIndex) Add 

func (vx VertexIndex) Add(e *quadedge.Edge)

Add an edge to the graph

func (VertexIndex) Get 

func (vx VertexIndex) Get(pt geom.Point) (*quadedge.Edge, bool)

Get retrives the edge

func (VertexIndex) Remove 

func (vx VertexIndex) Remove(e *quadedge.Edge)

Remove an edge from the graph

Source Files

View all Source files

Directories

Path Synopsis
internal
phenix

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.