1use std::cmp::Ordering;
2use std::fmt;
3
4use geo::winding_order::WindingOrder;
5use geo::{Contains, Winding};
6use geo_types::{LineString, MultiPolygon, Polygon};
7
8use crate::priority_queue::PriorityQueue;
9use crate::util::*;
10use crate::vertex_queue::*;
11
12#[derive(Debug)]
13#[allow(dead_code)]
14pub(crate) enum VertexType {
15 Tree {
16 axis: Ray,
17 left_ray: Ray,
18 right_ray: Ray,
19 parent: usize,
20 time_elapsed: f64,
21 },
22 Split {
23 anchor: usize,
24 location: Coordinate,
25 split_left: usize,
26 split_right: usize,
27 time_elapsed: f64,
28 },
29 Root {
30 location: Coordinate,
31 time_elapsed: f64,
32 },
33}
34
35impl VertexType {
36 fn init_tree_vertex(lv: Coordinate, cv: Coordinate, rv: Coordinate, orient: bool) -> Self {
37 let r1 = Ray::new(cv, lv);
38 let r2 = Ray::new(cv, rv);
39 let mut r3 = r1.bisector(&r2, cv, orient);
40 r3.angle = r3.angle / (r3.point_by_ratio(1.).dist_ray(&r2));
41 VertexType::Tree {
42 axis: r3,
43 left_ray: r1,
44 right_ray: r2,
45 parent: usize::MAX,
46 time_elapsed: 0.,
47 }
48 }
49
50 fn new_tree_vertex(location: Coordinate, left_ray: Ray, right_ray: Ray, orient: bool) -> Self {
51 let mut axis = left_ray.bisector(&right_ray, location, orient);
52 axis.angle = axis.angle
53 / f64::abs(
54 axis.point_by_ratio(1.).dist_ray(&left_ray)
55 - axis.point_by_ratio(0.).dist_ray(&left_ray),
56 );
57 let time_elapsed = axis.origin.dist_ray(&left_ray);
58 VertexType::Tree {
59 axis,
60 left_ray,
61 right_ray,
62 parent: usize::MAX,
63 time_elapsed,
64 }
65 }
66
67 fn new_split_vertex(
68 anchor: usize,
69 location: Coordinate,
70 split_left: usize,
71 split_right: usize,
72 time_elapsed: f64,
73 ) -> Self {
74 VertexType::Split {
75 anchor,
76 location,
77 split_left,
78 split_right,
79 time_elapsed,
80 }
81 }
82
83 fn new_root_vertex(location: Coordinate, time_elapsed: f64) -> Self {
84 VertexType::Root {
85 location,
86 time_elapsed,
87 }
88 }
89
90 #[allow(dead_code)]
91 fn initialize_from_polygon(input_polygon: &Polygon, orient: bool) -> Vec<Self> {
92 Self::initialize_from_polygon_vector(&vec![input_polygon.clone()], orient)
93 }
94
95 fn initialize_from_polygon_vector(
96 input_polygon_vector: &Vec<Polygon>,
97 orient: bool,
98 ) -> Vec<Self> {
99 let mut ret = Vec::new();
100 for p in input_polygon_vector {
101 let len = p.exterior().0.len() - 1;
102 for cur in 0..len {
103 let prv = (cur + len - 1) % len;
104 let nxt = (cur + 1) % len;
105 let new_vertex = VertexType::init_tree_vertex(
106 p.exterior().0[prv].into(),
107 p.exterior().0[cur].into(),
108 p.exterior().0[nxt].into(),
109 orient,
110 );
111 ret.push(new_vertex);
112 }
113 for i in 0..p.interiors().len() {
114 let len = p.interiors()[i].0.len() - 1;
115 for cur in 0..len {
116 let prv = (cur + len - 1) % len;
117 let nxt = (cur + 1) % len;
118 let new_node = VertexType::init_tree_vertex(
119 p.interiors()[i].0[prv].into(),
120 p.interiors()[i].0[cur].into(),
121 p.interiors()[i].0[nxt].into(),
122 orient,
123 );
124 ret.push(new_node);
125 }
126 }
127 }
128 ret
129 }
130
131 fn unwrap_location(&self) -> Coordinate {
132 match self {
133 VertexType::Tree { axis, .. } => axis.origin,
134 VertexType::Split { location, .. } => *location,
135 VertexType::Root { location, .. } => *location,
136 }
137 }
138
139 fn unwrap_time(&self) -> f64 {
140 match self {
141 VertexType::Tree { time_elapsed, .. } => *time_elapsed,
142 VertexType::Split { time_elapsed, .. } => *time_elapsed,
143 VertexType::Root { time_elapsed, .. } => *time_elapsed,
144 }
145 }
146
147 fn unwrap_ray(&self) -> Ray {
148 if let VertexType::Tree { axis, .. } = self {
149 return *axis;
150 }
151 panic!("Expected VertexType::TreeVertex");
152 }
153
154 fn unwrap_base_ray(&self) -> (Ray, Ray) {
155 if let VertexType::Tree {
156 left_ray,
157 right_ray,
158 ..
159 } = self
160 {
161 return (*left_ray, *right_ray);
162 }
163 panic!("Expected VertexType::TreeVertex but {:?}", self);
164 }
165
166 fn set_parent(&mut self, nparent: usize) {
167 if let VertexType::Tree { parent, .. } = self {
168 *parent = nparent;
169 } else {
170 panic!("Expected VertexType::TreeVertex but {:?}", self)
171 };
172 }
173}
174
175#[derive(PartialEq)]
176enum Event {
177 VertexEvent {
178 time: f64,
179 merge_from: usize,
180 merge_to: usize,
181 },
182 EdgeEvent {
183 time: f64,
184 split_from: usize,
185 split_into: usize,
186 split_to_left: usize,
187 split_to_right: usize,
188 },
189}
190
191impl PartialOrd for Event {
192 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
193 let x1 = match self {
194 Event::VertexEvent {
195 time,
196 merge_from,
197 merge_to,
198 } => (*time, *merge_from, *merge_to, 0, 0),
199 Event::EdgeEvent {
200 time,
201 split_from,
202 split_into,
203 split_to_left,
204 split_to_right,
205 } => (
206 *time,
207 *split_from,
208 *split_into,
209 *split_to_left,
210 *split_to_right,
211 ),
212 };
213 let x2 = match other {
214 Event::VertexEvent {
215 time,
216 merge_from,
217 merge_to,
218 } => (*time, *merge_from, *merge_to, 0, 0),
219 Event::EdgeEvent {
220 time,
221 split_from,
222 split_into,
223 split_to_left,
224 split_to_right,
225 } => (
226 *time,
227 *split_from,
228 *split_into,
229 *split_to_left,
230 *split_to_right,
231 ),
232 };
233 Some(x1.partial_cmp(&x2).unwrap())
234 }
235}
236
237impl Event {
238 fn unwrap_time(&self) -> f64 {
239 match self {
240 Event::VertexEvent { time, .. } => *time,
241 Event::EdgeEvent { time, .. } => *time,
242 }
243 }
244}
245
246#[derive(PartialEq)]
247enum Timeline {
248 ShrinkEvent {
249 time: f64,
250 location: Coordinate,
251 left_vertex: IndexType,
252 right_vertex: IndexType,
253 left_real: usize,
254 right_real: usize,
255 tie_break: f64,
256 },
257 SplitEvent {
258 time: f64,
259 location: Coordinate,
260 anchor_vertex: IndexType,
261 anchor_real: usize,
262 },
263}
264
265impl fmt::Display for Timeline {
266 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
267 match self {
268 Timeline::ShrinkEvent {
269 left_real,
270 right_real,
271 ..
272 } => write!(f, "Shrink {} and {}", *left_real, *right_real),
273 Timeline::SplitEvent { anchor_real, .. } => write!(f, "Split {}", *anchor_real),
274 }
275 }
276}
277
278impl PartialOrd for Timeline {
279 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
280 let t1 = match self {
281 Timeline::ShrinkEvent { time, .. } => *time,
282 Timeline::SplitEvent { time, .. } => *time,
283 };
284 let t2 = match other {
285 Timeline::ShrinkEvent { time, .. } => *time,
286 Timeline::SplitEvent { time, .. } => *time,
287 };
288 if fneq(t1, t2) {
289 return Some(t1.partial_cmp(&t2).unwrap());
290 }
291 let x1 = match self {
292 Timeline::ShrinkEvent {
293 location,
294 left_real,
295 right_real,
296 tie_break,
297 ..
298 } => (1, tie_break, location, left_real, right_real),
299 Timeline::SplitEvent {
300 location,
301 anchor_real,
302 ..
303 } => (0, &0., location, anchor_real, anchor_real),
304 };
305 let x2 = match other {
306 Timeline::ShrinkEvent {
307 location,
308 left_real,
309 right_real,
310 tie_break,
311 ..
312 } => (1, tie_break, location, left_real, right_real),
313 Timeline::SplitEvent {
314 location,
315 anchor_real,
316 ..
317 } => (0, &0., location, anchor_real, anchor_real),
318 };
319 Some(x1.partial_cmp(&x2).unwrap())
320 }
321}
322
323pub(crate) struct Skeleton {
326 ray_vector: Vec<VertexType>,
327 event_queue: Vec<Event>,
328 initial_vertex_queue: VertexQueue,
329}
330
331impl Skeleton {
332 pub(crate) fn apply_vertex_queue(
333 &self,
334 vertex_queue: &VertexQueue,
335 offset_distance: f64,
336 ) -> MultiPolygon {
337 let mut res = Vec::new();
338 let mut lsv = Vec::new();
339 let mut crdv = Vec::new();
340 let mut cur_vidx = usize::MAX;
341 for (vidx, _, idx) in vertex_queue.iter() {
342 if vidx != cur_vidx {
343 if cur_vidx < usize::MAX {
344 let mut ls = LineString::from(crdv);
345 ls.close();
346 lsv.push(ls);
347 }
348 cur_vidx = vidx;
349 crdv = Vec::new();
350 }
351 let crd = self.ray_vector[idx]
352 .unwrap_ray()
353 .point_by_ratio(offset_distance - self.ray_vector[idx].unwrap_time());
354 crdv.push(crd);
355 }
356 if cur_vidx < usize::MAX {
357 let mut ls = LineString::from(crdv);
358 ls.close();
359 lsv.push(ls);
360 }
361 for ls in &lsv {
362 if ls.winding_order() == Some(WindingOrder::CounterClockwise) {
363 let p1: Polygon = Polygon::new(ls.clone(), vec![]);
364 res.push(p1);
365 }
366 }
367 for ls in &lsv {
368 if ls.winding_order() == Some(WindingOrder::Clockwise) {
369 for e in &mut res {
370 if e.contains(ls) {
371 e.interiors_push(ls.clone());
372 break;
373 }
374 }
375 }
376 }
377 MultiPolygon::new(res)
378 }
379
380 pub(crate) fn apply_vertex_queue_rounded(
381 &self,
382 vertex_queue: &VertexQueue,
383 offset_distance: f64,
384 ) -> MultiPolygon {
385 let orient = self.get_orientation();
386 let mut res = Vec::new();
387 let mut lsv = Vec::new();
388 let mut crdv = Vec::new();
389 let mut cur_vidx = usize::MAX;
390 for (vidx, _, idx) in vertex_queue.iter() {
391 if vidx != cur_vidx {
392 if cur_vidx < usize::MAX {
393 let mut ls = LineString::from(crdv);
394 ls.close();
395 lsv.push(ls);
396 }
397 cur_vidx = vidx;
398 crdv = Vec::new();
399 }
400 let time_left = offset_distance - self.ray_vector[idx].unwrap_time();
401 let (lray, rray) = self.ray_vector[idx].unwrap_base_ray();
402 let cray = self.ray_vector[idx].unwrap_ray();
403 if (lray.angle + cray.angle).norm() > (lray.angle - cray.angle).norm() {
404 let crd = cray.point_by_ratio(time_left);
405 crdv.push(crd);
406 } else {
407 let mut left_normal;
408 let mut right_normal;
409 if orient {
410 left_normal = Ray {
411 origin: cray.origin,
412 angle: (-lray.angle.1, lray.angle.0).into(),
413 };
414 right_normal = Ray {
415 origin: cray.origin,
416 angle: (rray.angle.1, -rray.angle.0).into(),
417 };
418 } else {
419 left_normal = Ray {
420 origin: cray.origin,
421 angle: (lray.angle.1, -lray.angle.0).into(),
422 };
423 right_normal = Ray {
424 origin: cray.origin,
425 angle: (-rray.angle.1, rray.angle.0).into(),
426 };
427 }
428 left_normal.normalize();
429 right_normal.normalize();
430 loop {
431 let lcrd = left_normal.point_by_ratio(time_left);
432 crdv.push(lcrd);
433 left_normal = left_normal.rotate_by(if orient { 0.1 } else { -0.1 });
434 if orient && left_normal.orientation(&right_normal.point_by_ratio(1.)) == -1 {
435 break;
436 }
437 if !orient && left_normal.orientation(&right_normal.point_by_ratio(1.)) == 1 {
438 break;
439 }
440 }
441 crdv.push(right_normal.point_by_ratio(time_left));
442 }
443 }
444 if cur_vidx < usize::MAX {
445 let mut ls = LineString::from(crdv);
446 ls.close();
447 lsv.push(ls);
448 }
449 for ls in &lsv {
450 if ls.winding_order() == Some(WindingOrder::CounterClockwise) {
451 let p1: Polygon = Polygon::new(ls.clone(), vec![]);
452 res.push(p1);
453 }
454 }
455 for ls in &lsv {
456 if ls.winding_order() == Some(WindingOrder::Clockwise) {
457 for e in &mut res {
458 if e.contains(ls) {
459 e.interiors_push(ls.clone());
460 break;
461 }
462 }
463 }
464 }
465 MultiPolygon::new(res)
466 }
467
468 pub(crate) fn get_vertex_queue(&self, time_elapsed: f64) -> VertexQueue {
469 let mut ret = self.initial_vertex_queue.clone();
470 for e in &self.event_queue {
471 if e.unwrap_time() <= time_elapsed {
472 Self::apply_event(&mut ret, e);
473 ret.cleanup();
474 } else {
475 break;
476 }
477 }
478 ret
479 }
480
481 fn get_orientation(&self) -> bool {
482 let iz_ray = self.ray_vector[0].unwrap_ray();
483 let iz_left = self.ray_vector[0].unwrap_base_ray().0;
484 iz_left.orientation(&iz_ray.point_by_ratio(1.)) == 1
485 }
486
487 fn find_split_vertex(
488 cv: IndexType,
489 vertex_queue: &VertexQueue,
490 vertex_vector: &[VertexType],
491 is_init: bool,
492 orient: bool,
493 ) -> Vec<(f64, Coordinate, IndexType, usize)> {
494 let mut ret = Vec::new();
495 let cv_real = vertex_queue.get_real_index(cv);
496 let left_ray = vertex_vector[cv_real].unwrap_base_ray().0;
497 let right_ray = vertex_vector[cv_real].unwrap_base_ray().1;
498 if orient && fleq(left_ray.angle.outer_product(&right_ray.angle), 0.) {
499 return ret;
500 } if !orient && fgeq(left_ray.angle.outer_product(&right_ray.angle), 0.) {
502 return ret;
503 }
504
505 for (_, sv, sv_real) in vertex_queue.iter() {
506 let srv = vertex_queue.rv(sv);
507 let srv_real = vertex_queue.get_real_index(srv);
508 if sv == cv || sv == vertex_queue.rv(cv) || srv == cv || srv == vertex_queue.lv(cv) {
509 continue;
510 }
511 let base_ray = vertex_vector[sv_real].unwrap_base_ray().1;
512 let left_intersection = if left_ray.is_parallel(&base_ray) {
513 Default::default()
514 } else {
515 left_ray.intersect(&base_ray)
516 };
517 let right_intersection = if right_ray.is_parallel(&base_ray) {
518 Default::default()
519 } else {
520 right_ray.intersect(&base_ray)
521 };
522 let real_intersection = if left_ray.is_parallel(&base_ray) {
523 let ri_ray = right_ray.bisector(&base_ray.reverse(), right_intersection, !orient);
524 if !ri_ray.is_intersect(&vertex_vector[cv_real].unwrap_ray()) {
525 continue;
526 }
527 ri_ray.intersect(&vertex_vector[cv_real].unwrap_ray())
528 } else {
529 let li_ray = left_ray.bisector(&base_ray, left_intersection, orient);
530 if !li_ray.is_intersect(&vertex_vector[cv_real].unwrap_ray()) {
531 continue;
532 }
533 li_ray.intersect(&vertex_vector[cv_real].unwrap_ray())
534 };
535 if is_init {
536 if orient && base_ray.orientation(&real_intersection) < 0 {
537 continue;
538 }
539 if !orient && base_ray.orientation(&real_intersection) > 0 {
540 continue;
541 }
542 } else if orient {
543 if vertex_vector[sv_real]
544 .unwrap_ray()
545 .orientation(&real_intersection)
546 >= 0
547 {
548 continue;
549 }
550 if base_ray.orientation(&real_intersection) < 0 {
551 continue;
552 }
553 if vertex_vector[srv_real]
554 .unwrap_ray()
555 .orientation(&real_intersection)
556 < 0
557 {
558 continue;
559 }
560 } else {
561 if vertex_vector[sv_real]
562 .unwrap_ray()
563 .orientation(&real_intersection)
564 <= 0
565 {
566 continue;
567 }
568 if base_ray.orientation(&real_intersection) > 0 {
569 continue;
570 }
571 if vertex_vector[srv_real]
572 .unwrap_ray()
573 .orientation(&real_intersection)
574 > 0
575 {
576 continue;
577 }
578 }
579 let dist = real_intersection.dist_ray(&right_ray);
580 ret.push((dist, real_intersection, sv, sv_real));
581 }
582 ret.sort_by(|a, b| a.partial_cmp(b).unwrap());
583 if !is_init && !ret.is_empty() {
584 ret = vec![ret[0]];
585 }
586 ret
587 }
588
589 fn make_split_event(
590 cv: IndexType,
591 vertex_queue: &VertexQueue,
592 event_pq: &mut PriorityQueue<Timeline>,
593 vertex_vector: &[VertexType],
594 orient: bool,
595 ) {
596 let resv = Self::find_split_vertex(cv, vertex_queue, vertex_vector, true, orient);
597 let cv_real = vertex_queue.get_real_index(cv);
598 for (time, location, _, _) in resv {
599 event_pq.insert(Timeline::SplitEvent {
600 time,
601 location,
602 anchor_vertex: cv,
603 anchor_real: cv_real,
604 });
605 }
606 }
607
608 fn make_shrink_event(
609 cv: IndexType,
610 vertex_queue: &VertexQueue,
611 event_pq: &mut PriorityQueue<Timeline>,
612 vertex_vector: &[VertexType],
613 is_init: bool,
614 ) {
615 let mut lv = cv;
616 if vertex_queue.rv(cv) == vertex_queue.lv(cv) {
617 return;
618 }
619 for _ in 0..2 {
620 let rv = vertex_queue.rv(lv);
621 let lv_real = vertex_queue.get_real_index(lv);
622 let rv_real = vertex_queue.get_real_index(rv);
623 let lv_ray = vertex_vector[lv_real].unwrap_ray();
624 let rv_ray = vertex_vector[rv_real].unwrap_ray();
625 if lv_ray.is_intersect(&rv_ray) {
626 let cp = lv_ray.intersect(&rv_ray);
627 let dist = cp.dist_ray(&vertex_vector[lv_real].unwrap_base_ray().0);
628 let tie_break = lv_ray.origin.dist_coord(&rv_ray.origin);
629 event_pq.insert(Timeline::ShrinkEvent {
630 time: dist,
631 location: cp,
632 left_vertex: lv,
633 right_vertex: rv,
634 left_real: lv_real,
635 right_real: rv_real,
636 tie_break,
637 });
638 }
639 if is_init {
640 break;
641 }
642 lv = vertex_queue.lv(cv);
643 }
644 }
645
646 fn apply_event(
647 vertex_queue: &mut VertexQueue,
648 event: &Event,
649 ) -> (Option<IndexType>, Option<IndexType>) {
650 if let Event::VertexEvent {
651 merge_from,
652 merge_to,
653 ..
654 } = event
655 {
656 let merge_from = IndexType::PointerIndex(*merge_from);
657 let merge_to = IndexType::RealIndex(*merge_to);
658 let cv = vertex_queue.remove_and_set(merge_from, merge_to);
659 if vertex_queue.lv(cv) == vertex_queue.rv(cv) {
660 let lv = vertex_queue.lv(cv);
661 vertex_queue.content[lv.get_index()].done = true;
662 vertex_queue.content[cv.get_index()].done = true;
663 return (
664 Some(vertex_queue.content[vertex_queue.lv(cv).get_index()].index),
665 None,
666 );
667 }
668 return (Some(cv), None);
669 }
670 if let Event::EdgeEvent {
671 split_from,
672 split_into,
673 split_to_left,
674 split_to_right,
675 ..
676 } = event
677 {
678 let split_from = IndexType::PointerIndex(*split_from);
679 let split_into = IndexType::PointerIndex(*split_into);
680 let split_to_left = IndexType::RealIndex(*split_to_left);
681 let split_to_right = IndexType::RealIndex(*split_to_right);
682 let ret =
683 vertex_queue.split_and_set(split_from, split_into, split_to_left, split_to_right);
684 vertex_queue.cleanup();
685 return (Some(ret.0), Some(ret.1));
686 }
687
688 (None, None)
689 }
690
691 pub(crate) fn skeleton_of_polygon(input_polygon: &Polygon, orient: bool) -> Self {
692 Self::skeleton_of_polygon_vector(&vec![input_polygon.clone()], orient)
693 }
694
695 pub(crate) fn skeleton_of_polygon_vector(
696 input_polygon_vector: &Vec<Polygon>,
697 orient: bool,
698 ) -> Self {
699 let mut vertex_vector =
700 VertexType::initialize_from_polygon_vector(input_polygon_vector, orient);
701 let mut event_pq = PriorityQueue::new();
702 let mut event_queue = Vec::new();
703 let mut vertex_queue = VertexQueue::new();
704 vertex_queue.initialize_from_polygon_vector(input_polygon_vector);
705 let initial_vertex_queue = vertex_queue.clone();
706 for (_, cv, _) in vertex_queue.iter() {
708 Self::make_shrink_event(cv, &vertex_queue, &mut event_pq, &vertex_vector, true);
709 Self::make_split_event(cv, &vertex_queue, &mut event_pq, &vertex_vector, orient);
710 }
711
712 while !event_pq.is_empty() {
713 let x = event_pq.pop().unwrap();
714 if let Timeline::ShrinkEvent {
715 time,
716 location,
717 left_vertex,
718 right_vertex,
719 left_real,
720 right_real,
721 ..
722 } = x
723 {
724 if vertex_queue.content[left_vertex.get_index()].done
725 || vertex_queue.content[right_vertex.get_index()].done
726 || vertex_queue.get_real_index(left_vertex) != left_real
727 || vertex_queue.get_real_index(right_vertex) != right_real
728 {
729 continue;
730 }
731 let new_index = vertex_vector.len();
732 let left_ray = vertex_vector[left_real].unwrap_base_ray().0;
733 let right_ray = vertex_vector[right_real].unwrap_base_ray().1;
734 vertex_vector[left_real].set_parent(new_index);
735 vertex_vector[right_real].set_parent(new_index);
736 let new_event = Event::VertexEvent {
737 time,
738 merge_from: left_vertex.get_index(),
739 merge_to: new_index,
740 };
741 let new_vertex = VertexType::new_tree_vertex(location, left_ray, right_ray, orient);
742 vertex_vector.push(new_vertex);
743 match Self::apply_event(&mut vertex_queue, &new_event) {
744 (Some(IndexType::RealIndex(rv)), None) => {
745 vertex_vector[rv].set_parent(new_index);
746 vertex_vector[new_index] = VertexType::new_root_vertex(
747 vertex_vector[new_index].unwrap_location(),
748 vertex_vector[new_index].unwrap_time(),
749 );
750 }
751 (Some(cv), None) => {
752 Self::make_shrink_event(
753 cv,
754 &vertex_queue,
755 &mut event_pq,
756 &vertex_vector,
757 false,
758 );
759 }
760 _ => panic!("Expected Vertex Event"),
761 }
762 event_queue.push(new_event);
763 } else if let Timeline::SplitEvent {
764 time,
765 location,
766 anchor_vertex,
767 anchor_real,
768 } = x
769 {
770 if vertex_queue.content[anchor_vertex.get_index()].done
771 || vertex_queue.get_real_index(anchor_vertex) != anchor_real
772 {
773 continue;
774 }
775 vertex_queue.cleanup();
776 let rv = Self::find_split_vertex(
777 anchor_vertex,
778 &vertex_queue,
779 &vertex_vector,
780 false,
781 orient,
782 );
783 if rv.len() == 1 && feq(rv[0].0, time) && rv[0].1.eq(&location) {
784 let new_index1 = vertex_vector.len();
785 let new_index2 = new_index1 + 1;
786 let new_split_vertex = VertexType::new_split_vertex(
787 anchor_real,
788 location,
789 new_index1,
790 new_index2,
791 vertex_vector[anchor_real].unwrap_time(),
792 );
793 let new_tree_vertex1 = VertexType::new_tree_vertex(
794 location,
795 vertex_vector[anchor_real].unwrap_base_ray().0,
796 vertex_vector[rv[0].3].unwrap_base_ray().1,
797 orient,
798 );
799 let new_tree_vertex2 = VertexType::new_tree_vertex(
800 location,
801 vertex_vector[rv[0].3].unwrap_base_ray().1.reverse(),
802 vertex_vector[anchor_real].unwrap_base_ray().1,
803 orient,
804 );
805 vertex_vector.push(new_tree_vertex1);
806 vertex_vector.push(new_tree_vertex2);
807 vertex_vector.push(new_split_vertex);
808 let new_event = Event::EdgeEvent {
809 time,
810 split_from: anchor_vertex.get_index(),
811 split_into: rv[0].2.get_index(),
812 split_to_left: new_index1,
813 split_to_right: new_index2,
814 };
815 match Self::apply_event(&mut vertex_queue, &new_event) {
816 (Some(cv1), Some(cv2)) => {
817 vertex_vector[anchor_real].set_parent(new_index2 + 1);
818 Self::make_shrink_event(
819 cv1,
820 &vertex_queue,
821 &mut event_pq,
822 &vertex_vector,
823 false,
824 );
825 Self::make_shrink_event(
826 cv2,
827 &vertex_queue,
828 &mut event_pq,
829 &vertex_vector,
830 false,
831 );
832 }
833 _ => panic!("Expected Edge Event"),
834 }
835 event_queue.push(new_event);
836 }
837 }
838 vertex_queue.cleanup();
839 }
840 Self {
841 ray_vector: vertex_vector,
842 event_queue,
843 initial_vertex_queue,
844 }
845 }
846
847 pub(crate) fn to_linestring(&self) -> Vec<LineString> {
848 fn dfs_helper(
849 cur: usize,
850 visit: &mut Vec<bool>,
851 ret: &mut Vec<LineString>,
852 ray_vector: &Vec<VertexType>,
853 ) {
854 if visit[cur] {
855 return;
856 }
857 visit[cur] = true;
858 match ray_vector[cur] {
859 VertexType::Root { .. } => {}
860 VertexType::Tree { parent, .. } => {
861 if parent == usize::MAX {
862 let ls = LineString(vec![
863 ray_vector[cur].unwrap_location().into(),
864 ray_vector[cur].unwrap_ray().point_by_ratio(5.).into(),
865 ]);
866 ret.push(ls);
867 return;
868 }
869 let ls = LineString(vec![
870 ray_vector[cur].unwrap_location().into(),
871 ray_vector[parent].unwrap_location().into(),
872 ]);
873 ret.push(ls);
874 dfs_helper(parent, visit, ret, ray_vector);
875 }
876 VertexType::Split {
877 split_left,
878 split_right,
879 ..
880 } => {
881 dfs_helper(split_left, visit, ret, ray_vector);
882 dfs_helper(split_right, visit, ret, ray_vector);
883 }
884 }
885 }
886 let mut visit = vec![false; self.ray_vector.len()];
887 let mut ret = Vec::new();
888 for (_, _, e) in self.initial_vertex_queue.iter() {
889 dfs_helper(e, &mut visit, &mut ret, &self.ray_vector);
890 }
891 ret
892 }
893}