polygons 0.3.5

Fast points-in-polygon test and distances to polygons.
Documentation 
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
114
115

use crate::tree::Node;

fn box_distance(p: (f64, f64), node: &Node) -> f64 {
    let difx = if p.0 < node.xmin {
        p.0 - node.xmin
    } else if p.0 > node.xmax {
        p.0 - node.xmax
    } else {
        0.0
    };

    let dify = if p.1 < node.ymin {
        p.1 - node.ymin
    } else if p.1 > node.ymax {
        p.1 - node.ymax
    } else {
        0.0
    };

    distance(difx, dify)
}

pub fn get_distance_edge(node: &Node, d: f64, p: (f64, f64)) -> f64 {
    if box_distance(p, node) > d {
        return d;
    }

    let mut d_min = d;

    if !node.children_nodes.is_empty() {
        for child_node in node.children_nodes.iter() {
            let temp = get_distance_edge(child_node, d_min, p);
            d_min = d_min.min(temp);
        }
        return d_min;
    }

    if !node.edges.is_empty() {
        for edge in &node.edges {
            d_min = d_min.min(dsegment(
                p.0, p.1, edge.p1.x, edge.p1.y, edge.p2.x, edge.p2.y,
            ));
        }
        return d_min;
    }

    d_min
}

pub fn get_distance_vertex(node: &Node, i: usize, d: f64, p: (f64, f64)) -> (usize, f64) {
    if box_distance(p, node) + node.hmin > d {
        return (i, d);
    }

    let mut i_min = i;
    let mut d_min = d;

    if !node.children_nodes.is_empty() {
        for child_node in node.children_nodes.iter() {
            let (i_t, d_t) = get_distance_vertex(child_node, i_min, d_min, p);
            if d_t < d_min {
                d_min = d_t;
                i_min = i_t;
            }
        }
        return (i_min, d_min);
    }

    if !node.edges.is_empty() {
        for edge in &node.edges {
            let d_t = distance(edge.p1.x - p.0, edge.p1.y - p.1) + edge.p1.h;
            if d_t < d_min {
                d_min = d_t;
                i_min = edge.p1.index;
            }
        }

        let edge = node.edges.last().unwrap();
        let d_t = distance(edge.p2.x - p.0, edge.p2.y - p.1) + edge.p2.h;
        if d_t < d_min {
            d_min = d_t;
            i_min = edge.p2.index;
        }

        return (i_min, d_min);
    }

    (i_min, d_min)
}

fn distance(x: f64, y: f64) -> f64 {
    (x * x + y * y).sqrt()
}

// this is derived from a C/C++ code
// Copyright (C) 2004-2012 Per-Olof Persson
// which was shared under GPL
fn dsegment(x0: f64, y0: f64, p1x: f64, p1y: f64, p2x: f64, p2y: f64) -> f64 {
    let v = (p2x - p1x, p2y - p1y);
    let w = (x0 - p1x, y0 - p1y);

    let c1 = v.0 * w.0 + v.1 * w.1;

    if c1 <= 0.0 {
        return distance(x0 - p1x, y0 - p1y);
    }

    let c2 = v.0 * v.0 + v.1 * v.1;

    if c1 >= c2 {
        distance(x0 - p2x, y0 - p2y)
    } else {
        distance(x0 - (p1x + c1 / c2 * v.0), y0 - (p1y + c1 / c2 * v.1))
    }
}