Lets imagine that NASA is planning to send a new robot to Mars. Each day the center situated on Earth will send a destination point coordinates the robot needs to reach by the end of the day. Of course we'd like to save as much energy as possible thus choosing the shortest possible path. This would be a straight line in a perfect world (we don't consider curvature of surface), but situation becomes more complicated as there are some rocks and wells on Mars our robot can't go through. Behind of those our robot has some dimensions that might not allow it to pass narrow places.

Very-large-scale integration (VLSI) is the process of creating integrated circuits by combining thousands of transistors into a single chip. Considering the fact that it may take weeks or months to get an integrated circuit manufactured, designers often spend large amounts of time analyzing their layouts to avoid costly mistakes. One of the common static analysis checks is minimum distance requirement between the components of an integrated circuit (distance should be greater than specified value).

- The absolute error of the coordinates of the output Voronoi diagram inside the 32-bit integer discretization grid is slightly smaller than the absolute error of discretization itself, thus could be neglected at all.
- In both problems above we didn't consider error of measurement.
For example: is it possible to construct a map of the Mars within the
0.5
centimetres precision, or to get coordinates of the circuit parts
withing the subatomic precision? I guess the answer for both questions
would be "No". And that actually means that the error of the
discretization
step could be neglected comparing to the error produced by the
measuring
devices.

So the main step would be to declare the voronoi coordinate type traits that satisfy set of restrictions explained here:

struct my_voronoi_ctype_traits {

typedef boost::int64_t int_type;

typedef detail::extended_int<3> int_x2_type;

typedef detail::extended_int<3> uint_x2_type;

typedef detail::extended_int<128> big_int_type;

typedef fpt80 fpt_type;

typedef fpt80 efpt_type;

typedef my_ulp_comparison ulp_cmp_type;

typedef my_fpt_converter to_fpt_converter_type;

typedef my_fpt_converter to_efpt_converter_type;

};

It is always better to use C++ built-in types wherever it's possible. That's why we use the 64-bit signed integer type to handle our input coordinates. int_x2_type and uint_x2_type is required to handle 96-bit signed/unsigned integers. As there is no such built-in type we use library provided efficient fixed integer type. The big integer type should be capable to handle 48 * 64 bit integers, that is less than 32 * 128, and so far we are good with extended_int<128> type. We use the same floating point type for both fpt_type and efpt_type as it has enough exponent bits to represent both 48 * 32 bit and 48 * 64 bit integers (that is also the reason we don't need two floating-point converter structures). The ulp_cmp_type structure checks weather two IEEE floating-point values are within the given signed integer ulp range (we won't analyze corresponding code here as it requires deep understanding of the floating-point architecture and its usage to compare floating-point values), but just to mention the declaration is following:

struct my_ulp_comparison {

enum Result {

LESS = -1,

EQUAL = 0,

MORE = 1

};

Result operator()(fpt80 a, fpt80 b, unsigned int maxUlps) const;

};

The last step would be to declare the my_fpt_converter structure (converts the integer types to the floating-point type):

struct my_fpt_converter {

template <typename T>

fpt80 operator()(const T& that) const {

return static_cast<fpt80>(that);

}

template <size_t N>

fpt80 operator()(const typename detail::extended_int<N>& that) const {

fpt80 result = 0.0;

for (size_t i = 1; i <= (std::min)((size_t)3, that.size()); ++i) {

if (i != 1)

result *= static_cast<fpt80>(0x100000000ULL);

result += that.chunks()[that.size() - i];

}

return (that.count() < 0) ? -result : result;

}

};

At this point we are done with declaration of the Voronoi coordinate type traits. The next step is to declare the Voronoi diagram traits:

struct my_voronoi_diagram_traits {

typedef fpt80 coordinate_type;

typedef voronoi_cell<coordinate_type> cell_type;

typedef voronoi_vertex<coordinate_type> vertex_type;

typedef voronoi_edge<coordinate_type> edge_type;

struct vertex_equality_predicate_type {

public:

enum { ULPS = 128 };

bool operator()(const point_type &v1, const point_type &v2) const {

return (ulp_cmp(v1.x(), v2.x(), ULPS) == my_ulp_comparison::EQUAL &&

ulp_cmp(v1.y(), v2.y(), ULPS) == my_ulp_comparison::EQUAL);

}

private:

my_ulp_comparison ulp_cmp;

};

};

Above we simply declared the Voronoi primitive types and vertex equality predicate using the new coordinate type and corresponding ulp comparison structure. As we are done with the declaration of the coordinate type specific structures we are ready to proceed to the construction step itself. The first step would be to initialize voronoi_builder structure with a set of random points:

// Random generator and distribution. MAX is equal to 2^48.

boost::mt19937_64 gen(std::time(0));

boost::random::uniform_int_distribution<boost::int64_t> distr(-MAX, MAX-1);

// Declaring and configuring Voronoi builder with the new coordinate type traits.

voronoi_builder<boost::int64_t, my_voronoi_ctype_traits> vb;

// Voronoi builder initialization step.

for (size_t i = 0; i < GENERATED_POINTS; ++i) {

boost::int64_t x = distr(gen);

boost::int64_t y = distr(gen);

vb.insert_point(x, y);

}

The second step would be to generate the Voronoi diagram and this is done as before with the two lines of code:

// Declaring and configuring Voronoi diagram structure with the new coordinate type traits.

voronoi_diagram<fpt80, my_voronoi_diagram_traits> vd;

vb.construct(&vd);

From this point the user can operate with the Voronoi diagram data structure and in our tutorial we output some simple stats of the resulting Voronoi graph. Probably the hardest part of this tutorial is the declaration of the ulp comparison structure. The library provides efficient well-commented cross-platform implementation for 64-bit floating-point type (double). So the best advice would be to follow that implementation, but before doing that really consider thoughtfully if the default coordinate types are not capable to deal with your problem.

Copyright: | Copyright © Andrii Sydorchuk 2010-2012. |
---|---|

License: | Distributed under the Boost Software
License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
http://www.boost.org/LICENSE_1_0.txt) |