-
Notifications
You must be signed in to change notification settings - Fork 19
/
dcel.go
112 lines (88 loc) · 2.42 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
package geom
func newDCELFromGeometries(a, b Geometry) *doublyConnectedEdgeList {
ghosts := createGhosts(a, b)
a, b, ghosts = reNodeGeometries(a, b, ghosts)
interactions := findInteractionPoints([]Geometry{a, b, ghosts.AsGeometry()})
dcel := newDCEL()
dcel.addVertices(interactions)
dcel.addGhosts(ghosts, interactions)
dcel.addGeometry(a, operandA, interactions)
dcel.addGeometry(b, operandB, interactions)
dcel.fixVertices()
dcel.assignFaces()
dcel.populateInSetLabels()
return dcel
}
func newDCEL() *doublyConnectedEdgeList {
return &doublyConnectedEdgeList{
faces: nil,
halfEdges: make(map[[2]XY]*halfEdgeRecord),
vertices: make(map[XY]*vertexRecord),
}
}
type doublyConnectedEdgeList struct {
faces []*faceRecord // only populated in the overlay
halfEdges map[[2]XY]*halfEdgeRecord
vertices map[XY]*vertexRecord
}
type faceRecord struct {
cycle *halfEdgeRecord
// inSet encodes whether this face is part of the input geometry for each
// operand.
inSet [2]bool
extracted bool
}
type halfEdgeRecord struct {
origin *vertexRecord
twin *halfEdgeRecord
incident *faceRecord // only populated in the overlay
next, prev *halfEdgeRecord
seq Sequence
// srcEdge encodes whether or not this edge is explicitly appears as part
// of the input geometries.
srcEdge [2]bool
// srcFace encodes whether or not this edge explicitly borders onto a face
// in the input geometries.
srcFace [2]bool
// inSet encodes whether or not this edge is (explicitly or implicitly)
// part of the input geometry for each operand.
inSet [2]bool
extracted bool
}
type vertexRecord struct {
coords XY
incidents map[*halfEdgeRecord]struct{}
// src encodes whether on not this vertex explicitly appears in the input
// geometries.
src [2]bool
// inSet encodes whether or not this vertex is part of each input geometry
// (although it might not be explicitly encoded there).
inSet [2]bool
locations [2]location
extracted bool
}
func forEachEdgeInCycle(start *halfEdgeRecord, fn func(*halfEdgeRecord)) {
e := start
for {
fn(e)
e = e.next
if e == start {
break
}
}
}
// operand represents either the first (A) or second (B) geometry in a binary
// operation (such as Union or Covers).
type operand int
const (
operandA operand = 0
operandB operand = 1
)
func forEachOperand(fn func(operand operand)) {
fn(operandA)
fn(operandB)
}
type location struct {
interior bool
boundary bool
}