106 lines
2.0 KiB
Go
106 lines
2.0 KiB
Go
package geo
|
|
|
|
import "math"
|
|
|
|
const epsilon = 1e-9
|
|
|
|
// Point is a geographic coordinate in decimal degrees.
|
|
type Point struct {
|
|
Longitude float64
|
|
Latitude float64
|
|
}
|
|
|
|
// Ring is one GeoJSON linear ring.
|
|
type Ring []Point
|
|
|
|
// Polygon is a GeoJSON polygon. The first ring is the exterior ring; subsequent
|
|
// rings are holes.
|
|
type Polygon []Ring
|
|
|
|
func polygonContainsPoint(polygon Polygon, p Point) bool {
|
|
if len(polygon) == 0 {
|
|
return false
|
|
}
|
|
if pointOnRing(polygon[0], p) {
|
|
return true
|
|
}
|
|
if !ringContainsPoint(polygon[0], p) {
|
|
return false
|
|
}
|
|
for _, hole := range polygon[1:] {
|
|
if pointOnRing(hole, p) {
|
|
return true
|
|
}
|
|
if ringContainsPoint(hole, p) {
|
|
return false
|
|
}
|
|
}
|
|
return true
|
|
}
|
|
|
|
func ringContainsPoint(ring Ring, p Point) bool {
|
|
inside := false
|
|
n := len(ring)
|
|
if n == 0 {
|
|
return false
|
|
}
|
|
|
|
for i, j := 0, n-1; i < n; j, i = i, i+1 {
|
|
a := ring[j]
|
|
b := ring[i]
|
|
if pointOnSegment(p, a, b) {
|
|
return true
|
|
}
|
|
|
|
intersects := (a.Latitude > p.Latitude) != (b.Latitude > p.Latitude)
|
|
if intersects {
|
|
x := (b.Longitude-a.Longitude)*(p.Latitude-a.Latitude)/(b.Latitude-a.Latitude) + a.Longitude
|
|
if almostEqual(x, p.Longitude) {
|
|
return true
|
|
}
|
|
if x > p.Longitude {
|
|
inside = !inside
|
|
}
|
|
}
|
|
}
|
|
return inside
|
|
}
|
|
|
|
func pointOnRing(ring Ring, p Point) bool {
|
|
n := len(ring)
|
|
if n == 0 {
|
|
return false
|
|
}
|
|
for i, j := 0, n-1; i < n; j, i = i, i+1 {
|
|
if pointOnSegment(p, ring[j], ring[i]) {
|
|
return true
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
|
|
func pointOnSegment(p, a, b Point) bool {
|
|
cross := (p.Latitude-a.Latitude)*(b.Longitude-a.Longitude) - (p.Longitude-a.Longitude)*(b.Latitude-a.Latitude)
|
|
if math.Abs(cross) > epsilon {
|
|
return false
|
|
}
|
|
|
|
minLon, maxLon := minMax(a.Longitude, b.Longitude)
|
|
minLat, maxLat := minMax(a.Latitude, b.Latitude)
|
|
return p.Longitude >= minLon-epsilon &&
|
|
p.Longitude <= maxLon+epsilon &&
|
|
p.Latitude >= minLat-epsilon &&
|
|
p.Latitude <= maxLat+epsilon
|
|
}
|
|
|
|
func minMax(a, b float64) (float64, float64) {
|
|
if a < b {
|
|
return a, b
|
|
}
|
|
return b, a
|
|
}
|
|
|
|
func almostEqual(a, b float64) bool {
|
|
return math.Abs(a-b) <= epsilon
|
|
}
|