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

Directories

Path Synopsis
internal

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL