Mercurial > gemma

annotate pkg/octree/polygon.go @ 2498:843f39b9327e octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Handle hole more precisely.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 14:46:49 +0100
parents 98bc023750cf
children 2833ff156cb2
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
1 // This is Free Software under GNU Affero General Public License v >= 3.0
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
2 // without warranty, see README.md and license for details.
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
3 //
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
4 // SPDX-License-Identifier: AGPL-3.0-or-later
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
5 // License-Filename: LICENSES/AGPL-3.0.txt
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
6 //
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
7 // Copyright (C) 2018 by via donau
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
8 // – Österreichische Wasserstraßen-Gesellschaft mbH
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
9 // Software engineering by Intevation GmbH
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
10 //
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
11 // Author(s):
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
12 // * Sascha L. Teichmann <sascha.teichmann@intevation.de>
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
13
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
14 package octree
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
15
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
16 import (
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
17 "bytes"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
18 "encoding/binary"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
19 "fmt"
2498
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
20 "log"
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
21 "math"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
22
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
23 "github.com/tidwall/rtree"
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
24
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
25 "gemma.intevation.de/gemma/pkg/wkb"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
26 )
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
27
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
28 type (
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
29 ring []float64
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
30
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
31 Polygon struct {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
32 // TODO: Implement me!
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
33 rings []ring
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
34
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
35 indices []*rtree.RTree
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
36 }
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
37
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
38 IntersectionType byte
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
39
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
40 lineSegment []float64
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
41 )
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 const (
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
44 IntersectionInside IntersectionType = iota
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 IntersectionOutSide
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46 IntersectionOverlaps
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47 )
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
48
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
49 func (ls lineSegment) Rect(interface{}) ([]float64, []float64) {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
50
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
51 var min, max [2]float64
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
52
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
53 if ls[0] < ls[2] {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
54 min[0] = ls[0]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
55 max[0] = ls[2]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
56 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
57 min[0] = ls[2]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
58 max[0] = ls[0]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
59 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
60
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
61 if ls[1] < ls[3] {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
62 min[1] = ls[1]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
63 max[1] = ls[3]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
64 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
65 min[1] = ls[3]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
66 max[1] = ls[1]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
67 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
68
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
69 return min[:], max[:]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
70 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
71
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
72 func (p *Polygon) Indexify() {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
73 indices := make([]*rtree.RTree, len(p.rings))
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
74
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
75 for i := range indices {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
76 index := rtree.New(nil)
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
77 indices[i] = index
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
78
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
79 rng := p.rings[i]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
80
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
81 for i := 0; i < len(rng); i += 2 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
82 var ls lineSegment
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
83 if i+4 <= len(rng) {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
84 ls = lineSegment(rng[i : i+4])
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
85 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
86 ls = []float64{rng[i], rng[i+1], rng[0], rng[1]}
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
87 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
88 index.Insert(ls)
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
89 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
90 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
91
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
92 p.indices = indices
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
93 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
94
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
95 func (ls lineSegment) intersects(a Box2D) bool {
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
96 p1x := ls[0]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
97 p1y := ls[1]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
98 p2x := ls[2]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
99 p2y := ls[3]
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
100
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
101 left := a.X1
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
102 right := a.X2
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
103 top := a.Y1
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
104 bottom := a.Y2
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
105
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
106 // The direction of the ray
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
107 dx := p2x - p1x
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
108 dy := p2y - p1y
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
109
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
110 min, max := 0.0, 1.0
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
111
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
112 var t0, t1 float64
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
113
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
114 // Left and right sides.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
115 // - If the line is parallel to the y axis.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
116 if dx == 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
117 if p1x < left || p1x > right {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
118 return false
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
119 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
120 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
121 // - Make sure t0 holds the smaller value by checking the direction of the line.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
122 if dx > 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
123 t0 = (left - p1x) / dx
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
124 t1 = (right - p1x) / dx
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
125 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
126 t1 = (left - p1x) / dx
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
127 t0 = (right - p1x) / dx
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
128 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
129
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
130 if t0 > min {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
131 min = t0
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
132 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
133 if t1 < max {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
134 max = t1
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
135 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
136 if min > max || max < 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
137 return false
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
138 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
139 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
140
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
141 // The top and bottom side.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
142 // - If the line is parallel to the x axis.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
143 if dy == 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
144 if p1y < top || p1y > bottom {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
145 return false
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
146 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
147 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
148 // - Make sure t0 holds the smaller value by checking the direction of the line.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
149 if dy > 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
150 t0 = (top - p1y) / dy
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
151 t1 = (bottom - p1y) / dy
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
152 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
153 t1 = (top - p1y) / dy
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
154 t0 = (bottom - p1y) / dy
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
155 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
156
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
157 if t0 > min {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
158 min = t0
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
159 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
160 if t1 < max {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
161 max = t1
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
162 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
163 if min > max || max < 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
164 return false
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
165 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
166 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
167
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
168 // The point of intersection
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
169 // ix = p1x + dx*min
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
170 // iy = p1y + dy*min
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
171 return true
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
172 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
173
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
174 func (ls lineSegment) intersectsLineSegment(o lineSegment) bool {
2495
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
175
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
176 p0 := ls[:2]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
177 p1 := ls[2:4]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
178 p2 := o[:2]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
179 p3 := o[2:4]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
180
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
181 s10x := p1[0] - p0[0]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
182 s10y := p1[1] - p0[1]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
183 s32x := p3[0] - p2[0]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
184 s32y := p3[1] - p2[1]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
185
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
186 den := s10x*s32y - s32x*s10y
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
187
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
188 if den == 0 {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
189 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
190 }
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
191
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
192 denPos := den > 0
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
193
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
194 s02x := p0[0] - p2[0]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
195 s02y := p0[1] - p2[1]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
196
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
197 sNum := s10x*s02y - s10y*s02x
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
198 if sNum < 0 == denPos {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
199 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
200 }
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
201
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
202 tNum := s32x*s02y - s32y*s02x
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
203 if tNum < 0 == denPos {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
204 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
205 }
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
206
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
207 if sNum > den == denPos || tNum > den == denPos {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
208 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
209 }
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
210
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
211 // t := tNum / den
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
212 // intersection at( p0[0] + (t * s10x), p0[1] + (t * s10y) )
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
213 return true
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
214 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
215
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
216 func (p *Polygon) IntersectionBox2D(box Box2D) IntersectionType {
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
217
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
218 if len(p.rings) == 0 {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
219 return IntersectionOutSide
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
220 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
221
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
222 for _, index := range p.indices {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
223 var intersects bool
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
224 index.Search(box, func(item rtree.Item) bool {
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
225 if item.(lineSegment).intersects(box) {
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
226 intersects = true
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
227 return false
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
228 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
229 return true
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
230 })
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
231 if intersects {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
232 return IntersectionOverlaps
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
233 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
234 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
235
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
236 // No intersection -> check inside or outside
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
237 // if an abritrary point is inside or not.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
238 point := []float64{box.X1, box.Y1}
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
239
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
240 // Check holes first: inside a hole means outside.
2498
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
241 if len(p.rings) > 1 {
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
242 for _, hole := range p.rings[1:] {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
243 if hole.contains(point) {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
244 return IntersectionOutSide
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
245 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
246 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
247 }
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
248
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
249 // Check shell
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
250 if p.rings[0].contains(point) {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
251 return IntersectionInside
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
252 }
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
253 return IntersectionOutSide
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
254 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
255
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
256 func (p *Polygon) IntersectionWithTriangle(t *Triangle) IntersectionType {
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
257 box := t.BBox()
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
258 for _, index := range p.indices {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
259 var intersects bool
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
260 index.Search(box, func(item rtree.Item) bool {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
261 ls := item.(lineSegment)
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
262 other := make(lineSegment, 4)
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
263 for i := range t {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
264 other[0] = t[i].X
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
265 other[1] = t[i].Y
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
266 other[2] = t[(i+1)%len(t)].X
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
267 other[3] = t[(i+1)%len(t)].Y
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
268 if ls.intersectsLineSegment(other) {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
269 intersects = true
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
270 return false
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
271 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
272 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
273 return true
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
274 })
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
275 if intersects {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
276 return IntersectionOverlaps
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
277 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
278 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
279 // No intersection -> check inside or outside
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
280 // if an abritrary point is inside or not.
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
281 point := []float64{t[0].X, t[0].Y}
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
282
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
283 // Check holes first: inside a hole means outside.
2498
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
284 if len(p.rings) > 1 {
2494
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
285 for _, hole := range p.rings[1:] {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
286 if hole.contains(point) {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
287 return IntersectionOutSide
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
288 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
289 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
290 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
291
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
292 // Check shell
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
293 if p.rings[0].contains(point) {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
294 return IntersectionInside
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
295 }
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
296 return IntersectionOutSide
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
297 }
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
298
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
299 func (rng ring) isClosed() bool { return (len(rng) / 2) >= 3 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
300
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
301 func (rng ring) contains(point []float64) bool {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
302 if !rng.isClosed() {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
303 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
304 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
305
2498
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
306 end := len(rng)/2 - 1
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
307
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
308 contains := intersectsWithRaycast(point, rng[:2], rng[end*2:end*2+2])
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
309
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
310 for i := 2; i < len(rng); i += 2 {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
311 if intersectsWithRaycast(point, rng[i-2:i], rng[i:i+2]) {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
312 contains = !contains
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
313 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
314 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
315
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
316 return contains
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
317 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
318
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
319 // Using the raycast algorithm, this returns whether or not the passed in point
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
320 // Intersects with the edge drawn by the passed in start and end points.
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
321 // Original implementation: http://rosettacode.org/wiki/Ray-casting_algorithm#Go
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
322 func intersectsWithRaycast(point, start, end []float64) bool {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
323
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
324 // Always ensure that the the first point
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
325 // has a y coordinate that is less than the second point
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
326 if start[1] > end[1] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
327 // Switch the points if otherwise.
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
328 start, end = end, start
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
329 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
330
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
331 // Move the point's y coordinate
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
332 // outside of the bounds of the testing region
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
333 // so we can start drawing a ray
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
334 for point[1] == start[1] || point[1] == end[1] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
335 y := math.Nextafter(point[1], math.Inf(1))
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
336 point = []float64{point[0], y}
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
337 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
338
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
339 // If we are outside of the polygon, indicate so.
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
340 if point[1] < start[1] || point[1] > end[1] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
341 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
342 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
343
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
344 if start[0] > end[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
345 if point[0] > start[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
346 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
347 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
348 if point[0] < end[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
349 return true
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
350 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
351 } else {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
352 if point[0] > end[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
353 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
354 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
355 if point[0] < start[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
356 return true
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
357 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
358 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
359
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
360 raySlope := (point[1] - start[1]) / (point[0] - start[0])
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
361 diagSlope := (end[1] - start[1]) / (end[0] - start[0])
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
362
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
363 return raySlope >= diagSlope
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
364 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
365
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
366 func (p *Polygon) FromWKB(data []byte) error {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
367
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
368 r := bytes.NewReader(data)
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
369
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
370 endian, err := r.ReadByte()
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
371
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
372 var order binary.ByteOrder
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
373
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
374 switch {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
375 case err != nil:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
376 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
377 case endian == wkb.NDR:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
378 order = binary.LittleEndian
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
379 case endian == wkb.XDR:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
380 order = binary.BigEndian
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
381 default:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
382 return fmt.Errorf("unknown byte order %x", endian)
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
383 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
384
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
385 var geomType uint32
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
386 err = binary.Read(r, order, &geomType)
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
387
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
388 switch {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
389 case err != nil:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
390 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
391 case geomType != wkb.Polygon:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
392 return fmt.Errorf("unknown geometry type %x", geomType)
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
393 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
394
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
395 var numRings uint32
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
396 if err = binary.Read(r, order, &numRings); err != nil {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
397 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
398 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
399
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
400 rngs := make([]ring, numRings)
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
401
2498
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
402 log.Printf("info: Number of rings: %d\n", len(rngs))
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
403
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
404 for rng := uint32(0); rng < numRings; rng++ {
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
405 var numVertices uint32
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
406 if err = binary.Read(r, order, &numVertices); err != nil {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
407 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
408 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
409
2498
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
410 log.Printf("info: Number of vertices in ring %d: %d\n", rng, numVertices)
843f39b9327e Handle hole more precisely.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2495
diff changeset
411
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
412 numVertices *= 2
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
413 vertices := make([]float64, numVertices)
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
414
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
415 for v := uint32(0); v < numVertices; v += 2 {
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
416 var lat, lon uint64
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
417 if err = binary.Read(r, order, &lat); err != nil {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
418 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
419 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
420 if err = binary.Read(r, order, &lon); err != nil {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
421 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
422 }
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
423 vertices[v] = math.Float64frombits(lat)
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
424 vertices[v+1] = math.Float64frombits(lon)
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
425 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
426
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
427 rngs[rng] = vertices
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
428 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
429
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
430 p.rings = rngs
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
431
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
432 return nil
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
433 }