Core 1.0
BoxSet2 Class Reference

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.

Detailed Description

A simple set of boxes.

Constructor & Destructor Documentation

◆ BoxSet2()

BoxSet2::BoxSet2 ( const QVector< Box2 > & b)
explicit

Create a set.

Parameters
bSet of boxes.

Member Function Documentation

◆ Area()

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.

◆ Draw()

void BoxSet2::Draw ( QGraphicsScene & scene,
const QPen & pen,
const QBrush & brush ) const

Draw the set of boxes.

Parameters
sceneGraphics scene.
penThe pen.
brushThe brush.

◆ GetBox()

Box2 BoxSet2::GetBox ( ) const

Compute the bounding box.

See also
Box2::Box2(const QVector<Box2>&)

◆ Inside()

bool BoxSet2::Inside ( const Vector2 & p) const

Check if a point is inside the set.

Brute force algorithm, simply check all boxes.

Parameters
pPoint.

◆ R()

double BoxSet2::R ( const Vector2 & p) const

Compute the squared distance between a point and the set of boxes.

Parameters
pThe point.

◆ RandomInside()

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 box is chosen with a probability proportional to its area, and a point is drawn uniformly in this box;
  • the point is accepted only if the chosen box is the first box of the set that contains it.

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.

Parameters
randomRandom number generator.
Returns
A point of the union of the boxes.
See also
BoxSet2::Inside, Box2::RandomInside

◆ Signed()

double BoxSet2::Signed ( const Vector2 & p) const

Compute the signed distance between a point and the set of boxes.

Parameters
pThe point.