Mercurial > gemma

annotate pkg/octree/hull.go @ 2564:27501719e79b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
STT tree: deduplicated som code.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 11 Mar 2019 10:49:16 +0100
parents 620038ade708
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2483
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 // Copyright (C) 2018 Michael Fogleman
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 // Permission is hereby granted, free of charge, to any person obtaining
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 // a copy of this software and associated documentation files (the "Software"),
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 // to deal in the Software without restriction, including without limitation
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 // and/or sell copies of the Software, and to permit persons to whom the
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8 // Software is furnished to do so, subject to the following conditions:
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 // The above copyright notice and this permission notice shall be included
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 // in all copies or substantial portions of the Software.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 //
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
16 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
18 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
19
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
20 package octree
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
21
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
22 import "sort"
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
23
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
24 func cross2D(p, a, b Vertex) float64 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
25 return (a.X-p.X)*(b.Y-p.Y) - (a.Y-p.Y)*(b.X-p.X)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
26 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
27
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
28 // ConvexHull returns the convex hull of the provided points.
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
29 func ConvexHull(points []Vertex) []Vertex {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
30 // copy points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
31 pointsCopy := make([]Vertex, len(points))
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
32 copy(pointsCopy, points)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
33 points = pointsCopy
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
34
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
35 // sort points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36 sort.Slice(points, func(i, j int) bool {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37 a := points[i]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
38 b := points[j]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
39 if a.X != b.X {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
40 return a.X < b.X
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 return a.Y < b.Y
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 })
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 // filter nearly-duplicate points
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46 distinctPoints := points[:0]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47 for i, p := range points {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48 if i > 0 && p.SquaredDistance2D(points[i-1]) < eps {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
49 continue
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
50 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
51 distinctPoints = append(distinctPoints, p)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
52 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
53 points = distinctPoints
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
54
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
55 // find upper and lower portions
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
56 var U, L []Vertex
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
57 for _, p := range points {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
58 for len(U) > 1 && cross2D(U[len(U)-2], U[len(U)-1], p) > 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
59 U = U[:len(U)-1]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
60 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
61 for len(L) > 1 && cross2D(L[len(L)-2], L[len(L)-1], p) < 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
62 L = L[:len(L)-1]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
63 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
64 U = append(U, p)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
65 L = append(L, p)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
66 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
67
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
68 // reverse upper portion
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
69 for i, j := 0, len(U)-1; i < j; i, j = i+1, j-1 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
70 U[i], U[j] = U[j], U[i]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
71 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
72
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
73 // construct complete hull
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
74 if len(U) > 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
75 U = U[:len(U)-1]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
76 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
77 if len(L) > 0 {
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
78 L = L[:len(L)-1]
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
79 }
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
80 return append(L, U...)
620038ade708 Incorporated fogleman's fast Delaunay triangulation adjuted to our vertex model.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
81 }