boostvoronoi_core/
visual_utils.rs

1// Boost.Polygon library voronoi_graphic_utils.hpp header file
2
3//          Copyright Andrii Sydorchuk 2010-2012.
4// Distributed under the Boost Software License, Version 1.0.
5//    (See accompanying file LICENSE_1_0.txt or copy at
6//          http://www.boost.org/LICENSE_1_0.txt)
7
8// See http://www.boost.org for updates, documentation, and revision history of C++ code.
9
10// Ported from C++ boost 1.76.0 to Rust in 2020/2021 by Eadf (github.com/eadf)
11
12//! Graphical utilities.
13
14use crate::{
15    cast,
16    geometry::{Line, Point},
17    BvError, InputType, OutputType,
18};
19use std::fmt;
20
21/// Utilities class, that contains set of routines handful for visualization.
22pub struct VoronoiVisualUtils {}
23
24impl VoronoiVisualUtils {
25    /// Discretize parabolic Voronoi edge.
26    /// Parabolic Voronoi edges are always formed by one point and one segment
27    /// from the initial input set.
28    ///
29    /// Args:
30    ///   point: input point in diagram coordinate system
31    ///   segment: input segment in diagram coordinate system
32    ///   max_dist: maximum discretization distance in output coordinate system,
33    ///   affine: an affine transform converting from diagram coordinate system to output coordinate system,
34    ///   discretization: point discretization of the given Voronoi edge in output coordinate system,
35    ///
36    /// Template arguments:
37    ///   InCT: coordinate type of the input geometries (usually integer).
38    ///   Point: point type, should model point concept.
39    ///   Segment: segment type, should model segment concept.
40    ///
41    /// Important:
42    ///   discretization should contain both edge endpoints initially.
43    pub fn discretize<I: InputType, F: OutputType>(
44        point: &Point<I>,
45        segment: &Line<I>,
46        max_dist: F,
47        affine: &SimpleAffine<F>,
48        discretization: &mut Vec<[F; 2]>,
49    ) {
50        // no need to discretize infinitely small distances
51        if discretization[0][0] == discretization[1][0]
52            && discretization[0][1] == discretization[1][1]
53        {
54            return;
55        }
56        // Apply the linear transformation to move start point of the segment to
57        // the point with coordinates (0, 0) and the direction of the segment to
58        // coincide the positive direction of the x-axis.
59        let segm_vec_x: F =
60            affine.transform_ix(segment.end.x) - affine.transform_ix(segment.start.x);
61        let segm_vec_y: F =
62            affine.transform_iy(segment.end.y) - affine.transform_iy(segment.start.y);
63        let sqr_segment_length = segm_vec_x * segm_vec_x + segm_vec_y * segm_vec_y;
64
65        // Compute x-coordinates of the endpoints of the edge
66        // in the transformed space.
67        let projection_start =
68            sqr_segment_length * Self::point_projection(affine, &discretization[0], segment);
69        let projection_end =
70            sqr_segment_length * Self::point_projection(affine, &discretization[1], segment);
71
72        // Compute parabola parameters in the transformed space.
73        // Parabola has next representation:
74        // f(x) = ((x-rot_x)^2 + rot_y^2) / (2.0*rot_y).
75        let point_vec_x = affine.transform_ix(point.x) - affine.transform_ix(segment.start.x);
76        let point_vec_y = affine.transform_iy(point.y) - affine.transform_iy(segment.start.y);
77        let rot_x = segm_vec_x * point_vec_x + segm_vec_y * point_vec_y;
78        let rot_y = segm_vec_x * point_vec_y - segm_vec_y * point_vec_x;
79
80        // Save the last point.
81        let last_point = (*discretization)[1];
82        let _ = discretization.pop();
83
84        // Use stack to avoid recursion.
85        let mut point_stack = vec![projection_end];
86        let mut cur_x = projection_start;
87        let mut cur_y = Self::parabola_y::<F>(cur_x, rot_x, rot_y);
88
89        // Adjust max_dist parameter in the transformed space.
90        let max_dist_transformed = max_dist * max_dist * sqr_segment_length;
91        while !point_stack.is_empty() {
92            let new_x = point_stack[point_stack.len() - 1]; // was .top();
93            let new_y = Self::parabola_y::<F>(new_x, rot_x, rot_y);
94
95            // Compute coordinates of the point of the parabola that is
96            // furthest from the current line segment.
97            let mid_x = (new_y - cur_y) / (new_x - cur_x) * rot_y + rot_x;
98            let mid_y = Self::parabola_y::<F>(mid_x, rot_x, rot_y);
99
100            // Compute maximum distance between the given parabolic arc
101            // and line segment that discretize it.
102            let mut dist = (new_y - cur_y) * (mid_x - cur_x) - (new_x - cur_x) * (mid_y - cur_y);
103            #[allow(clippy::suspicious_operation_groupings)]
104            {
105                dist = dist * dist
106                    / ((new_y - cur_y) * (new_y - cur_y) + (new_x - cur_x) * (new_x - cur_x));
107            }
108            if dist.is_nan() {
109                break;
110            }
111            if dist <= max_dist_transformed {
112                // Distance between parabola and line segment is less than max_dist.
113                let _ = point_stack.pop();
114                let inter_x = (segm_vec_x * new_x - segm_vec_y * new_y) / sqr_segment_length
115                    + affine.transform_ix(segment.start.x);
116                let inter_y = (segm_vec_x * new_y + segm_vec_y * new_x) / sqr_segment_length
117                    + affine.transform_iy(segment.start.y);
118                discretization.push([inter_x, inter_y]);
119                cur_x = new_x;
120                cur_y = new_y;
121            } else {
122                point_stack.push(mid_x);
123            }
124        }
125        // Update last point.
126        let discretization_len = discretization.len();
127        discretization[discretization_len - 1] = last_point;
128    }
129
130    /// Compute y(x) = ((x - a) * (x - a) + b * b) / (2 * b).
131    #[inline(always)]
132    #[allow(clippy::suspicious_operation_groupings)]
133    fn parabola_y<F: OutputType>(x: F, a: F, b: F) -> F {
134        ((x - a) * (x - a) + b * b) / (b + b)
135    }
136
137    // Get normalized length of the distance between:
138    //   1) point projection onto the segment
139    //   2) start point of the segment
140    // Return this length divided by the segment length. This is made to avoid
141    // sqrt computation during transformation from the initial space to the
142    // transformed one and vice versa. The assumption is made that projection of
143    // the point lies between the start-point and endpoint of the segment.
144    pub fn point_projection<I: InputType, F: OutputType>(
145        affine: &SimpleAffine<F>,
146        point: &[F; 2],
147        segment: &Line<I>,
148    ) -> F {
149        let segment_vec_x: F =
150            affine.transform_ix(segment.end.x) - affine.transform_ix(segment.start.x);
151        let segment_vec_y: F =
152            affine.transform_iy(segment.end.y) - affine.transform_iy(segment.start.y);
153        let point_vec_x = point[0] - affine.transform_ix(segment.start.x);
154        let point_vec_y = point[1] - affine.transform_iy(segment.start.y);
155        let sqr_segment_length = segment_vec_x * segment_vec_x + segment_vec_y * segment_vec_y;
156        let vec_dot = segment_vec_x * point_vec_x + segment_vec_y * point_vec_y;
157        vec_dot / sqr_segment_length
158    }
159}
160
161/// A simple 2d axis aligned bounding box.
162///
163/// If `min_max` is `None` no data has been assigned.
164#[derive(PartialEq, Eq, Clone, fmt::Debug)]
165pub struct Aabb2<F: OutputType> {
166    min_max_: Option<([F; 2], [F; 2])>,
167}
168
169impl<F: OutputType> Default for Aabb2<F> {
170    #[inline]
171    fn default() -> Self {
172        Self { min_max_: None }
173    }
174}
175
176impl<F: OutputType> Aabb2<F> {
177    /// Creates a new AABB with the limits defined by `p1` & `p2`
178    pub fn new<I: InputType>(p1: &Point<I>, p2: &Point<I>) -> Self {
179        let mut rv = Self::default();
180        rv.update_point(p1);
181        rv.update_point(p2);
182        rv
183    }
184
185    /// Creates a new AABB with `i32` coordinates
186    pub fn new_from_i32<I: InputType>(x1: i32, y1: i32, x2: i32, y2: i32) -> Self {
187        let mut rv = Self::default();
188        rv.update_coordinate::<I>(x1, y1);
189        rv.update_coordinate::<I>(x2, y2);
190        rv
191    }
192
193    #[inline(always)]
194    pub fn update_point<I: InputType>(&mut self, point: &Point<I>) {
195        let x = cast::<I, F>(point.x);
196        let y = cast::<I, F>(point.y);
197        self.update_vertex(x, y);
198    }
199
200    #[inline(always)]
201    pub fn update_coordinate<I: InputType>(&mut self, x: i32, y: i32) {
202        self.update_vertex(cast::<i32, F>(x), cast::<i32, F>(y));
203    }
204
205    #[inline]
206    pub fn update_vertex(&mut self, x: F, y: F) {
207        if self.min_max_.is_none() {
208            self.min_max_ = Some(([x, y], [x, y]));
209            return;
210        }
211        let (mut aabb_min, mut aabb_max) = self.min_max_.take().unwrap();
212
213        if x < aabb_min[0] {
214            aabb_min[0] = x;
215        }
216        if y < aabb_min[1] {
217            aabb_min[1] = y;
218        }
219        if x > aabb_max[0] {
220            aabb_max[0] = x;
221        }
222        if y > aabb_max[1] {
223            aabb_max[1] = y;
224        }
225        self.min_max_ = Some((aabb_min, aabb_max));
226    }
227
228    #[inline]
229    pub fn update_i64(&mut self, x: i64, y: i64) {
230        self.update_vertex(cast::<i64, F>(x), cast::<i64, F>(y))
231    }
232
233    #[inline]
234    pub fn update_f64(&mut self, x: f64, y: f64) {
235        self.update_vertex(cast::<f64, F>(x), cast::<f64, F>(y))
236    }
237
238    #[inline(always)]
239    pub fn update_line<I: InputType>(&mut self, line: &Line<I>) {
240        self.update_point(&line.start);
241        self.update_point(&line.end);
242    }
243
244    #[inline(always)]
245    pub fn get_high(&self) -> Option<[F; 2]> {
246        if let Some((_, high)) = self.min_max_ {
247            return Some(high);
248        }
249        None
250    }
251
252    #[inline(always)]
253    pub fn get_low(&self) -> Option<[F; 2]> {
254        if let Some((low, _)) = self.min_max_ {
255            return Some(low);
256        }
257        None
258    }
259
260    /// grows the aabb uniformly by some percent.
261    /// method does nothing if not initialized
262    pub fn grow_percent<I: InputType>(&mut self, percent: i32) {
263        if self.min_max_.is_some() {
264            let size_x = self.get_high().unwrap()[0] - self.get_low().unwrap()[0];
265            let size_y = self.get_high().unwrap()[1] - self.get_low().unwrap()[1];
266            let size = if size_x > size_y { size_x } else { size_y };
267
268            let delta = size * cast::<f32, F>((percent as f32) / 100.0);
269
270            let mut p = self.get_high().unwrap();
271            p[0] = p[0] + delta;
272            p[1] = p[1] + delta;
273            self.update_vertex(p[0], p[1]);
274            let mut p = self.get_low().unwrap();
275            p[0] = p[0] - delta;
276            p[1] = p[1] - delta;
277            self.update_vertex(p[0], p[1]);
278        }
279    }
280
281    /// returns `Some(true)` if the aabb contains the point (inclusive)
282    /// returns `None` if the aabb is uninitialized
283    ///```
284    /// # use boostvoronoi_core::geometry::Point;
285    /// # use boostvoronoi_core::visual_utils::Aabb2;
286    /// let p0 = Point::from([0,0]);
287    /// let p1 = Point::from([1,1]);
288    ///
289    /// let aabb = Aabb2::<f32>::new(&p0,&p1);
290    /// assert!(aabb.contains_point(&Point::from([1,1])).unwrap_or(false));
291    /// assert!(!aabb.contains_point(&Point::from([2,1])).unwrap_or(true));
292    /// ```
293    #[inline]
294    pub fn contains_point<I: InputType>(&self, point: &Point<I>) -> Option<bool> {
295        if let Some(min_max) = self.min_max_ {
296            let x = cast::<I, F>(point.x);
297            let y = cast::<I, F>(point.y);
298
299            Some(x >= min_max.0[0] && x <= min_max.1[0] && y >= min_max.0[1] && y <= min_max.1[1])
300        } else {
301            None
302        }
303    }
304
305    /// returns `Some(true)` if the aabb contains the line (inclusive)
306    /// returns `None` if the aabb is uninitialized
307    /// ```
308    /// # use boostvoronoi_core::BvError;
309    /// # use boostvoronoi_core::geometry::{Line, Point};
310    /// # use boostvoronoi_core::visual_utils::Aabb2;
311    /// let p0 = Point::from([0,0]);
312    /// let p1 = Point::from([10,10]);
313    ///
314    /// let aabb = Aabb2::<f32>::new(&p0,&p1);
315    /// assert!( aabb.contains_line(&Line::from([1,1,10,10])).unwrap_or(false));
316    /// assert!(!aabb.contains_line(&Line::from([1,-1,10,10])).unwrap_or(true));
317    /// ```
318    #[inline]
319    pub fn contains_line<I: InputType>(&self, line: &Line<I>) -> Option<bool> {
320        if self.min_max_.is_some() {
321            // unwrap is now safe
322            Some(
323                self.contains_point(&line.start).unwrap()
324                    && self.contains_point(&line.end).unwrap(),
325            )
326        } else {
327            None
328        }
329    }
330}
331
332/// This is a simple affine transformation object.
333/// Inadvertently it also serves as a type converter F<->I<->i32
334/// It can pan and zoom but not rotate.
335#[derive(PartialEq, Clone, fmt::Debug)]
336pub struct SimpleAffine<F: OutputType> {
337    /// The offsets used to center the 'source' coordinate system. Typically the input geometry
338    /// in this case.
339    to_center_: [F; 2],
340    /// A zoom scale
341    pub scale: [F; 2],
342    /// The offsets needed to center coordinates of interest on the 'dest' coordinate system.
343    /// i.e. the screen coordinate system.
344    pub to_offset: [F; 2],
345}
346
347impl<F: OutputType> Default for SimpleAffine<F> {
348    #[inline]
349    fn default() -> Self {
350        Self {
351            to_center_: [F::zero(), F::zero()],
352            scale: [F::one(), F::one()],
353            to_offset: [F::zero(), F::zero()],
354        }
355    }
356}
357
358impl<F: OutputType> SimpleAffine<F> {
359    pub fn new<I: InputType>(
360        source_aabb: &Aabb2<F>,
361        dest_aabb: &Aabb2<F>,
362    ) -> Result<Self, BvError> {
363        let min_dim = cast::<i32, F>(10);
364
365        if let Some(s_low) = source_aabb.get_low() {
366            if let Some(s_high) = source_aabb.get_high() {
367                if let Some(d_low) = dest_aabb.get_low() {
368                    if let Some(d_high) = dest_aabb.get_high() {
369                        //println!("s_low:{:?},s_high:{:?},d_low:{:?},d_high:{:?}", s_low, s_high, d_low, d_high);
370
371                        let source_aabb_center = [
372                            -(s_low[0] + s_high[0]) / cast::<i32, F>(2_i32),
373                            -(s_low[1] + s_high[1]) / cast::<i32, F>(2_i32),
374                        ];
375                        let source_aabb_size = [
376                            (s_high[0] - s_low[0]).max(min_dim),
377                            (s_high[1] - s_low[1]).max(min_dim),
378                        ];
379
380                        let dest_aabb_center = [
381                            (d_low[0] + d_high[0]) / cast::<i32, F>(2_i32),
382                            (d_low[1] + d_high[1]) / cast::<i32, F>(2_i32),
383                        ];
384                        let dest_aabb_size = [
385                            (d_high[0] - d_low[0]).max(min_dim),
386                            (d_high[1] - d_low[1]).max(min_dim),
387                        ];
388
389                        // make sure the larges dimension of source fits inside smallest of dest
390                        let source_aabb_size = source_aabb_size[0].max(source_aabb_size[1]);
391                        let dest_aabb_size = dest_aabb_size[0].min(dest_aabb_size[1]);
392                        let scale = dest_aabb_size / source_aabb_size;
393
394                        return Ok(Self {
395                            to_center_: source_aabb_center,
396                            scale: [scale, scale],
397                            to_offset: dest_aabb_center,
398                        });
399                    }
400                }
401            }
402        }
403        Err(BvError::InternalError(format!(
404            "could not get dimension of the AABB. {}:{}",
405            file!(),
406            line!()
407        )))
408    }
409
410    /// transform from destination coordinate system to source coordinate system
411    #[inline(always)]
412    pub fn reverse_transform<I: InputType>(&self, x: F, y: F) -> Result<[I; 2], BvError> {
413        let x = self.reverse_transform_x(x)?;
414        let y = self.reverse_transform_y(y)?;
415        Ok([x, y])
416    }
417
418    /// transform from destination coordinate system to source coordinate system
419    #[inline(always)]
420    pub fn reverse_transform_x<I: InputType>(&self, x: F) -> Result<I, BvError> {
421        super::try_cast::<F, I>(
422            ((x - self.to_offset[0]) / self.scale[0] - self.to_center_[0]).round(),
423        )
424    }
425
426    /// transform from dest coordinate system to source coordinate system
427    #[inline(always)]
428    pub fn reverse_transform_y<I: InputType>(&self, y: F) -> Result<I, BvError> {
429        super::try_cast::<F, I>(
430            ((y - self.to_offset[1]) / self.scale[1] - self.to_center_[1]).round(),
431        )
432    }
433
434    /// transform from source coordinate system to dest coordinate system
435    #[inline(always)]
436    pub fn transform(&self, x: F, y: F) -> [F; 2] {
437        [self.transform_x(x), self.transform_y(y)]
438    }
439
440    /// transform from source coordinate system to dest coordinate system
441    /// float x coordinate
442    #[inline(always)]
443    pub fn transform_x(&self, x: F) -> F {
444        (x + self.to_center_[0]) * self.scale[0] + self.to_offset[0]
445    }
446
447    /// transform from source coordinate system to dest coordinate system
448    /// float y coordinate
449    #[inline(always)]
450    pub fn transform_y(&self, y: F) -> F {
451        (y + self.to_center_[1]) * self.scale[1] + self.to_offset[1]
452    }
453
454    /// transform from source coordinate system to dest coordinate system
455    #[inline(always)]
456    pub fn transform_i<I: InputType>(&self, point: [I; 2]) -> [F; 2] {
457        [self.transform_ix(point[0]), self.transform_iy(point[1])]
458    }
459
460    /// transform from source coordinate system to dest coordinate system
461    #[inline(always)]
462    pub fn transform_f(&self, point: [F; 2]) -> [F; 2] {
463        [self.transform_fx(point[0]), self.transform_fy(point[1])]
464    }
465
466    /// transform from source coordinate system to dest coordinate system
467    #[inline(always)]
468    pub fn transform_p<I: InputType>(&self, point: &Point<I>) -> [F; 2] {
469        [self.transform_ix(point.x), self.transform_iy(point.y)]
470    }
471
472    /// transform from source coordinate system to dest coordinate system
473    /// integer x coordinate
474    #[inline(always)]
475    pub fn transform_ix<I: InputType>(&self, x: I) -> F {
476        (cast::<I, F>(x) + self.to_center_[0]) * self.scale[0] + self.to_offset[0]
477    }
478
479    /// transform from source coordinate system to dest coordinate system
480    /// integer y coordinate
481    #[inline(always)]
482    pub fn transform_iy<I: InputType>(&self, y: I) -> F {
483        (cast::<I, F>(y) + self.to_center_[1]) * self.scale[1] + self.to_offset[1]
484    }
485
486    /// transform from source coordinate system to destination coordinate system
487    /// float x coordinate
488    #[inline(always)]
489    pub fn transform_fx(&self, x: F) -> F {
490        (x + self.to_center_[0]) * self.scale[0] + self.to_offset[0]
491    }
492
493    /// transform from source coordinate system to destination coordinate system
494    /// float y coordinate
495    #[inline(always)]
496    pub fn transform_fy(&self, y: F) -> F {
497        (y + self.to_center_[1]) * self.scale[1] + self.to_offset[1]
498    }
499
500    /// multiply the scale by a factor f
501    #[inline(always)]
502    pub fn zoom(&mut self, f: F) {
503        self.scale = [self.scale[0] * f, self.scale[1] * f];
504    }
505}
506
507/// Helper function: Affine transforms and casts a slice of `[[integer,integer,integer,integer]]` into
508/// input data for the Builder.
509pub fn to_segments_offset<I1: InputType, I2: InputType>(
510    points: &[[I1; 4]],
511    scale_x: f64,
512    scale_y: f64,
513    dx: i64,
514    dy: i64,
515) -> Vec<Line<I2>> {
516    let fx = |x: I1| cast::<f64, I2>(cast::<I1, f64>(x) * scale_x) + cast::<i64, I2>(dx);
517    let fy = |y: I1| cast::<f64, I2>(cast::<I1, f64>(y) * scale_y) + cast::<i64, I2>(dy);
518    points
519        .iter()
520        .map(|x| Line {
521            start: Point {
522                x: fx(x[0]),
523                y: fy(x[1]),
524            },
525            end: Point {
526                x: fx(x[2]),
527                y: fy(x[3]),
528            },
529        })
530        .collect()
531}
boostvoronoi_core/visual_utils.rs

boostvoronoi_core/
visual_utils.rs
