MyGAL
Box.h
1 /* MyGAL
2  * Copyright (C) 2019 Pierre Vigier
3  *
4  * This program is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU Lesser General Public License as published
6  * by the Free Software Foundation, either version 3 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU Lesser General Public License for more details.
13  *
14  * You should have received a copy of the GNU Lesser General Public License
15  * along with this program. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #pragma once
19 
20 // STL
21 #include <array>
22 // My includes
23 #include "Vector2.h"
24 #include "util.h"
25 
29 namespace mygal
30 {
31 
32 template<typename T>
33 class Diagram;
34 
35 template<typename T>
37 
46 template<typename T>
47 class Box
48 {
49 public:
50  T left;
51  T bottom;
52  T right;
53  T top;
55  bool contains(const Vector2<T>& point) const
56  {
57  return almostBetween(point.x, left, right) && almostBetween(point.y, bottom, top);
58  }
59 
60 private:
61  friend Diagram<T>;
62  friend FortuneAlgorithm<T>;
63 
64  enum class Side : int {Left, Bottom, Right, Top};
65 
66  struct Intersection
67  {
68  Side side;
69  Vector2<T> point;
70  };
71 
72  // Useful for Fortune's algorithm
73  Intersection getFirstIntersection(const Vector2<T>& origin, const Vector2<T>& direction) const
74  {
75  // origin must be in the box
76  auto intersection = Intersection{};
77  auto t = std::numeric_limits<T>::infinity();
78  if (direction.x > static_cast<T>(0.0))
79  {
80  t = (right - origin.x) / direction.x;
81  intersection.side = Side::Right;
82  intersection.point = origin + t * direction;
83  }
84  else if (direction.x < static_cast<T>(0.0))
85  {
86  t = (left - origin.x) / direction.x;
87  intersection.side = Side::Left;
88  intersection.point = origin + t * direction;
89  }
90  if (direction.y > static_cast<T>(0.0))
91  {
92  auto newT = (top - origin.y) / direction.y;
93  if (newT < t)
94  {
95  intersection.side = Side::Top;
96  intersection.point = origin + newT * direction;
97  }
98  }
99  else if (direction.y < static_cast<T>(0.0))
100  {
101  auto newT = (bottom - origin.y) / direction.y;
102  if (newT < t)
103  {
104  intersection.side = Side::Bottom;
105  intersection.point = origin + newT * direction;
106  }
107  }
108  return intersection;
109  }
110 
111  // Useful for diagram intersection
112  int getIntersections(const Vector2<T>& origin, const Vector2<T>& destination, std::array<Intersection, 2>& intersections) const
113  {
114  // WARNING: If the intersection is a corner, both intersections are equals
115  // I tried to add this test (i == 0 || !almostEqual(t[0], t[1])) to detect duplicates
116  // But it does not make a big difference
117  auto direction = destination - origin;
118  auto t = std::array<T, 2>();
119  auto i = std::size_t(0); // index of the current intersection
120  // Left
121  if (strictlyLower(origin.x, left) || strictlyLower(destination.x, left))
122  {
123  t[i] = (left - origin.x) / direction.x;
124  if (strictlyBetween(t[i], static_cast<T>(0.0), static_cast<T>(1.0)))
125  {
126  intersections[i].side = Side::Left;
127  intersections[i].point = origin + t[i] * direction;
128  // Check that the intersection is inside the box
129  if (almostBetween(intersections[i].point.y, bottom, top))
130  ++i;
131  }
132  }
133  // Right
134  if (strictlyGreater(origin.x, right) || strictlyGreater(destination.x, right))
135  {
136  t[i] = (right - origin.x) / direction.x;
137  if (strictlyBetween(t[i], static_cast<T>(0.0), static_cast<T>(1.0)))
138  {
139  intersections[i].side = Side::Right;
140  intersections[i].point = origin + t[i] * direction;
141  // Check that the intersection is inside the box
142  if (almostBetween(intersections[i].point.y, bottom, top))
143  ++i;
144  }
145  }
146  // Bottom
147  if (strictlyLower(origin.y, bottom) || strictlyLower(destination.y, bottom))
148  {
149  t[i] = (bottom - origin.y) / direction.y;
150  if (i < 2 && strictlyBetween(t[i], static_cast<T>(0.0), static_cast<T>(1.0)))
151  {
152  intersections[i].side = Side::Bottom;
153  intersections[i].point = origin + t[i] * direction;
154  // Check that the intersection is inside the box
155  if (almostBetween(intersections[i].point.x, left, right))
156  ++i;
157  }
158  }
159  // Top
160  if (strictlyGreater(origin.y, top) || strictlyGreater(destination.y, top))
161  {
162  t[i] = (top - origin.y) / direction.y;
163  if (i < 2 && strictlyBetween(t[i], static_cast<T>(0.0), static_cast<T>(1.0)))
164  {
165  intersections[i].side = Side::Top;
166  intersections[i].point = origin + t[i] * direction;
167  // Check that the intersection is inside the box
168  if (almostBetween(intersections[i].point.x, left, right))
169  ++i;
170  }
171  }
172  // Sort the intersections from the nearest to the farthest
173  if (i == 2 && t[0] > t[1])
174  std::swap(intersections[0], intersections[1]);
175  return i;
176  }
177 };
178 
179 }
Data structure representing a partitioning of the space.
Definition: Box.h:33
Class representing a box.
Definition: Box.h:47
Implementation of Fortune&#39;s algorithm.
Definition: Box.h:36
Class representing a 2D vector.
Definition: Vector2.h:33
Namespace of MyGAL.
Definition: Box.h:29
T bottom
Definition: Box.h:51
T left
Definition: Box.h:50
T top
Definition: Box.h:53
T right
Definition: Box.h:52