BoxSet2 Class Reference

A simple set of boxes. More...

#include <boxset.h>

Public Member Functions
double	Area () const
	Area of union of rectangles. More...
bool	Inside (const Vector2 &) const
	Check if a point is inside the set. More...
Box2	GetBox () const
	Compute the bounding box. More...
double	R (const Vector2 &) const
	Compute the squared distance between a point and the set of boxes. More...
double	Signed (const Vector2 &) const
	Compute the signed distance between a point and the set of boxes. More...
Vector2	RandomInside (Random &=Random::R239) const
	Generate a random vector inside the box set. More...
void	Draw (QGraphicsScene &, const QPen &, const QBrush &) const
	Draw the set of boxes. More...

Protected Attributes
QVector< Box2 >	boxes
	Set of boxes.

Detailed Description

A simple set 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.

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

scene	Graphics scene.
pen	The pen.
brush	The 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

p

Point.

R()

double BoxSet2::R

(

const Vector2 &

p

)

const

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

Parameters

p	The point.

RandomInside()

Vector2 BoxSet2::RandomInside

(

Random &

random = Random::R239

)

const

Generate a random vector inside the box set.

Parameters

random

Random number generator.

Signed()

double BoxSet2::Signed

(

const Vector2 &

p

)

const

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

Parameters

p	The point.