andreesteve / voronoice

A nice and fast way to construct 2D Voronoi Diagrams
MIT License
34 stars 9 forks source link

Non-centered Bounding boxes not respected #2

Closed Telzhaak closed 3 years ago

Telzhaak commented 3 years ago

Hello,

  1. noice crate, thank you for the work!
  2. non-centered boxes are not handled correctly internally

The Voronoi-algorithm for example uses BoundingBox::is_inside()

is_inside = point.x.abs() <= self.top_right.x && point.y.abs() <= self.top_right.y

which only works for centered boxes.

Similarily which_edge()

if point.y == self.top_right.y {
    // top
    BoundingBoxTopBottomEdge::Top
} else if point.y == -self.top_right.y {
    BoundingBoxTopBottomEdge::Bottom
} else {
    BoundingBoxTopBottomEdge::None
}

relies on mirrored coordinates around the origin (0,0)

point.y == -self.top_right.y

The simplest solution would be to add a private centered_bounding_box-variable to the VoronoiBuilder.

  1. Center arbitrary bounding_box by subtracting BoundingBox.center() from every site
  2. Use this centered centered_bounding_box in all calculations (which is the current working state)
  3. Reapply shift back to every obtained vertex/centerpoint

However, this is problematic, if users can access the algorithm directly, without using VoronoiBuilder, because they could supply noncentered boxes instead which results in something like this: Voronoi_problems 25 different Voronoi-Diagrams with different Bounding boxes. The blue cross is the world origin, and the red dots in the 3 quadrants (right-up, right-down, left-down) are sites for which no Voronoi-Diagram could be generated