-
Notifications
You must be signed in to change notification settings - Fork 3
/
util.go
91 lines (75 loc) · 2.76 KB
/
util.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
package location
import (
"fmt"
"math"
)
// InRangeLL accepts latitude and longitude values to create 2 points. The points are
// used to determine their range, then the range is used to determine if the distance
// is less than that range.
func InRangeLL(lat1 float64, lon1 float64, lat2 float64, lon2 float64, distance float64) (bool, error) {
point1 := Point{Latitude: lat1, Longitude: lon1}
point2 := Point{Latitude: lat2, Longitude: lon2}
return point1.InRange(&point2, distance)
}
// createSquare - When there are only two points in a geometry, instead of using a
// line, create a square/rectangle out of the max/mins
func createSquare(geometry []Point) ([]Point, error) {
if len(geometry) != 2 {
return nil, fmt.Errorf("length of geometry must be 2: %d", len(geometry))
}
minLat := math.Min(geometry[0].Latitude, geometry[1].Latitude)
maxLat := math.Max(geometry[0].Latitude, geometry[1].Latitude)
minLon := math.Min(geometry[0].Longitude, geometry[1].Longitude)
maxLon := math.Max(geometry[0].Longitude, geometry[1].Longitude)
points := []Point{
Point{Latitude: minLat, Longitude: minLon},
Point{Latitude: minLat, Longitude: maxLon},
Point{Latitude: maxLat, Longitude: maxLon},
Point{Latitude: maxLat, Longitude: minLon},
}
return points, nil
}
// Find the number of times that the point intesects with
// the edges of the geometry when extending a ray towards the
// edges of the geometry.
func findIntersection(geometry []Point, point Point) int {
intersected := 0 // number of times an edge is hit
for i, geoPoint := range geometry {
curr := geoPoint
nxt := geometry[(i+1)%len(geometry)]
if curr.Y() == nxt.Y() {
continue
}
// determine if an intersection occurred for this point in the geometry and the point
if math.Max(curr.Y(), nxt.Y()) >= point.Y() && point.Y() > math.Min(curr.Y(), nxt.Y()) {
if point.X() <= math.Max(curr.X(), nxt.X()) {
xinters := (point.Y()-curr.Y())*(nxt.X()-curr.X())/(nxt.Y()-curr.Y()) + curr.X()
if curr.X() == nxt.X() || point.X() <= xinters {
intersected += 1
}
}
}
}
return intersected
}
// InArea will determine if a point exists in a geometry. The algorithm can be found
// here: https://www.eecs.umich.edu/courses/eecs380/HANDOUTS/PROJ2/InsidePoly.html
func InArea(geometry []Point, point Point) (bool, error) {
if len(geometry) < 2 {
return false, fmt.Errorf("geometry must be a set of at least 2 points")
}
var geoPoints []Point
if len(geometry) == 2 {
points, err := createSquare(geometry)
if err != nil {
return false, err
}
geoPoints = points
} else {
geoPoints = geometry
}
intersected := findIntersection(geoPoints, point)
// There will be an odd number for points in a geometry, even for those that
// do not reside in the geometry
return intersected%2 == 1, nil
}