gemma: pkg/octree/polygon.go annotate

annotate pkg/octree/polygon.go @ 2575:59e7a011d347

Morphological differences: Moved TIN clipping to octree package and hide the technical details there.

author	Sascha L. Teichmann <sascha.teichmann@intevation.de>
date	Mon, 11 Mar 2019 14:50:04 +0100
parents	2833ff156cb2
children	857bb070b9f1

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"
2574 2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	18 "context"
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	19 "database/sql"
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	20 "encoding/binary"
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	21 "fmt"
2498 843f39b9327e Handle hole more precisely. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2495 diff changeset	22 "log"
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	23 "math"
2574 2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	24 "time"
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	25
2492 10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	26 "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	27
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	28 "gemma.intevation.de/gemma/pkg/wkb"
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	29 )
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	30
2492 10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	31 type (
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	32 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	33
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	34 Polygon struct {
2574 2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	35 rings []ring
2492 10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	36 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	37 }
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	38
2492 10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	39 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	40
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	41 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	42 )
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	43
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	44 const (
2574 2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	45 clippingPolygonSQL = `
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	46 WITH joined AS (
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	47 SELECT
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	48 sr.area AS area,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	49 sr.date_info AS date_info
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	50 FROM waterway.sounding_results sr JOIN
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	51 waterway.bottlenecks bn ON sr.bottleneck_id = bn.id
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	52 WHERE bn.bottleneck_id = $1
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	53 )
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	54 SELECT ST_AsBinary(
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	55 ST_intersection(
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	56 (SELECT ST_Transform(area::geometry, $2::int) FROM joined WHERE date_info = $3::date),
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	57 (SELECT ST_Transform(area::geometry, $2::int) FROM joined WHERE date_info = $4::date)
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	58 )
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	59 ) AS area
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	60 `
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	61 )
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	62
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	63 const (
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	64 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	65 IntersectionOutSide
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	66 IntersectionOverlaps
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	67 )
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	68
2574 2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	69 func LoadClippingPolygon(
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	70 ctx context.Context,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	71 conn *sql.Conn,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	72 epsg uint32,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	73 bottleneck string,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	74 first, second time.Time,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	75 ) (*Polygon, error) {
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	76
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	77 var clip []byte
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	78
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	79 if err := conn.QueryRowContext(
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	80 ctx, clippingPolygonSQL,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	81 bottleneck,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	82 epsg,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	83 first, second,
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	84 ).Scan(&clip); err != nil {
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	85 return nil, err
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	86 }
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	87
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	88 var polygon Polygon
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	89 if err := polygon.FromWKB(clip); err != nil {
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	90 return nil, err
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	91 }
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	92 polygon.Indexify()
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	93 return &polygon, nil
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	94 }
2833ff156cb2 Morphological differences: Moved loading of clipping polygon into octree package. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2498 diff changeset	95
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 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	97
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	98 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	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 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	101 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	102 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	103 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	104 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	105 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	106 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	107
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	108 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	109 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	110 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	111 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	112 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	113 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	114 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	115
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	116 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	117 }
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 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	120 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	121
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	122 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	123 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	124 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	125
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	126 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	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 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	129 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	130 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	131 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	132 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	133 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	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 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	136 }
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 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	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
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	142 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	143 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	144 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	145 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	146 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	147
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	148 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	149 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	150 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	151 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	152
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	153 // 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	154 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	155 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	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 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	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 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	160
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	161 // 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	162 // - 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	163 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	164 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	165 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	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 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	168 // - 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	169 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	170 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	171 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	172 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	173 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	174 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	175 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	176
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	177 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	178 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	179 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	180 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	181 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	182 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	183 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	184 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	185 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	186 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	187
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	188 // 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	189 // - 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	190 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	191 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	192 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	193 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	194 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	195 // - 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	196 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	197 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	198 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	199 } else {
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	200 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	201 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	202 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	203
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	204 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	205 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	206 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	207 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	208 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	209 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	210 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	211 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	212 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	213 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	214
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	215 // 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	216 // 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	217 // 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	218 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	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
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	221 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	222
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	223 p0 := ls[:2]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	224 p1 := ls[2:4]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	225 p2 := o[:2]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	226 p3 := o[2:4]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	227
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	228 s10x := p1[0] - p0[0]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	229 s10y := p1[1] - p0[1]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	230 s32x := p3[0] - p2[0]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	231 s32y := p3[1] - p2[1]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	232
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	233 den := s10xs32y - s32xs10y
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	234
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	235 if den == 0 {
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	236 return false
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	237 }
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	238
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	239 denPos := den > 0
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	240
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	241 s02x := p0[0] - p2[0]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	242 s02y := p0[1] - p2[1]
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	243
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	244 sNum := s10xs02y - s10ys02x
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	245 if sNum < 0 == denPos {
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	246 return false
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	247 }
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	248
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	249 tNum := s32xs02y - s32ys02x
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	250 if tNum < 0 == denPos {
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	251 return false
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	252 }
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	253
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	254 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	255 return false
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	256 }
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	257
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	258 // t := tNum / den
98bc023750cf Impelemented line segment / line segment intersection test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2494 diff changeset	259 // 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	260 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	261 }
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
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	263 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	264
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	265 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	266 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	267 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	268
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	269 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	270 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	271 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	272 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	273 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	274 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	275 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	276 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	277 })
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	278 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	279 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	280 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	281 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	282
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	283 // 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	284 // 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	285 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	286
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	287 // 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	288 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	289 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	290 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	291 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	292 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	293 }
10681749371d Implemented the BBox/clipping polygon test. TODO: triangle/clipping polygon test. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2490 diff changeset	294 }
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	295
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	296 // 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	297 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	298 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	299 }
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	300 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	301 }
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	302
cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	303 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	304 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	305 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	306 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	307 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	308 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	309 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	310 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	311 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	312 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	313 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	314 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	315 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	316 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	317 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	318 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	319 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	320 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	321 })
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	322 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	323 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	324 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	325 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	326 // 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	327 // 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	328 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	329
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	330 // 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	331 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	332 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	333 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	334 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	335 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	336 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	337 }
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	338
a727e0426240 More on triangle/clipping polygon intersection. TODO: line segment / line segment intersection. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2492 diff changeset	339 // 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	340 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	341 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	342 }
2488 cb55d7eaaa36 Started with the idea to clip an octree by an bounding polygon. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: diff changeset	343 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	344 }
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	345
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	346 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	347
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	348 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	349 if !rng.isClosed() {
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
2498 843f39b9327e Handle hole more precisely. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2495 diff changeset	353 end := len(rng)/2 - 1
843f39b9327e Handle hole more precisely. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2495 diff changeset	354
843f39b9327e Handle hole more precisely. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2495 diff changeset	355 contains := intersectsWithRaycast(point, rng[:2], rng[end2:end2+2])
2490 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 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	358 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	359 contains = !contains
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	360 }
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
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	363 return contains
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
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	366 // 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	367 // 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	368 // 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	369 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	370
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	371 // 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	372 // 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	373 if start[1] > end[1] {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	374 // Switch the points if otherwise.
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	375 start, end = end, start
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	376 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	377
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	378 // Move the point's y coordinate
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	379 // 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	380 // 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	381 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	382 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	383 point = []float64{point[0], y}
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	384 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	385
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	386 // 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	387 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	388 return false
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	389 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	390
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	391 if start[0] > end[0] {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	392 if point[0] > start[0] {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	393 return false
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	394 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	395 if point[0] < end[0] {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	396 return true
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	397 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	398 } else {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	399 if point[0] > end[0] {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	400 return false
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	401 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	402 if point[0] < start[0] {
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	403 return true
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	404 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	405 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	406
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	407 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	408 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	409
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	410 return raySlope >= diagSlope
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	411 }
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	412
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	413 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	414
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	415 r := bytes.NewReader(data)
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	416
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	417 endian, err := r.ReadByte()
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 var order binary.ByteOrder
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	420
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	421 switch {
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	422 case err != nil:
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	423 return err
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	424 case endian == wkb.NDR:
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	425 order = binary.LittleEndian
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	426 case endian == wkb.XDR:
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	427 order = binary.BigEndian
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	428 default:
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	429 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	430 }
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 var geomType uint32
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	433 err = binary.Read(r, order, &geomType)
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	434
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	435 switch {
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	436 case err != nil:
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	437 return err
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	438 case geomType != wkb.Polygon:
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	439 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	440 }
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	441
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	442 var numRings uint32
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	443 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	444 return err
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	445 }
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	446
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	447 rngs := make([]ring, numRings)
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	448
2498 843f39b9327e Handle hole more precisely. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2495 diff changeset	449 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	450
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	451 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	452 var numVertices uint32
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	453 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	454 return err
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	455 }
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	456
2498 843f39b9327e Handle hole more precisely. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2495 diff changeset	457 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	458
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	459 numVertices *= 2
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	460 vertices := make([]float64, numVertices)
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	461
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	462 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	463 var lat, lon uint64
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	464 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	465 return err
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	466 }
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	467 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	468 return err
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	469 }
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	470 vertices[v] = math.Float64frombits(lat)
c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	471 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	472 }
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	473
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	474 rngs[rng] = vertices
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	475 }
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	476
2490 c9164ff98871 Started with point in polygon check. Sascha L. Teichmann <sascha.teichmann@intevation.de> parents: 2489 diff changeset	477 p.rings = rngs
2489 4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	478
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	479 return nil
4f292ff74d9e Added a WKB reader for clipping polygon. Sascha L. Teichmann <teichmann@intevation.de> parents: 2488 diff changeset	480 }

Mercurial > gemma

annotate pkg/octree/polygon.go @ 2575:59e7a011d347