Mercurial > gemma
changeset 4538:46c9a731a686 iso-areas
Use custom binary search in triangle indices.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Thu, 26 Sep 2019 10:58:22 +0200 |
parents | e0d04cd8f992 |
children | 99928231b679 |
files | cmd/isoareas/main.go |
diffstat | 1 files changed, 17 insertions(+), 5 deletions(-) [+] |
line wrap: on
line diff
--- a/cmd/isoareas/main.go Wed Sep 25 22:01:05 2019 +0200 +++ b/cmd/isoareas/main.go Thu Sep 26 10:58:22 2019 +0200 @@ -19,7 +19,6 @@ "log" "math" "os" - "sort" "strconv" "strings" "time" @@ -165,16 +164,29 @@ return t.Halfedges[idx : idx+3] } +func contains(needle int32, haystack []int32) bool { + lo, hi := 0, len(haystack)-1 + for lo <= hi { + mid := (hi-lo)/2 + lo + switch v := haystack[mid]; { + case v < needle: + lo = mid + 1 + case v > needle: + hi = mid - 1 + default: + return true + } + } + return false +} + func inner(t *octree.Triangulation, idx int32, indices []int32) bool { for _, n := range neighbors(t, idx) { if n < 0 { return false } - n /= 3 - if p := sort.Search(len(indices), func(i int) bool { - return indices[i] >= n - }); p >= len(indices) || indices[p] != n { + if !contains(n/3, indices) { return false } }