Mercurial > gemma
changeset 4729:1137c5a18242 stack-polygons
Virtualized point in polygon test with an interface to be usable for contours, too.
author | Sascha L. Teichmann <teichmann@intevation.de> |
---|---|
date | Thu, 17 Oct 2019 23:33:20 +0200 |
parents | bfbdcf67ae55 |
children | 76dbeab4a0d6 |
files | pkg/octree/polygon.go |
diffstat | 1 files changed, 47 insertions(+), 27 deletions(-) [+] |
line wrap: on
line diff
--- a/pkg/octree/polygon.go Thu Oct 17 22:37:04 2019 +0200 +++ b/pkg/octree/polygon.go Thu Oct 17 23:33:20 2019 +0200 @@ -281,19 +281,18 @@ // No intersection -> check inside or outside // if an abritrary point is inside or not. - point := []float64{box.X1, box.Y1} // Check holes first: inside a hole means outside. if len(p.rings) > 1 { for _, hole := range p.rings[1:] { - if hole.contains(point) { + if contains(hole, box.X1, box.Y1) { return IntersectionOutSide } } } // Check shell - if p.rings[0].contains(point) { + if contains(p.rings[0], box.X1, box.Y1) { return IntersectionInside } return IntersectionOutSide @@ -324,37 +323,59 @@ } // No intersection -> check inside or outside // if an abritrary point is inside or not. - point := []float64{t[0].X, t[0].Y} + pX, pY := t[0].X, t[0].Y // Check holes first: inside a hole means outside. if len(p.rings) > 1 { for _, hole := range p.rings[1:] { - if hole.contains(point) { + if contains(hole, pX, pY) { return IntersectionOutSide } } } // Check shell - if p.rings[0].contains(point) { + if contains(p.rings[0], pX, pY) { return IntersectionInside } return IntersectionOutSide } -func (rng ring) isClosed() bool { return (len(rng) / 2) >= 3 } +func (rng ring) closed() bool { + return (len(rng) / 2) >= 3 +} + +func (rng ring) length() int { + return len(rng) / 2 +} -func (rng ring) contains(point []float64) bool { - if !rng.isClosed() { +func (rng ring) point(i int) (float64, float64) { + i *= 2 + return rng[i], rng[i+1] +} + +type segments interface { + closed() bool + length() int + point(int) (float64, float64) +} + +func contains(s segments, pX, pY float64) bool { + if !s.closed() { return false } - end := len(rng)/2 - 1 + n := s.length() + + sX, sY := s.point(0) + eX, eY := s.point(n - 1) - contains := intersectsWithRaycast(point, rng[:2], rng[end*2:end*2+2]) + contains := intersectsWithRaycast(pX, pY, sX, sY, eX, eY) - for i := 2; i < len(rng); i += 2 { - if intersectsWithRaycast(point, rng[i-2:i], rng[i:i+2]) { + for i := 1; i < n; i++ { + sX, sY := s.point(i - 1) + eX, eY := s.point(i) + if intersectsWithRaycast(pX, pY, sX, sY, eX, eY) { contains = !contains } } @@ -365,46 +386,45 @@ // Using the raycast algorithm, this returns whether or not the passed in point // Intersects with the edge drawn by the passed in start and end points. // Original implementation: http://rosettacode.org/wiki/Ray-casting_algorithm#Go -func intersectsWithRaycast(point, start, end []float64) bool { +func intersectsWithRaycast(pX, pY, sX, sY, eX, eY float64) bool { // Always ensure that the the first point // has a y coordinate that is less than the second point - if start[1] > end[1] { + if sY > eY { // Switch the points if otherwise. - start, end = end, start + sX, sY, eX, eY = eX, eY, sX, sY } // Move the point's y coordinate // outside of the bounds of the testing region // so we can start drawing a ray - for point[1] == start[1] || point[1] == end[1] { - y := math.Nextafter(point[1], math.Inf(1)) - point = []float64{point[0], y} + for pY == sY || pY == eY { + pY = math.Nextafter(pY, math.Inf(1)) } // If we are outside of the polygon, indicate so. - if point[1] < start[1] || point[1] > end[1] { + if pY < sY || pY > eY { return false } - if start[0] > end[0] { - if point[0] > start[0] { + if sX > eX { + if pX > sX { return false } - if point[0] < end[0] { + if pX < eX { return true } } else { - if point[0] > end[0] { + if pX > eX { return false } - if point[0] < start[0] { + if pX < sX { return true } } - raySlope := (point[1] - start[1]) / (point[0] - start[0]) - diagSlope := (end[1] - start[1]) / (end[0] - start[0]) + raySlope := (pY - sY) / (pX - sX) + diagSlope := (eY - sY) / (eX - sX) return raySlope >= diagSlope }