dcel

package
v0.0.0-...-b5aa40e Latest Latest
Warning

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

 Go to latest Published: Feb 7, 2018 License: MIT Imports: 8 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// OUTER_FACE is used to represent the infinite space
	// around the outer edge(s) of a DCEL.
	OUTER_FACE = 0
)

Variables

This section is empty.

Functions

func EdgeTwin 

func EdgeTwin(i int) int

EdgeTwin can obtain a given edge index's twin without accessing the edge itself, for index manipulation, or for initially setting the Twins in construction.

Hopeful Mandate: twin edges come in pairs if i is even, then, i+1 is its pair, and otherwise i-i is its pair.

Types

type DCEL 

type DCEL struct {
	Vertices  []*Vertex
	HalfEdges []*Edge
	// The first value in a face is the outside component
	// of the face, the second value is the inside component
	Faces []*Face
}

A DCEL is a structure representin arbitrary plane divisions and 3d polytopes. Its values are relatively self-explanatory but constructing it is significantly harder.

func FourPoint 

func FourPoint(p1, p2, p3, p4 geom.D3) *DCEL

FourPoint creates a dcel from four points, connected in order around one face.

func New 

func New() *DCEL

New returns an empty DCEL with its inner fields initialized to empty slices, and a zeroth outside face.

func Random2DDCEL 

func Random2DDCEL(size float64, splits int) *DCEL

func Rect 

func Rect(x, y, w, h float64) *DCEL

Rect is a wrapper around FourPoint to make a rectangle with top left position and dimensions.

func (*DCEL) Bounds 

func (dc *DCEL) Bounds() geom.Span

Bounds on a DCEL returns a Span calculated from every point in the DCEL.

func (*DCEL) ConnectVerts 

func (dc *DCEL) ConnectVerts(a, b *Vertex, f *Face)

ConnectVerts takes two vertices and adds edges to the dcel containing them to connect the two vertices by a full edge. the added edges will be at dc.HalfEdges[len-1] and len-2. no face is added, and connectVerts assumes the provided face is the face in which the diagonal will land.

The job of creating new faces is delayed because if a series of ConnectVerts is called on the same face, calling code won't be able to easily tell which face the sequential diagonals land in.

This function doesn't cover enough cases to work.

func (*DCEL) Copy 

func (dc *DCEL) Copy() *DCEL

Copy duplicates a DCEL's internal values in a new DCEL.

func (*DCEL) CorrectDirectionality 

func (dc *DCEL) CorrectDirectionality(f *Face)

CorrectDirectionality (rather innefficently) ensures that a face has the right clockwise/ counter-clockwise orientation based on whether its chain is the inner or outer portion of a face.

func (*DCEL) CorrectDirectionalityAll 

func (dc *DCEL) CorrectDirectionalityAll()

This is probably how we actually want to do flipping, always.

func (*DCEL) CorrectTwins 

func (dc *DCEL) CorrectTwins()

CorrectTwins modifies the ordering on twins inside the DCEL such that dc.HalfEdges[i] is the twin of dc.HalfEdges[i+1] for all even i values.

func (*DCEL) FullEdge 

func (dc *DCEL) FullEdge(i int) (geom.FullEdge, error)

FullEdge returns the ith edge in the form of its two vertices

func (*DCEL) FullEdges 

func (dc *DCEL) FullEdges() ([]geom.FullEdge, [][2]*Face, error)

FullEdges returns the set of all FullEdges in DCEL.

func (*DCEL) Max 

func (dc *DCEL) Max(i int) (x float64)

Max functions iterate through vertices to find the maximum value along a given axis in the DCEL

func (*DCEL) MaxX 

func (dc *DCEL) MaxX() float64

MaxX returns the Maximum of all X values

func (*DCEL) MaxY 

func (dc *DCEL) MaxY() float64

MaxY returns the Maximum of all Y values

func (*DCEL) MaxZ 

func (dc *DCEL) MaxZ() float64

MaxZ returns the Maximum of all Z values

func (*DCEL) Min 

func (dc *DCEL) Min(i int) (x float64)

Min functions iterate through vertices to find the maximum value along a given axis in the DCEL

func (*DCEL) MinX 

func (dc *DCEL) MinX() float64

MinX returns the Minimum of all X values

func (*DCEL) MinY 

func (dc *DCEL) MinY() float64

