Mercurial > gemma
changeset 2494:a727e0426240 octree-diff
More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Mon, 04 Mar 2019 12:27:56 +0100 |
parents | e3487fa9284d |
children | 98bc023750cf |
files | pkg/octree/polygon.go pkg/octree/vertex.go |
diffstat | 2 files changed, 59 insertions(+), 4 deletions(-) [+] |
line wrap: on
line diff
--- a/pkg/octree/polygon.go Mon Mar 04 11:56:07 2019 +0100 +++ b/pkg/octree/polygon.go Mon Mar 04 12:27:56 2019 +0100 @@ -91,7 +91,7 @@ p.indices = indices } -func (a Box2D) InterectsSegment(ls lineSegment) bool { +func (ls lineSegment) intersects(a Box2D) bool { p1x := ls[0] p1y := ls[1] p2x := ls[2] @@ -170,6 +170,11 @@ return true } +func (ls lineSegment) intersectsLineSegment(o lineSegment) bool { + // TODO: Implement me! + return false +} + func (p *Polygon) IntersectionBox2D(box Box2D) IntersectionType { if len(p.rings) == 0 { @@ -179,8 +184,7 @@ for _, index := range p.indices { var intersects bool index.Search(box, func(item rtree.Item) bool { - ls := item.(lineSegment) - if box.InterectsSegment(ls) { + if item.(lineSegment).intersects(box) { intersects = true return false } @@ -203,6 +207,8 @@ } } } + + // Check shell if p.rings[0].contains(point) { return IntersectionInside } @@ -210,7 +216,45 @@ } func (p *Polygon) IntersectionWithTriangle(t *Triangle) IntersectionType { - // TODO: Implement me + box := t.BBox() + for _, index := range p.indices { + var intersects bool + index.Search(box, func(item rtree.Item) bool { + ls := item.(lineSegment) + other := make(lineSegment, 4) + for i := range t { + other[0] = t[i].X + other[1] = t[i].Y + other[2] = t[(i+1)%len(t)].X + other[3] = t[(i+1)%len(t)].Y + if ls.intersectsLineSegment(other) { + intersects = true + return false + } + } + return true + }) + if intersects { + return IntersectionOverlaps + } + } + // No intersection -> check inside or outside + // if an abritrary point is inside or not. + point := []float64{t[0].X, t[0].Y} + + // Check holes first: inside a hole means outside. + if len(p.rings) > 0 { + for _, hole := range p.rings[1:] { + if hole.contains(point) { + return IntersectionOutSide + } + } + } + + // Check shell + if p.rings[0].contains(point) { + return IntersectionInside + } return IntersectionOutSide }
--- a/pkg/octree/vertex.go Mon Mar 04 11:56:07 2019 +0100 +++ b/pkg/octree/vertex.go Mon Mar 04 12:27:56 2019 +0100 @@ -88,6 +88,17 @@ } } +func (t *Triangle) BBox() Box2D { + minX := math.Min(math.Min(t[0].X, t[1].X), t[2].X) + maxX := math.Max(math.Max(t[0].X, t[1].X), t[2].X) + minY := math.Min(math.Min(t[0].Y, t[1].Y), t[2].Y) + maxY := math.Max(math.Max(t[0].Y, t[1].Y), t[2].Y) + return Box2D{ + X1: minX, Y1: minY, + X2: maxX, Y2: maxY, + } +} + func (p Plane3D) Z(x, y float64) float64 { // p.A*x + p.B*y + p.C*z + p.D = 0 return -(p.A*x + p.B*y + p.D) / p.C