/
qtype.go
73 lines (66 loc) · 1.46 KB
/
qtype.go
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
package quadedge
import (
"fmt"
"github.com/go-spatial/geom"
)
// QType describes the classification of a point to a line
type QType uint
const (
// LEFT indicates that the point is left of the line
LEFT = QType(iota)
// RIGHT indicates that the point is right of the line
RIGHT
// BEYOND indicates that the point is beyond the line
BEYOND
// BEHIND indicates that the point is behind the line
BEHIND
// BETWEEN indicates that the point is between the endpoints of the line
BETWEEN
// ORIGIN indicates that the point is at the origin of the line
ORIGIN
// DESTINATION indicates that the point is at the destination of the line
DESTINATION
)
func (q QType) String() string {
switch q {
case LEFT:
return "LEFT"
case RIGHT:
return "RIGHT"
case BEYOND:
return "BEYOND"
case BEHIND:
return "BEHIND"
case BETWEEN:
return "BETWEEN"
case ORIGIN:
return "ORIGIN"
case DESTINATION:
return "DESTINATION"
default:
return fmt.Sprintf("UNKNOWN(%v)", int(q))
}
}
// Classify returns where b is in realation to a and c.
func Classify(a, b, c geom.Point) QType {
aa := c.Subtract(b)
bb := a.Subtract(b)
sa := aa.CrossProduct(bb)
ab := aa.Multiply(bb)
switch {
case sa > 0.0:
return LEFT
case sa < 0.0:
return RIGHT
case ab[0] < 0.0 || ab[1] < 0.0:
return BEHIND
case aa.Magnitude() < bb.Magnitude():
return BEYOND
case cmp.GeomPointEqual(a, b):
return ORIGIN
case cmp.GeomPointEqual(a, c):
return DESTINATION
default:
return BETWEEN
}
}