Mercurial > gemma

annotate pkg/octree/polygon.go @ 2495:98bc023750cf octree-diff

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Impelemented line segment / line segment intersection test.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 04 Mar 2019 12:45:44 +0100
parents a727e0426240
children 843f39b9327e
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"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
20 "math"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
21
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
22 "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
23
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
24 "gemma.intevation.de/gemma/pkg/wkb"
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
25 )
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
26
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
27 type (
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
28 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
29
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
30 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
31 // 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
32 rings []ring
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
33
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
34 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
35 }
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
36
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
37 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
38
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
39 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
40 )
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
41
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
42 const (
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
43 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
44 IntersectionOutSide
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
45 IntersectionOverlaps
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
46 )
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
47
2492
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
48 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
49
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
50 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
51
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
52 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
53 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
54 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
55 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
56 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
57 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
58 }
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 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
61 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
62 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
63 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
64 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
65 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
66 }
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 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
69 }
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 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
72 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
73
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
74 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
75 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
76 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
77
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
78 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
79
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
80 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
81 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
82 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
83 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
84 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
85 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
86 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
87 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
88 }
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 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
92 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
93
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
94 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
95 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
96 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
97 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
98 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
99
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
100 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
101 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
102 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
103 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
104
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
105 // 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
106 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
107 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
108
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
109 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
110
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
111 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
112
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
113 // 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
114 // - 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
115 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
116 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
117 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
118 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
119 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
120 // - 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
121 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
122 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
123 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
124 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
125 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
126 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
127 }
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 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
130 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
131 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
132 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
133 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
134 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
135 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
136 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
137 }
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 // 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
141 // - 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
142 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
143 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
144 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
145 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
146 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
147 // - 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
148 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
149 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
150 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
151 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
152 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
153 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
154 }
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 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
157 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
158 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
159 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
160 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
161 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
162 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
163 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
164 }
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 // 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
168 // 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
169 // 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
170 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
171 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
172
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
173 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
174
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
175 p0 := ls[:2]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
176 p1 := ls[2:4]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
177 p2 := o[:2]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
178 p3 := o[2:4]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
179
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
180 s10x := p1[0] - p0[0]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
181 s10y := p1[1] - p0[1]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
182 s32x := p3[0] - p2[0]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
183 s32y := p3[1] - p2[1]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
184
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
185 den := s10x*s32y - s32x*s10y
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
186
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
187 if den == 0 {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
188 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
189 }
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 denPos := den > 0
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
192
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
193 s02x := p0[0] - p2[0]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
194 s02y := p0[1] - p2[1]
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
195
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
196 sNum := s10x*s02y - s10y*s02x
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
197 if sNum < 0 == denPos {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
198 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
199 }
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 tNum := s32x*s02y - s32y*s02x
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
202 if tNum < 0 == denPos {
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
203 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
204 }
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 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
207 return false
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
208 }
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 // t := tNum / den
98bc023750cf Impelemented line segment / line segment intersection test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2494
diff changeset
211 // 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
212 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
213 }
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
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
215 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
216
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
217 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
218 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
219 }
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 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
222 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
223 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
224 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
225 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
226 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
227 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
228 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
229 })
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
230 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
231 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
232 }
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 // 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
236 // 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
237 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
238
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
239 // Check holes first: inside a hole means outside.
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2490
diff changeset
240 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
241 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
242 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
243 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
244 }
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 }
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
247
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 // 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
249 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
250 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
251 }
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
252 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
253 }
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 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
256 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
257 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
258 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
259 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
260 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
261 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
262 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
263 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
264 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
265 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
266 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
267 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
268 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
269 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
270 }
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 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
273 })
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 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
275 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
276 }
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 // 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
279 // 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
280 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
281
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 // Check holes first: inside a hole means 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
283 if len(p.rings) > 0 {
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2492
diff changeset
284 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
285 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
286 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
287 }
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 // 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
292 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
293 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
294 }
2488
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents:
diff changeset
295 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
296 }
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
297
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
298 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
299
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
300 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
301 if !rng.isClosed() {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
302 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
303 }
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 contains := intersectsWithRaycast(point, rng[:2], rng[len(rng)-2:len(rng)])
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
306
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
307 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
308 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
309 contains = !contains
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
310 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
311 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
312
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
313 return contains
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 // 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
317 // 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
318 // 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
319 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
320
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
321 // 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
322 // 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
323 if start[1] > end[1] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
324 // Switch the points if otherwise.
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
325 start, end = end, start
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
326 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
327
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
328 // Move the point's y coordinate
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
329 // 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
330 // 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
331 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
332 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
333 point = []float64{point[0], y}
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
334 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
335
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
336 // 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
337 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
338 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
339 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
340
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
341 if start[0] > end[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
342 if point[0] > start[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
343 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
344 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
345 if point[0] < end[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
346 return true
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 } else {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
349 if point[0] > end[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
350 return false
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
351 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
352 if point[0] < start[0] {
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
353 return true
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 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
356
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
357 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
358 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
359
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
360 return raySlope >= diagSlope
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
361 }
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
362
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
363 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
364
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
365 r := bytes.NewReader(data)
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
366
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
367 endian, err := r.ReadByte()
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
368
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
369 var order binary.ByteOrder
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
370
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
371 switch {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
372 case err != nil:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
373 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
374 case endian == wkb.NDR:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
375 order = binary.LittleEndian
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
376 case endian == wkb.XDR:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
377 order = binary.BigEndian
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
378 default:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
379 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
380 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
381
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
382 var geomType uint32
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
383 err = binary.Read(r, order, &geomType)
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 switch {
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
386 case err != nil:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
387 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
388 case geomType != wkb.Polygon:
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
389 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
390 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
391
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
392 var numRings uint32
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
393 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
394 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
395 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
396
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
397 rngs := make([]ring, numRings)
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
398
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
399 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
400 var numVertices uint32
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
401 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
402 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
403 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
404
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
405 numVertices *= 2
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
406 vertices := make([]float64, numVertices)
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
407
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
408 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
409 var lat, lon uint64
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
410 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
411 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
412 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
413 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
414 return err
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
415 }
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
416 vertices[v] = math.Float64frombits(lat)
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
417 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
418 }
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
419
2490
c9164ff98871 Started with point in polygon check.
Sascha L. Teichmann <sascha.teichmann@intevation.de>
parents: 2489
diff changeset
420 rngs[rng] = vertices
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
421 }
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 p.rings = rngs
2489
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
424
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
425 return nil
4f292ff74d9e Added a WKB reader for clipping polygon.
Sascha L. Teichmann <teichmann@intevation.de>
parents: 2488
diff changeset
426 }