MinY returns the Minimum of all Y values

func (*DCEL) MinZ 

func (dc *DCEL) MinZ() float64

MinZ returns the Minimum of all Z values

func (*DCEL) ScanFaces 

func (dc *DCEL) ScanFaces(f *Face) int

ScanFaces returns which index, if any, within dc matches f.

func (*DCEL) String 

func (dc *DCEL) String() string

func (*DCEL) VerticesSorted 

func (dc *DCEL) VerticesSorted(ds ...int) []int

VerticesSorted returns a list indicating the sorted order of this dcel's vertices in dimensions ds. Example: to get points sorted by x, use with (0) 

to get points sorted by y, breaking ties
   on lesser x, use with (1,0).

type Edge 

type Edge struct {
	// Origin is the vertex this edge starts at
	Origin *Vertex
	// Face is the index within Faces that this
	// edge wraps around
	Face *Face
	// Next and Prev are the edges following and
	// preceding this edge that also wrap around
	// Face
	Next *Edge
	Prev *Edge
	// Twin is the half edge who points to this
	// half-edge's origin, and respectively whose
	// origin this half-edge points to.
	Twin *Edge
}

An Edge represents an edge within a DCEL, specifically a half edge, which maintains references to it's origin vertex, the face it bounds, the half edge sharing its space bounding its adjacent face, and the previous and following edges which bound its face.

func NewEdge 

func NewEdge() *Edge

NewEdge returns a null-initialized Edge.

func (*Edge) AllEdges 

func (e *Edge) AllEdges() []*Edge

AllEdges on an edge is equivalent to e.Origin.AllEdges, which actually calls this instead of the other way around because that involves less code duplciation.

func (*Edge) At 

func (e *Edge) At(i int) geom.Dimensional

At returns either e.Origin or e.Twin.Origin for 0 or 1

func (*Edge) Bounds 

func (e *Edge) Bounds() geom.Span

Bounds on an Edge returns a Span on the edge's origin and it's twin's origin.

func (*Edge) Compare 

func (e *Edge) Compare(i interface{}) search.CompareResult

Compare allows Edge to satisfy search interfaces for placement in BSTs.

func (*Edge) Copy 

func (e *Edge) Copy() *Edge

Copy returns a copy of edge e

func (*Edge) D 

func (e *Edge) D() int

D redirects to Origin.D

func (*Edge) EdgeChain 

func (e *Edge) EdgeChain() []*Edge

EdgeChain returns the edges of e as a chain until e.Next = e again.

func (*Edge) Eq 

func (e *Edge) Eq(e2 geom.Spanning) bool

Eq redirects to Origin.Eq

func (*Edge) FindSharedPoint 

func (e *Edge) FindSharedPoint(e2 *Edge, d int) (float64, error)

FindSharedPoint returns some value, if one exists, in dimension d, that has a defined point on both e and e2. This function is deterministic. It does not return a -random- value, if multiple values are valid.

func (*Edge) Flip 

func (e *Edge) Flip()

Flip converts edge and all that share a face with edge from counterclockwise to clockwise or vice versa

func (*Edge) FullEdge 

func (e *Edge) FullEdge() (geom.FullEdge, error)

FullEdge returns this edge with its twin in the form of its two vertices

func (*Edge) High 

func (e *Edge) High(d int) geom.Dimensional

High returns whichever point on e is higher in dimension d

func (*Edge) IsClockwise 

func (e *Edge) IsClockwise() (bool, error)

IsClockwise returns whether a given set of edges is clockwise or not. Method credit: lhf on stackOverflow https://math.stackexchange.com/questions/340830

func (*Edge) Len 

func (e *Edge) Len() int

Len returns the number of discrete points defined on an edge, in normal cases, 2

func (*Edge) Low 

func (e *Edge) Low(d int) geom.Dimensional

Low returns whichever point on e is lower in dimension d

func (*Edge) Mid2D 

func (e *Edge) Mid2D() (geom.Point, error)

Mid2D returns the midpoint of an Edge

func (*Edge) PointAlong 

func (e *Edge) PointAlong(d int, pcnt float64) geom.D3

PointAlong returns the point some percent along e, increasing on dimension d. If percent <= 0, returns e.Low(d). if percent >= 1, returns e.High(d).

func (*Edge) PointAt 

func (e *Edge) PointAt(d int, v float64) (geom.Point, error)

