geov/visvalingam.go at master · rapour/geov · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package geov

import (
	"math"

	geo "github.com/kellydunn/golang-geo"
)

type augmentedPoint struct {
	area     float64
	point    *geo.Point
	next     *augmentedPoint
	previous *augmentedPoint
}

func (ap *augmentedPoint) computeArea() {

	if ap == nil || ap.previous == nil || ap.next == nil {
		return
	}

	if ap.point == nil || ap.next.point == nil || ap.previous.point == nil {
		return
	}

	ap.area = math.Abs(
		ap.previous.point.Lat()*(ap.point.Lng()-ap.next.point.Lng()) +
			ap.point.Lat()*(ap.next.point.Lng()-ap.previous.point.Lng()) +
			ap.next.point.Lat()*(ap.previous.point.Lng()-ap.point.Lng()))

}

func (ap *augmentedPoint) remove() {

	if ap.previous == nil || ap.next == nil {
		return
	}

	ap.next.previous = ap.previous
	ap.previous.next = ap.next

}

func (ap augmentedPoint) Value() float64 {
	return ap.area
}

func (ap *augmentedPoint) addNext(p *geo.Point) *augmentedPoint {

	if ap.point == nil {
		ap.point = p
		return ap
	}

	if ap.next == nil {
		ap.next = &augmentedPoint{point: p, previous: ap}
		return ap.next
	}

	return ap.next.addNext(p)
}

func Visvalingam(a Arc, ratio float64) Arc {

	origin := augmentedPoint{}

	heap := NewHeap[float64](nil)

	for _, p := range a.Points {
		tmp := p
		heap.Add(origin.addNext(&tmp))
	}

	it := &origin
	for {
		if it == nil {
			break
		}
		it.computeArea()
		it = it.next
	}

	for {

		if l := heap.GetSize() + 2; l <= 2 || float64(l)/float64(len(a.Points)) <= ratio {
			break
		}

		m := heap.ExtractMin().(*augmentedPoint)
		m.remove()

		if m.next != nil {
			m.next.computeArea()
		}

		if m.previous != nil {
			m.previous.computeArea()
		}

	}

	res := Arc{}
	chain := &origin
	for {

		if chain == nil {
			return res
		}

		res.AddPoint(*chain.point)
		chain = chain.next
	}
}