1use bbox::{BoundingBox, HasBoundingBox};
2use fnv::FnvHashSet;
3use grid::{CellCoords, Grid, GridShape};
4use line_path::LinePath;
5use segments::{LineSegment, Segment};
6use N;
7
8#[derive(Copy, Clone, PartialEq, Eq, Hash)]
9pub struct PathIdx(u32);
10
11impl PathIdx {
12 pub fn as_idx(self) -> usize {
13 self.0 as usize
14 }
15}
16
17#[derive(Copy, Clone, PartialEq, Eq, Hash)]
18pub struct SegmentIdx(u32);
19
20impl SegmentIdx {
21 pub fn as_idx(self) -> usize {
22 self.0 as usize
23 }
24}
25
26#[derive(Copy, Clone, PartialEq, Eq, Hash)]
27pub struct PathSegmentIdx {
28 pub path_idx: PathIdx,
29 pub segment_idx: SegmentIdx,
30}
31
32pub struct SegmentGrid {
33 grid: Grid<PathSegmentIdx>,
34 next_path_idx: usize,
35}
36
37impl GridShape for LineSegment {
38 fn covered_cell_coords(&self, cell_width: N) -> Vec<CellCoords> {
39 let length = self.length();
40 let step = cell_width / 2.0;
41
42 if length <= step {
43 bbox_unique_cell_coords(self.bounding_box(), cell_width)
44 .iter()
45 .filter_map(|maybe| maybe.clone())
46 .collect()
47 } else {
48 let start = self.start();
49 let direction = self.direction();
50
51 let mut start_along = 0.0;
52 let mut end_along = step;
53
54 let start_4_coords = bbox_unique_cell_coords(
55 LineSegment::new(
56 start + direction * start_along,
57 start + direction * end_along,
58 ).bounding_box(),
59 cell_width,
60 );
61 let mut coords: Vec<_> = start_4_coords
62 .iter()
63 .filter_map(|maybe| maybe.clone())
64 .collect();
65
66 loop {
67 start_along += step;
68 end_along = (end_along + step).min(length);
69
70 let mut new_4_coords = bbox_unique_cell_coords(
71 LineSegment::new(
72 start + direction * start_along,
73 start + direction * end_along,
74 ).bounding_box(),
75 cell_width,
76 );
77
78 {
79 let only_if_new = |new_coord| {
80 if coords[coords.len().saturating_sub(4)..coords.len()].contains(&new_coord)
81 {
82 None
83 } else {
84 Some(new_coord)
85 }
86 };
87
88 new_4_coords[0] = new_4_coords[0].and_then(only_if_new);
89 new_4_coords[1] = new_4_coords[1].and_then(only_if_new);
90 new_4_coords[2] = new_4_coords[2].and_then(only_if_new);
91 new_4_coords[3] = new_4_coords[3].and_then(only_if_new);
92 }
93
94 coords.extend(new_4_coords.iter().filter_map(|maybe| maybe.clone()));
95
96 if start_along + step >= length {
97 break;
98 }
99 }
100
101 coords
102 }
103 }
104}
105
106fn bbox_unique_cell_coords(bbox: BoundingBox, cell_width: N) -> [Option<CellCoords>; 4] {
107 let bottom_left = CellCoords(
108 (bbox.min.x / cell_width).floor() as i32,
109 (bbox.min.y / cell_width).floor() as i32,
110 );
111 let top_left = CellCoords(
112 (bbox.min.x / cell_width).floor() as i32,
113 (bbox.max.y / cell_width).floor() as i32,
114 );
115 let top_right = CellCoords(
116 (bbox.max.x / cell_width).floor() as i32,
117 (bbox.max.y / cell_width).floor() as i32,
118 );
119 let bottom_right = CellCoords(
120 (bbox.max.x / cell_width).floor() as i32,
121 (bbox.min.y / cell_width).floor() as i32,
122 );
123
124 let mut result = [Some(bottom_left), None, None, None];
125
126 if top_left != bottom_left {
129 result[1] = Some(top_left);
130 }
131
132 if top_right != bottom_left && top_right != top_left {
133 result[2] = Some(top_right);
134 }
135
136 if bottom_right != bottom_left && bottom_right != top_left && bottom_right != top_right {
137 result[3] = Some(bottom_right);
138 }
139
140 result
141}
142
143#[test]
144fn intersection_grid() {
145 use P2;
146 assert_eq!(
147 LineSegment::new(P2::new(0.0, 0.0), P2::new(3.0, 2.0)).covered_cell_coords(0.25),
148 vec![
149 CellCoords(-1, -1),
150 CellCoords(-1, 0),
151 CellCoords(0, 0),
152 CellCoords(0, -1),
153 CellCoords(1, 0),
154 CellCoords(1, 1),
155 CellCoords(2, 1),
156 CellCoords(2, 2),
157 CellCoords(3, 2),
158 CellCoords(3, 1),
159 CellCoords(4, 2),
160 CellCoords(4, 3),
161 CellCoords(5, 3),
162 CellCoords(5, 4),
163 CellCoords(6, 4),
164 CellCoords(6, 3),
165 CellCoords(7, 4),
166 CellCoords(7, 5),
167 CellCoords(8, 5),
168 CellCoords(8, 6),
169 CellCoords(9, 6),
170 CellCoords(9, 5),
171 CellCoords(10, 6),
172 CellCoords(10, 7),
173 CellCoords(11, 7),
174 CellCoords(11, 8),
175 CellCoords(12, 8),
176 CellCoords(12, 7),
177 ]
178 );
179}
180
181impl SegmentGrid {
182 pub fn new(cell_width: N) -> SegmentGrid {
183 SegmentGrid {
184 grid: Grid::new(cell_width),
185 next_path_idx: 0,
186 }
187 }
188
189 pub fn insert(
190 &mut self,
191 path: &LinePath,
192 ) -> (PathIdx, FnvHashSet<(SegmentIdx, PathSegmentIdx)>) {
193 let path_idx = PathIdx(self.next_path_idx as u32);
194 self.next_path_idx += 1;
195
196 let mut interactions = FnvHashSet::default();
197
198 for (segment_idx, segment) in path.segments().enumerate() {
199 let path_segment_idx = PathSegmentIdx {
200 path_idx: path_idx,
201 segment_idx: SegmentIdx(segment_idx as u32),
202 };
203
204 self.grid
205 .insert_visiting(path_segment_idx, &segment, |existing_cell_content| {
206 for other_path_segment_idx in existing_cell_content.iter() {
207 if path_segment_idx.path_idx != other_path_segment_idx.path_idx {
209 interactions
210 .insert((SegmentIdx(segment_idx as u32), *other_path_segment_idx));
211 }
212 }
213 });
214 }
215
216 (path_idx, interactions)
217 }
218}