1use std::cmp::Ordering;
2use std::fmt;
3
4use geo::{Winding, Contains};
5use geo::winding_order::WindingOrder;
6use geo_types::{Polygon, MultiPolygon, LineString};
7
8use crate::priority_queue::PriorityQueue;
9use crate::vertex_queue::*;
10use crate::util::*;
11
12#[derive(Debug)]
13#[allow(dead_code)]
14pub(crate) enum VertexType{
15 TreeVertex{axis: Ray, left_ray: Ray, right_ray: Ray, parent: usize, time_elapsed: f64,},
16 SplitVertex{anchor: usize, location: Coordinate, split_left: usize, split_right: usize, time_elapsed: f64,},
17 RootVertex{location: Coordinate, time_elapsed: f64,}
18}
19
20impl VertexType{
21 fn init_tree_vertex(lv: Coordinate, cv: Coordinate, rv: Coordinate, orient: bool) -> Self{
22 let r1 = Ray::new(cv, lv);
23 let r2 = Ray::new(cv, rv);
24 let mut r3 = r1.bisector(&r2, cv, orient);
25 r3.angle = r3.angle/(r3.point_by_ratio(1.).dist_ray(&r2));
26 VertexType::TreeVertex { axis: r3, left_ray: r1, right_ray: r2, parent: usize::MAX, time_elapsed: 0. }
27 }
28
29 fn new_tree_vertex(location: Coordinate, left_ray: Ray, right_ray: Ray, orient: bool) -> Self{
30 let mut axis = left_ray.bisector(&right_ray, location, orient);
31 axis.angle = axis.angle/f64::abs(axis.point_by_ratio(1.).dist_ray(&left_ray)-axis.point_by_ratio(0.).dist_ray(&left_ray));
32 let time_elapsed = axis.origin.dist_ray(&left_ray);
33 VertexType::TreeVertex { axis, left_ray, right_ray, parent: usize::MAX, time_elapsed }
34 }
35
36 fn new_split_vertex(anchor: usize, location: Coordinate, split_left: usize, split_right: usize, time_elapsed: f64) -> Self{
37 VertexType::SplitVertex { anchor, location, split_left, split_right, time_elapsed }
38 }
39
40 fn new_root_vertex(location: Coordinate, time_elapsed: f64) -> Self{
41 VertexType::RootVertex { location: location, time_elapsed: time_elapsed }
42 }
43
44 #[allow(dead_code)]
45 fn initialize_from_polygon(input_polygon: &Polygon, orient: bool) -> Vec<Self>{
46 Self::initialize_from_polygon_vector(&vec![input_polygon.clone()], orient)
47 }
48
49 fn initialize_from_polygon_vector(input_polygon_vector: &Vec<Polygon>, orient: bool) -> Vec<Self>{
50 let mut ret = Vec::new();
51 for p in input_polygon_vector{
52 let len = p.exterior().0.len() - 1;
53 for cur in 0..len{
54 let prv = (cur+len-1)%len;
55 let nxt = (cur+1)%len;
56 let new_vertex = VertexType::init_tree_vertex(p.exterior().0[prv].into(), p.exterior().0[cur].into(), p.exterior().0[nxt].into(), orient);
57 ret.push(new_vertex);
58 }
59 for i in 0..p.interiors().len(){
60 let len = p.interiors()[i].0.len()-1;
61 for cur in 0..len{
62 let prv = (cur+len-1)%len;
63 let nxt = (cur+1)%len;
64 let new_node = VertexType::init_tree_vertex(p.interiors()[i].0[prv].into(), p.interiors()[i].0[cur].into(), p.interiors()[i].0[nxt].into(), orient);
65 ret.push(new_node);
66 }
67 }
68 }
69 ret
70 }
71
72 fn unwrap_location(&self) -> Coordinate{
73 match self{
74 VertexType::TreeVertex { axis, .. } => axis.origin.clone(),
75 VertexType::SplitVertex { location, .. } => location.clone(),
76 VertexType::RootVertex { location, .. } => location.clone(),
77 }
78 }
79
80 fn unwrap_time(&self) -> f64{
81 match self{
82 VertexType::TreeVertex { time_elapsed, .. } => *time_elapsed,
83 VertexType::SplitVertex { time_elapsed, .. } => *time_elapsed,
84 VertexType::RootVertex { time_elapsed, .. } => *time_elapsed,
85 }
86 }
87
88 fn unwrap_ray(&self) -> Ray{
89 if let VertexType::TreeVertex { axis, .. } = self{
90 return axis.clone();
91 }
92 panic!("Expected VertexType::TreeVertex");
93 }
94
95 fn unwrap_base_ray(&self) -> (Ray, Ray){
96 if let VertexType::TreeVertex { left_ray, right_ray, .. } = self{
97 return (left_ray.clone(), right_ray.clone());
98 }
99 panic!("Expected VertexType::TreeVertex but {:?}", self);
100 }
101
102 fn set_parent(&mut self, nparent: usize){
103 if let VertexType::TreeVertex { parent, .. } = self{
104 *parent = nparent;
105 }
106 else {panic!("Expected VertexType::TreeVertex but {:?}", self)};
107 }
108}
109
110#[derive(PartialEq)]
111enum Event{
112 VertexEvent{time: f64, merge_from: usize, merge_to: usize},
113 EdgeEvent{time: f64, split_from: usize, split_into: usize, split_to_left: usize, split_to_right: usize},
114}
115
116impl PartialOrd for Event{
117 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
118 let x1 = match self{
119 Event::VertexEvent { time, merge_from, merge_to } => (*time, *merge_from, *merge_to, 0, 0),
120 Event::EdgeEvent { time, split_from, split_into, split_to_left, split_to_right } => (*time, *split_from, *split_into, *split_to_left, *split_to_right,),
121 };
122 let x2 = match other{
123 Event::VertexEvent { time, merge_from, merge_to } => (*time, *merge_from, *merge_to, 0, 0),
124 Event::EdgeEvent { time, split_from, split_into, split_to_left, split_to_right } => (*time, *split_from, *split_into, *split_to_left, *split_to_right,),
125 };
126 Some(x1.partial_cmp(&x2).unwrap())
127 }
128}
129
130impl Event{
131 fn unwrap_time(&self) -> f64{
132 match self{
133 Event::VertexEvent { time, ..} => *time,
134 Event::EdgeEvent { time, ..} => *time,
135 }
136 }
137}
138
139#[derive(PartialEq)]
140enum Timeline{
141 ShrinkEvent{time: f64, location: Coordinate, left_vertex: IndexType, right_vertex: IndexType, left_real: usize, right_real: usize, tie_break: f64,},
142 SplitEvent{time: f64, location: Coordinate, anchor_vertex: IndexType, anchor_real: usize,},
143}
144
145impl fmt::Display for Timeline{
146 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
147 match self{
148 Timeline::ShrinkEvent { left_real, right_real, .. } => write!(f, "Shrink {} and {}", *left_real, *right_real),
149 Timeline::SplitEvent { anchor_real, ..} => write!(f, "Split {}", *anchor_real),
150 }
151 }
152}
153
154impl PartialOrd for Timeline {
155 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
156 let t1 = match self{
157 Timeline::ShrinkEvent { time, .. } => *time,
158 Timeline::SplitEvent { time, ..} => *time,
159 };
160 let t2 = match other{
161 Timeline::ShrinkEvent { time, .. } => *time,
162 Timeline::SplitEvent { time, ..} => *time,
163 };
164 if fneq(t1, t2) {return Some(t1.partial_cmp(&t2).unwrap());}
165 let x1 = match self{
166 Timeline::ShrinkEvent { location, left_real, right_real, tie_break, .. }
167 => (1, tie_break, location, left_real, right_real),
168 Timeline::SplitEvent { location, anchor_real, .. }
169 => (0, &0., location, anchor_real, anchor_real),
170 };
171 let x2 = match other{
172 Timeline::ShrinkEvent { location, left_real, right_real, tie_break, .. }
173 => (1, tie_break, location, left_real, right_real),
174 Timeline::SplitEvent { location, anchor_real, .. }
175 => (0, &0., location, anchor_real, anchor_real),
176 };
177 Some(x1.partial_cmp(&x2).unwrap())
178 }
179}
180
181pub(crate) struct Skeleton{
184 ray_vector: Vec<VertexType>,
185 event_queue: Vec<Event>,
186 initial_vertex_queue: VertexQueue,
187}
188
189impl Skeleton{
190
191 pub(crate) fn apply_vertex_queue(&self, vertex_queue: &VertexQueue, offset_distance: f64) -> MultiPolygon{
192 let mut res = Vec::new();
193 let mut lsv = Vec::new();
194 let mut crdv= Vec::new();
195 let mut cur_vidx = usize::MAX;
196 for (vidx, _, idx) in vertex_queue.iter(){
197 if vidx != cur_vidx{
198 if cur_vidx < usize::MAX {
199 let mut ls = LineString::from(crdv);
200 ls.close();
201 lsv.push(ls);
202 }
203 cur_vidx = vidx;
204 crdv = Vec::new();
205 }
206 let crd = self.ray_vector[idx].unwrap_ray().point_by_ratio(offset_distance-self.ray_vector[idx].unwrap_time());
207 crdv.push(crd);
208 }
209 if cur_vidx < usize::MAX {
210 let mut ls = LineString::from(crdv);
211 ls.close();
212 lsv.push(ls);
213 }
214 for ls in &lsv{
215 if ls.winding_order() == Some(WindingOrder::CounterClockwise){
216 let p1: Polygon = Polygon::new(
217 ls.clone(), vec![],
218 );
219 res.push(p1);
220 }
221 }
222 for ls in &lsv{
223 if ls.winding_order() == Some(WindingOrder::Clockwise){
224 for e in &mut res{
225 if e.contains(ls){
226 e.interiors_push(ls.clone());
227 break;
228 }
229 }
230 }
231 }
232 MultiPolygon::new(res)
233 }
234
235 pub(crate) fn apply_vertex_queue_rounded(&self, vertex_queue: &VertexQueue, offset_distance: f64) -> MultiPolygon{
236 let orient = self.get_orientation();
237 let mut res = Vec::new();
238 let mut lsv = Vec::new();
239 let mut crdv= Vec::new();
240 let mut cur_vidx = usize::MAX;
241 for (vidx, _, idx) in vertex_queue.iter(){
242 if vidx != cur_vidx{
243 if cur_vidx < usize::MAX {
244 let mut ls = LineString::from(crdv);
245 ls.close();
246 lsv.push(ls);
247 }
248 cur_vidx = vidx;
249 crdv = Vec::new();
250 }
251 let time_left = offset_distance-self.ray_vector[idx].unwrap_time();
252 let (lray, rray) = self.ray_vector[idx].unwrap_base_ray();
253 let cray = self.ray_vector[idx].unwrap_ray();
254 if (lray.angle + cray.angle).norm() > (lray.angle - cray.angle).norm(){
255 let crd = cray.point_by_ratio(time_left);
256 crdv.push(crd);
257 }
258 else{
259 let mut left_normal;
260 let mut right_normal;
261 if orient{
262 left_normal = Ray{origin: cray.origin, angle: (-lray.angle.1, lray.angle.0).into()};
263 right_normal = Ray{origin: cray.origin, angle: (rray.angle.1, -rray.angle.0).into()};
264 }
265 else{
266 left_normal = Ray{origin: cray.origin, angle: (lray.angle.1, -lray.angle.0).into()};
267 right_normal = Ray{origin: cray.origin, angle: (-rray.angle.1, rray.angle.0).into()};
268 }
269 left_normal.normalize();
270 right_normal.normalize();
271 loop{
272 let lcrd = left_normal.point_by_ratio(time_left);
273 crdv.push(lcrd);
274 left_normal = left_normal.rotate_by(if orient {0.1} else {-0.1});
275 if orient && left_normal.orientation(&right_normal.point_by_ratio(1.)) == -1 {break;}
276 if !orient && left_normal.orientation(&right_normal.point_by_ratio(1.)) == 1 {break;}
277 }
278 crdv.push(right_normal.point_by_ratio(time_left));
279 }
280 }
281 if cur_vidx < usize::MAX {
282 let mut ls = LineString::from(crdv);
283 ls.close();
284 lsv.push(ls);
285 }
286 for ls in &lsv{
287 if ls.winding_order() == Some(WindingOrder::CounterClockwise){
288 let p1: Polygon = Polygon::new(
289 ls.clone(), vec![],
290 );
291 res.push(p1);
292 }
293 }
294 for ls in &lsv{
295 if ls.winding_order() == Some(WindingOrder::Clockwise){
296 for e in &mut res{
297 if e.contains(ls){
298 e.interiors_push(ls.clone());
299 break;
300 }
301 }
302 }
303 }
304 MultiPolygon::new(res)
305 }
306
307 pub(crate) fn get_vertex_queue(&self, time_elapsed: f64) -> VertexQueue{
308 let mut ret = self.initial_vertex_queue.clone();
309 for e in &self.event_queue{
310 if e.unwrap_time() <= time_elapsed{
311 Self::apply_event(&mut ret, e);
312 ret.cleanup();
313 }
314 else {break;}
315 }
316 ret
317 }
318
319 fn get_orientation(&self) -> bool{
320 let iz_ray = self.ray_vector[0].unwrap_ray();
321 let iz_left = self.ray_vector[0].unwrap_base_ray().0;
322 iz_left.orientation(&iz_ray.point_by_ratio(1.)) == 1
323 }
324
325 fn find_split_vertex(cv: IndexType, vertex_queue: &VertexQueue, vertex_vector: &Vec<VertexType>, is_init: bool, orient: bool) -> Vec<(f64, Coordinate, IndexType, usize)>{
326 let mut ret = Vec::new();
327 let cv_real = vertex_queue.get_real_index(cv);
328 let left_ray = vertex_vector[cv_real].unwrap_base_ray().0;
329 let right_ray = vertex_vector[cv_real].unwrap_base_ray().1;
330 if orient && fleq(left_ray.angle.outer_product(&right_ray.angle), 0.) {return ret;} if !orient && fgeq(left_ray.angle.outer_product(&right_ray.angle), 0.) {return ret;}
332
333 for (_, sv, sv_real) in vertex_queue.iter(){
334 let srv = vertex_queue.rv(sv);
335 let srv_real = vertex_queue.get_real_index(srv);
336 if sv == cv || sv == vertex_queue.rv(cv) || srv == cv || srv == vertex_queue.lv(cv) {continue;}
337 let base_ray = vertex_vector[sv_real].unwrap_base_ray().1;
338 let left_intersection = if left_ray.is_parallel(&base_ray) {Default::default()} else {left_ray.intersect(&base_ray)};
339 let right_intersection = if right_ray.is_parallel(&base_ray) {Default::default()} else {right_ray.intersect(&base_ray)};
340 let real_intersection = if left_ray.is_parallel(&base_ray) {
341 let ri_ray = right_ray.bisector(&base_ray.reverse(), right_intersection, !orient);
342 if !ri_ray.is_intersect(&vertex_vector[cv_real].unwrap_ray()) {continue;}
343 ri_ray.intersect(&vertex_vector[cv_real].unwrap_ray())
344 } else{
345 let li_ray = left_ray.bisector(&base_ray, left_intersection, orient);
346 if !li_ray.is_intersect(&vertex_vector[cv_real].unwrap_ray()) {continue;}
347 li_ray.intersect(&vertex_vector[cv_real].unwrap_ray())
348 };
349 if is_init {
350 if orient && base_ray.orientation(&real_intersection) < 0 {continue;}
351 if !orient && base_ray.orientation(&real_intersection) > 0 {continue;}
352 }
353 else{
354 if orient{
355 if vertex_vector[sv_real].unwrap_ray().orientation(&real_intersection) >= 0 {continue;}
356 if base_ray.orientation(&real_intersection) < 0 {continue;}
357 if vertex_vector[srv_real].unwrap_ray().orientation(&real_intersection) < 0 {continue;}
358 }
359 else{
360 if vertex_vector[sv_real].unwrap_ray().orientation(&real_intersection) <= 0 {continue;}
361 if base_ray.orientation(&real_intersection) > 0 {continue;}
362 if vertex_vector[srv_real].unwrap_ray().orientation(&real_intersection) > 0 {continue;}
363 }
364 }
365 let dist = real_intersection.dist_ray(&right_ray);
366 ret.push((dist, real_intersection, sv, sv_real));
367 }
368 ret.sort_by(|a, b| a.partial_cmp(b).unwrap());
369 if !is_init && ret.len() != 0 {ret = vec![ret[0]];}
370 ret
371 }
372
373 fn make_split_event(cv: IndexType, vertex_queue: &VertexQueue, event_pq: &mut PriorityQueue<Timeline>, vertex_vector: &Vec<VertexType>, orient: bool){
374 let resv = Self::find_split_vertex(cv, vertex_queue, vertex_vector, true, orient);
375 let cv_real = vertex_queue.get_real_index(cv);
376 for (time, location, _, _) in resv{
377 event_pq.insert(Timeline::SplitEvent { time: time, location: location, anchor_vertex: cv, anchor_real: cv_real, });
378 }
379 }
380
381 fn make_shrink_event(cv: IndexType, vertex_queue: &VertexQueue, event_pq: &mut PriorityQueue<Timeline>, vertex_vector: &Vec<VertexType>, is_init: bool){
382 let mut lv = cv;
383 if vertex_queue.rv(cv) == vertex_queue.lv(cv) {return;}
384 for _ in 0..2{
385 let rv = vertex_queue.rv(lv);
386 let lv_real = vertex_queue.get_real_index(lv);
387 let rv_real = vertex_queue.get_real_index(rv);
388 let lv_ray = vertex_vector[lv_real].unwrap_ray();
389 let rv_ray = vertex_vector[rv_real].unwrap_ray();
390 if lv_ray.is_intersect(&rv_ray){
391 let cp = lv_ray.intersect(&rv_ray);
392 let dist = cp.dist_ray(&vertex_vector[lv_real].unwrap_base_ray().0);
393 let tie_break = lv_ray.origin.dist_coord(&rv_ray.origin);
394 event_pq.insert(Timeline::ShrinkEvent { time: dist, location: cp, left_vertex: lv, right_vertex: rv, left_real: lv_real, right_real: rv_real, tie_break: tie_break });
395 }
396 if is_init {break;}
397 lv = vertex_queue.lv(cv);
398 }
399 }
400
401 fn apply_event(vertex_queue: &mut VertexQueue, event: &Event) -> (Option<IndexType>, Option<IndexType>){
402 if let Event::VertexEvent { merge_from, merge_to, .. } = event{
403 let merge_from = IndexType::PointerIndex(*merge_from);
404 let merge_to = IndexType::RealIndex(*merge_to);
405 let cv = vertex_queue.remove_and_set(merge_from, merge_to);
406 if vertex_queue.lv(cv) == vertex_queue.rv(cv){
407 let lv = vertex_queue.lv(cv);
408 vertex_queue.content[lv.get_index()].done = true;
409 vertex_queue.content[cv.get_index()].done = true;
410 return (Some(vertex_queue.content[vertex_queue.lv(cv).get_index()].index), None);
411 }
412 return (Some(cv), None);
413 }
414 if let Event::EdgeEvent{ split_from, split_into, split_to_left, split_to_right, ..} = event{
415 let split_from = IndexType::PointerIndex(*split_from);
416 let split_into = IndexType::PointerIndex(*split_into);
417 let split_to_left = IndexType::RealIndex(*split_to_left);
418 let split_to_right = IndexType::RealIndex(*split_to_right);
419 let ret = vertex_queue.split_and_set(split_from, split_into, split_to_left, split_to_right);
420 vertex_queue.cleanup();
421 return (Some(ret.0), Some(ret.1));
422 }
423
424 (None, None)
425 }
426
427 pub(crate) fn skeleton_of_polygon(input_polygon: &Polygon, orient: bool) -> Self{
428 Self::skeleton_of_polygon_vector(&vec![input_polygon.clone()], orient)
429 }
430
431 pub(crate) fn skeleton_of_polygon_vector(input_polygon_vector: &Vec<Polygon>, orient: bool) -> Self{
432 let mut vertex_vector = VertexType::initialize_from_polygon_vector(input_polygon_vector, orient);
433 let mut event_pq = PriorityQueue::new();
434 let mut event_queue = Vec::new();
435 let mut vertex_queue = VertexQueue::new();
436 vertex_queue.initialize_from_polygon_vector(input_polygon_vector);
437 let initial_vertex_queue = vertex_queue.clone();
438 for (_, cv, _) in vertex_queue.iter(){
440 Self::make_shrink_event(cv, &vertex_queue, &mut event_pq, &vertex_vector, true);
441 Self::make_split_event(cv, &vertex_queue, &mut event_pq, &vertex_vector, orient);
442 }
443
444 while !event_pq.is_empty() {
445 let x = event_pq.pop().unwrap();
446 if let Timeline::ShrinkEvent { time, location, left_vertex, right_vertex, left_real, right_real, .. } = x{
447 if vertex_queue.content[left_vertex.get_index()].done || vertex_queue.content[right_vertex.get_index()].done || vertex_queue.get_real_index(left_vertex) != left_real || vertex_queue.get_real_index(right_vertex) != right_real {
448 continue;
449 }
450 let new_index = vertex_vector.len();
451 let left_ray = vertex_vector[left_real].unwrap_base_ray().0;
452 let right_ray = vertex_vector[right_real].unwrap_base_ray().1;
453 vertex_vector[left_real].set_parent(new_index);
454 vertex_vector[right_real].set_parent(new_index);
455 let new_event = Event::VertexEvent { time: time, merge_from: left_vertex.get_index(), merge_to: new_index };
456 let new_vertex = VertexType::new_tree_vertex(location, left_ray, right_ray, orient);
457 vertex_vector.push(new_vertex);
458 match Self::apply_event(&mut vertex_queue, &new_event){
459 (Some(IndexType::RealIndex(rv)), None) => {
460 vertex_vector[rv].set_parent(new_index);
461 vertex_vector[new_index] = VertexType::new_root_vertex(vertex_vector[new_index].unwrap_location(), vertex_vector[new_index].unwrap_time());
462 },
463 (Some(cv), None) => {
464 Self::make_shrink_event(cv, &vertex_queue, &mut event_pq, &vertex_vector, false);
465 },
466 _ => panic!("Expected Vertex Event"),
467 }
468 event_queue.push(new_event);
469 }
470 else if let Timeline::SplitEvent { time, location, anchor_vertex, anchor_real } = x{
471 if vertex_queue.content[anchor_vertex.get_index()].done || vertex_queue.get_real_index(anchor_vertex) != anchor_real {
472 continue;
473 }
474 vertex_queue.cleanup();
475 let rv = Self::find_split_vertex(anchor_vertex, &vertex_queue, &vertex_vector, false, orient);
476 if rv.len() == 1 && feq(rv[0].0, time) && rv[0].1.eq(&location) {
477 let new_index1 = vertex_vector.len();
478 let new_index2 = new_index1 + 1;
479 let new_split_vertex = VertexType::new_split_vertex(anchor_real, location, new_index1, new_index2, vertex_vector[anchor_real].unwrap_time());
480 let new_tree_vertex1 = VertexType::new_tree_vertex(location, vertex_vector[anchor_real].unwrap_base_ray().0, vertex_vector[rv[0].3].unwrap_base_ray().1, orient);
481 let new_tree_vertex2 = VertexType::new_tree_vertex(location, vertex_vector[rv[0].3].unwrap_base_ray().1.reverse(), vertex_vector[anchor_real].unwrap_base_ray().1, orient);
482 vertex_vector.push(new_tree_vertex1);
483 vertex_vector.push(new_tree_vertex2);
484 vertex_vector.push(new_split_vertex);
485 let new_event = Event::EdgeEvent { time, split_from: anchor_vertex.get_index(), split_into: rv[0].2.get_index(), split_to_left: new_index1, split_to_right: new_index2 };
486 match Self::apply_event(&mut vertex_queue, &new_event){
487 (Some(cv1), Some(cv2)) => {
488 vertex_vector[anchor_real].set_parent(new_index2+1);
489 Self::make_shrink_event(cv1, &vertex_queue, &mut event_pq, &vertex_vector, false);
490 Self::make_shrink_event(cv2, &vertex_queue, &mut event_pq, &vertex_vector, false);
491 },
492 _ => panic!("Expected Edge Event"),
493 }
494 event_queue.push(new_event);
495 }
496 }
497 vertex_queue.cleanup();
498 }
499 Self { ray_vector: vertex_vector, event_queue: event_queue, initial_vertex_queue: initial_vertex_queue }
500 }
501
502
503
504 pub(crate) fn to_linestring(&self) -> Vec<LineString>{
505 fn dfs_helper(cur: usize, visit: &mut Vec<bool>, ret: &mut Vec<LineString>, ray_vector: &Vec<VertexType>){
506 if visit[cur] {return;}
507 visit[cur] = true;
508 match ray_vector[cur]{
509 VertexType::RootVertex { .. } => {return;},
510 VertexType::TreeVertex { parent, .. } => {
511 if parent == usize::MAX{
512 let ls = LineString(vec![ray_vector[cur].unwrap_location().into(), ray_vector[cur].unwrap_ray().point_by_ratio(5.).into()]);
513 ret.push(ls);
514 return;
515 }
516 let ls = LineString(vec![ray_vector[cur].unwrap_location().into(), ray_vector[parent].unwrap_location().into()]);
517 ret.push(ls);
518 dfs_helper(parent, visit, ret, ray_vector);
519 },
520 VertexType::SplitVertex { split_left, split_right, .. } => {
521 dfs_helper(split_left, visit, ret, ray_vector);
522 dfs_helper(split_right, visit, ret, ray_vector);
523 }
524 }
525 }
526 let mut visit = vec![false;self.ray_vector.len()];
527 let mut ret = Vec::new();
528 for (_, _, e) in self.initial_vertex_queue.iter(){
529 dfs_helper(e, &mut visit, &mut ret, &self.ray_vector);
530 }
531 ret
532 }
533}