## Contents- Boost.Polygon Main Page
- Design Overview
- Isotropy
- Coordinate Concept
- Interval Concept
- Point Concept
- Segment Concept
- Rectangle Concept
- Polygon 90 Concept
- Polygon 90 With Holes Concept
- Polygon 45 Concept
- Polygon 45 With Holes Concept
- Polygon Concept
- Polygon With Holes Concept
- Polygon 90 Set Concept
- Polygon 45 Set Concept
- Polygon Set Concept
- Connectivity Extraction 90
- Connectivity Extraction 45
- Connectivity Extraction
- Property Merge 90
- Property Merge 45
- Property Merge
- Voronoi Main Page
- Voronoi Benchmark
- Voronoi Builder
- Voronoi Diagram
- Voronoi Predicates
- Voronoi Robust FPT
## Other Resources## Polygon Sponsor |
## Voronoi Builder
Voronoi builder is the event generator structure. It implements the sweepline
algorithm
that scans a 2D space and generates two types of events:
site events and circle events (we won't go into details what those are
exactly). Each event is reported to the output data structure builder.
The structure shares Voronoi name as the events generated by it
correspond to the Voronoi diagram edges and vertices, thus giving
enough information to construct the Voronoi diagram of a set of points
and linear segments. The requirements for the input/output
coordinate type of
the builder geometries are not the same as for the rest of the
Boost.Polygon library. The main differences are in the following: |

voronoi_builder() | Default constructor. |

size_t insert_point(const int_type& x, const int_type& y) |
Inserts a point object with
the specified coordinates into the Voronoi builder. Returns index number of the inserted site. |

size_t insert_segment(const int_type& x1, const int_type& y1, const int_type& x2, const int_type& y2) |
Inserts a segment object
with the specified coordinates into the Voronoi builder. Returns index number of the inserted site. |

template <typename OUTPUT> void construct(OUTPUT* output) |
Runs sweepline
algorithm over the set of the inserted geometries, outputs site and
circle events to the OUTPUT data structure. It's responsibility of the
output data structure to process them. |

void clear() |
Clears the
list of the inserted geometries. Sets index counter to zero. |

The library provides the default coordinate type traits specialization for the 32-bit signed integer type:

template <typename T>

struct voronoi_ctype_traits;

template <>

struct voronoi_ctype_traits<int32> {

typedef int32 int_type;

typedef int64 int_x2_type;

typedef uint64 uint_x2_type;

typedef extended_int<128> big_int_type;

typedef fpt64 fpt_type;

typedef extended_exponent_fpt<fpt_type>
efpt_type;

typedef ulp_comparison<fpt_type> ulp_cmp_type;

typedef type_converter_fpt to_fpt_converter_type;

typedef type_converter_efpt to_efpt_converter_type;

};

int_type |
At least X-bit signed
integer type. |

int_x2_type |
At least 2X-bit signed
integer type. |

uint_x2_type |
At least 2X-bit unsigned
integer type. |

big_int_type |
At least 8X-bit signed
integer type for voronoi of points. At least 64X-bit signed integer type for voronoi of segments. |

fpt_type |
IEEE-754 floating point
type, with mantissa at least (X+16) bits and exponent able to handle
32X-bit unsigned integer type. |

efpt_type |
IEEE-754 floating point
type, with mantissa at least (X+16) bits and exponent able to handle
64X-bit unsigned integer type. |

ulp_cmp_type |
Ulp comparison structure
that checks if two fpt_type values are within the given ulp range
(relative error range). |

to_fpt_converter_type |
Type converter structure
that converts any of the integer types above plus efpt_type to the
fpt_type using operator(). |

to_efpt_converter_type |
Type converter structure
that converts any of the integer types above to the efpt_type using
operator(). |

Notes:

- Four different integer types are used (instead of a single big_int_type) to slightly improve algorithm performance and memory usage.
- As the maximum required size of the big_int_type is known in advance (based on the size of the integer type), library provided implementation of a fixed integer could be used (it is much faster than heap-allocated big integers).
- Two separate floating-point types are defined because for the input with 32-bit signed integer coordinates double won't be able to handle 2048-bit (64 * 32) integers as they will overflow its exponent. On the gcc compiler it's possible to use 80-bit long doubles for both fpt types, however this is not supported by MSVC compiler.
- efpt_type and to_efpt_converter_type are not used to construct Voronoi diagram of points (mocks will work fine).
- For an example of the user defined coordinate type traits see advanced Voronoi tutorial.

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) |