-
Notifications
You must be signed in to change notification settings - Fork 0
/
dcel.go
126 lines (109 loc) · 3.65 KB
/
dcel.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
// Package dcel implements a doubly connected edge list data structure, and is used to represent
// planar graphs in a plane. This implementation is intended to be used in 2D space only.
package dcel
import (
"fmt"
"strconv"
)
// DCEL stores the state of the data structure and provides methods for linking of three sets of
// objects: vertecies, edges and faces.
type DCEL struct {
Vertices []*Vertex
Faces []*Face
HalfEdges []*HalfEdge
}
// Vertex represents a node in the DCEL structure. Each vertex has 2D coordinates and a pointer
// to an arbitrary half edge that has this vertex as its target (origin). Annotations (user data)
// can be stored in the Data field.
type Vertex struct {
X, Y int
HalfEdge *HalfEdge
Data interface{}
}
// Face represents a subdivision of the plane. Each face has a pointer to one of the half edges
// at its boundary. Faces can have user specified IDs and annotations.
type Face struct {
HalfEdge *HalfEdge
ID int64
Data interface{}
}
// HalfEdge represents one of the half-edges in an edge pair. Each half-edge has a pointer to its
// target vertex (origin), the face to which it belongs, its twin edge (a reversed half-edge, pointing
// to a neighbour face) and pointers to the next and previous half-edges at the boundary of its face.
// Half-edges can also store user data.
type HalfEdge struct {
Target *Vertex
Face *Face
Twin *HalfEdge
Next *HalfEdge
Prev *HalfEdge
Data interface{}
}
func (v *Vertex) String() string {
return fmt.Sprintf("{Vertex %p; X,Y: %d,%d; Edge: %p}", v, v.X, v.Y, v.HalfEdge)
}
func (f *Face) String() string {
return fmt.Sprintf("{Face #%d %p}", f.ID, f)
}
func (he *HalfEdge) String() string {
faceID := "nil"
if he.Face != nil {
faceID = "#" + strconv.FormatInt(he.Face.ID, 10)
}
return fmt.Sprintf("{Edge %p; Target: %d,%d; Twin: %p; Face: %s}", he, he.Target.X, he.Target.Y, he.Twin, faceID)
}
// IsClosed returns true if both half-edges in the pair have a target vertex.
func (he *HalfEdge) IsClosed() bool {
return he.Target != nil && he.Twin != nil && he.Twin.Target != nil
}
// NewDCEL creates a new DCEL data structure.
func NewDCEL() *DCEL {
return &DCEL{}
}
// NewFace creates a new face and stores it in the DCEL structure.
func (d *DCEL) NewFace() *Face {
face := &Face{}
d.Faces = append(d.Faces, face)
return face
}
// NewVertex creates a new vertex with the given coordinates and stores it in the structure.
func (d *DCEL) NewVertex(x, y int) *Vertex {
vertex := &Vertex{
X: x,
Y: y,
}
d.Vertices = append(d.Vertices, vertex)
return vertex
}
// NewHalfEdge creates a new half-edge starting at the given vertex and stores it in the structure.
func (d *DCEL) NewHalfEdge(face *Face, vertex *Vertex, twin *HalfEdge) *HalfEdge {
halfEdge := &HalfEdge{
Face: face,
Target: vertex,
Twin: twin,
}
// Link new half-edge to the one pointed by the face counter-clockwise
if face.HalfEdge != nil {
halfEdge.Prev = face.HalfEdge.Prev
if halfEdge.Prev != nil {
halfEdge.Prev.Next = halfEdge
}
face.HalfEdge.Prev = halfEdge
halfEdge.Next = face.HalfEdge
}
// Set the new half-edge as the one pointed by the face
face.HalfEdge = halfEdge
// If the vertex is not yet linked with an edge, link to this one
if vertex != nil && vertex.HalfEdge == nil {
vertex.HalfEdge = halfEdge
}
d.HalfEdges = append(d.HalfEdges, halfEdge)
return halfEdge
}
// NewEdge creates a pair of half-edges, one of them starting at the given vertex.
func (d *DCEL) NewEdge(face1, face2 *Face, vertex *Vertex) (*HalfEdge, *HalfEdge) {
halfEdge := d.NewHalfEdge(face1, vertex, nil)
twin := d.NewHalfEdge(face2, nil, halfEdge)
halfEdge.Twin = twin
return halfEdge, twin
}