PointAt returns the point at a given position on some d dimension along this edge. I.E. for d = 0, v = 5, if this edge was represented as y = mx + b, this would return y = m*5 + b.

func (*Edge) Set 

func (e *Edge) Set(i int, d geom.Dimensional) geom.Spanning

Set sets the value behind a point on e to a given point

func (*Edge) SetNext 

func (e *Edge) SetNext(e2 *Edge)

SetNext is shorthand for a next and prev assignment.

func (*Edge) SetPrev 

func (e *Edge) SetPrev(e2 *Edge)

SetPrev is shorthand for a prev and next assignment.

func (*Edge) SetTwin 

func (e *Edge) SetTwin(e2 *Edge)

SetTwin is shorthand for two twin assignments.

func (*Edge) String 

func (e *Edge) String() string

String converts an edge into a string.

func (*Edge) Val 

func (e *Edge) Val(d int) float64

Val redirects to Origin.Val

func (*Edge) X 

func (e *Edge) X() float64

X redirects to Origin.X

func (*Edge) Y 

func (e *Edge) Y() float64

Y redirects to Origin.Y

func (*Edge) Z 

func (e *Edge) Z() float64

Z redirects to Origin.Z

type Face 

type Face struct {
	Inner, Outer *Edge
}

A Face points to the edges on its inner and outer portions. Any given face may have either of these values be nil, but never both.

func NewFace 

func NewFace() *Face

NewFace returns a null-initialized Face.

func (*Face) Bounds 

func (f *Face) Bounds() geom.Span

Bounds returns a Span calculated from every point on the Inner of this face because at time of writing we don't populate Outer

func (*Face) Contains 

func (f *Face) Contains(p geom.D2) bool

Contains returns whether a point lies inside f. We cannot assume that f is convex, or anything besides some polygon. That leaves us with a rather complex form of PIP--

func (*Face) Encloses 

func (f *Face) Encloses(f2 *Face) bool

Encloses returns whether f completey enwraps f2 Doing this check legitimately would be costly and complex. We assume, right now, that we already -know- that either f encloses f2 or f2 encloses f. If this is true, if one of them has a point higher than the other, that one is the encloser.

func (*Face) Vertices 

func (f *Face) Vertices() []*Vertex

Vertices wraps around a face and finds all vertices that border it.

func (*Face) VerticesSorted 

func (f *Face) VerticesSorted(ds ...int) []*Vertex

VerticesSorted returns this face's vertices sorted in dimensions ds. Example: to get points sorted by x, use with (0) 

to get points sorted by y, breaking ties
   on lesser x, use with (1,0).

--This has different behavior than DCEL.VerticesSorted! it does not return indices but direct vertex pointers.

type Vertex 

type Vertex struct {
	geom.Point
	OutEdge *Edge
}

A Vertex is a Point which knows its outEdge.

func NewVertex 

func NewVertex(x, y, z float64) *Vertex

NewVertex returns a Vertex at a given position with no outEdge

func PointToVertex 

func PointToVertex(dp geom.D3) *Vertex

PointToVertex converts a point into a vertex

func (*Vertex) Add 

func (v *Vertex) Add(d int, f float64)

Add adds to the point behind a vertex

func (*Vertex) AllEdges 

func (v *Vertex) AllEdges() []*Edge

AllEdges iterates through the edges surrounding a vertex and returns them all.

func (*Vertex) EdgeToward 

func (v *Vertex) EdgeToward(v2 *Vertex) *Edge

EdgeToward returns the edge around this vertex which is pointing toward v2.

func (*Vertex) Mult 

func (v *Vertex) Mult(d int, f float64)

Mult multiplies the point behind a vertex

func (*Vertex) PartitionEdges 

func (v *Vertex) PartitionEdges(d int) (lesser []*Edge,
	greater []*Edge, colinear []*Edge, err error)

PartitionEdges splits the edges around a vertex and returns those whose endpoints are lesser, equal to, and greater than the given vertex in dimension d.

Source Files

View all Source files

Directories

Path Synopsis
package off describes methods for interacting with OFF files and structures formatted as OFF files.
 package off describes methods for interacting with OFF files and structures formatted as OFF files.
bench/bruteForce
bench/slab
bench/trapezoid
bruteForce
kirkpatrick
monotone
rtree
slab
test/parse
trapezoid
visualize

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.