|
Core 1.0
|
A simple set of boxes. More...
#include <boxset.h>
Public Member Functions | |
| BoxSet2 (const QVector< Box2 > &) | |
| Create a set. | |
| double | Area () const |
| Area of union of rectangles. | |
| bool | Inside (const Vector2 &) const |
| Check if a point is inside the set. | |
| Box2 | GetBox () const |
| Compute the bounding box. | |
| double | R (const Vector2 &) const |
| Compute the squared distance between a point and the set of boxes. | |
| double | Signed (const Vector2 &) const |
| Compute the signed distance between a point and the set of boxes. | |
| Vector2 | RandomInside (Random &=Random::R239) const |
| Generate a random vector inside the box set. | |
| void | Draw (QGraphicsScene &, const QPen &, const QBrush &) const |
| Draw the set of boxes. | |
Protected Attributes | |
| QVector< Box2 > | boxes |
| Set of boxes. | |
A simple set of boxes.
|
explicit |
Create a set.
| b | Set of boxes. |
| double BoxSet2::Area | ( | ) | const |
Area of union of rectangles.
For a given set of rectangles, it gives the area of the union. This problem is sometines called the Klee's measure problem [Klee77].
Implementation of Bentley's plane-sweep algorithm. First apply the coordinate compression technique. Then the y-structure, which is called measure tree, is simply implemented by using segment tree data structure.
Complexity: \( O(n \log n) \) time and \( O(n) \) space.
The coordinates of the boxes are real numbers, they are not rounded.
References: V. Klee (1977). Can the measure of U[a_i, b_i] be computed in less than O(n log n) steps? American Mathematical Monthly, 84, 284-285.
| void BoxSet2::Draw | ( | QGraphicsScene & | scene, |
| const QPen & | pen, | ||
| const QBrush & | brush ) const |
Draw the set of boxes.
| scene | Graphics scene. |
| pen | The pen. |
| brush | The brush. |
| Box2 BoxSet2::GetBox | ( | ) | const |
Compute the bounding box.
| bool BoxSet2::Inside | ( | const Vector2 & | p | ) | const |
Check if a point is inside the set.
Brute force algorithm, simply check all boxes.
| p | Point. |
| double BoxSet2::R | ( | const Vector2 & | p | ) | const |
Compute the squared distance between a point and the set of boxes.
| p | The point. |
| Vector2 BoxSet2::RandomInside | ( | Random & | random = Random::R239 | ) | const |
Generate a random vector inside the box set.
The distribution is uniform over the union of the boxes, even if the boxes overlap. It is obtained by rejection sampling:
A point of the union is therefore accepted through a single box, and all the points of the union have the same density. The acceptance probability is the ratio between the area of the union and the sum of the areas of the boxes, which is at least 1/n for n boxes, whatever the layout of the set. Drawing in the bounding box of the set instead would reject most of the points for sparse or elongated sets, and never terminates if the set has no area.
The cost of a call is proportional to the number of boxes.
If the set is empty, or if none of its boxes has an area, no point can be drawn uniformly: the origin is returned for an empty set, and the center of the first box otherwise.
| random | Random number generator. |
| double BoxSet2::Signed | ( | const Vector2 & | p | ) | const |
Compute the signed distance between a point and the set of boxes.
| p | The point. |