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
 		}
 	}