-
Notifications
You must be signed in to change notification settings - Fork 0
/
delaunay.js
195 lines (170 loc) · 5.07 KB
/
delaunay.js
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
function Triangle(a, b, c, type) {
this.a = a
this.b = b
this.c = c
if(a.type && b.type && c.type){
if(a.type == "t" || b.type == "t" || c.type == "t"){
this.fill = "#D1E751"
}
}
var A = b.x - a.x,
B = b.y - a.y,
C = c.x - a.x,
D = c.y - a.y,
E = A * (a.x + b.x) + B * (a.y + b.y),
F = C * (a.x + c.x) + D * (a.y + c.y),
G = 2 * (A * (c.y - b.y) - B * (c.x - b.x)),
minx, miny, dx, dy
/* If the points of the triangle are collinear, then just find the
* extremes and use the midpoint as the center of the circumcircle. */
if(Math.abs(G) < 0.000001) {
minx = Math.min(a.x, b.x, c.x)
miny = Math.min(a.y, b.y, c.y)
dx = (Math.max(a.x, b.x, c.x) - minx) * 0.5
dy = (Math.max(a.y, b.y, c.y) - miny) * 0.5
this.x = minx + dx
this.y = miny + dy
this.r = dx * dx + dy * dy
}
else {
this.x = (D*E - B*F) / G
this.y = (A*F - C*E) / G
dx = this.x - a.x
dy = this.y - a.y
this.r = dx * dx + dy * dy
}
}
Triangle.prototype.draw = function(ctx) {
ctx.beginPath()
ctx.moveTo(this.a.x, this.a.y)
ctx.lineTo(this.b.x, this.b.y)
ctx.lineTo(this.c.x, this.c.y)
ctx.closePath()
ctx.stroke()
}
Triangle.prototype.drawRaleaph = function(paper) {
var path = paper.path("M " + this.a.x + " " + this.a.y + " L " + this.b.x + " " + this.b.y + " L " + this.c.x + " " + this.c.y + " z")
if(this.fill){
path.attr({fill: this.fill})
}
}
function byX(a, b) {
return b.x - a.x
}
function dedup(edges) {
var j = edges.length,
a, b, i, m, n
outer: while(j) {
b = edges[--j]
a = edges[--j]
i = j
while(i) {
n = edges[--i]
m = edges[--i]
if((a === m && b === n) || (a === n && b === m)) {
edges.splice(j, 2)
edges.splice(i, 2)
j -= 2
continue outer
}
}
}
}
function triangulate(vertices) {
/* Bail if there aren't enough vertices to form any triangles. */
if(vertices.length < 3)
return []
/* Ensure the vertex array is in order of descending X coordinate
* (which is needed to ensure a subquadratic runtime), and then find
* the bounding box around the points. */
vertices.sort(byX)
var i = vertices.length - 1,
xmin = vertices[i].x,
xmax = vertices[0].x,
ymin = vertices[i].y,
ymax = ymin
while(i--) {
if(vertices[i].y < ymin) ymin = vertices[i].y
if(vertices[i].y > ymax) ymax = vertices[i].y
}
/* Find a supertriangle, which is a triangle that surrounds all the
* vertices. This is used like something of a sentinel value to remove
* cases in the main algorithm, and is removed before we return any
* results.
*
* Once found, put it in the "open" list. (The "open" list is for
* triangles who may still need to be considered; the "closed" list is
* for triangles which do not.) */
var dx = xmax - xmin,
dy = ymax - ymin,
dmax = (dx > dy) ? dx : dy,
xmid = (xmax + xmin) * 0.5,
ymid = (ymax + ymin) * 0.5,
open = [
new Triangle(
{x: xmid - 20 * dmax, y: ymid - dmax, __sentinel: true},
{x: xmid , y: ymid + 20 * dmax, __sentinel: true},
{x: xmid + 20 * dmax, y: ymid - dmax, __sentinel: true}
)
],
closed = [],
edges = [],
j, a, b
/* Incrementally add each vertex to the mesh. */
i = vertices.length
while(i--) {
/* For each open triangle, check to see if the current point is
* inside it's circumcircle. If it is, remove the triangle and add
* it's edges to an edge list. */
edges.length = 0
j = open.length
while(j--) {
/* If this point is to the right of this triangle's circumcircle,
* then this triangle should never get checked again. Remove it
* from the open list, add it to the closed list, and skip. */
dx = vertices[i].x - open[j].x
if(dx > 0 && dx * dx > open[j].r) {
closed.push(open[j])
open.splice(j, 1)
continue
}
/* If not, skip this triangle. */
dy = vertices[i].y - open[j].y
if(dx * dx + dy * dy > open[j].r)
continue
/* Remove the triangle and add it's edges to the edge list. */
edges.push(
open[j].a, open[j].b,
open[j].b, open[j].c,
open[j].c, open[j].a
)
open.splice(j, 1)
}
/* Remove any doubled edges. */
dedup(edges)
/* Add a new triangle for each edge. */
j = edges.length
while(j) {
b = edges[--j]
a = edges[--j]
open.push(new Triangle(a, b, vertices[i]))
}
}
/* Copy any remaining open triangles to the closed list, and then
* remove any triangles that share a vertex with the supertriangle. */
Array.prototype.push.apply(closed, open)
i = closed.length
while(i--)
if(closed[i].a.__sentinel ||
closed[i].b.__sentinel ||
closed[i].c.__sentinel)
closed.splice(i, 1)
/* Yay, we're done! */
return closed
}
if (typeof module !== 'undefined') {
module.exports = {
Triangle: Triangle,
triangulate: triangulate
}
}