jrpeters edited this page Mar 10, 2016 · 7 revisions

#Welcome to the AreaCon wiki!

This Wiki is meant as an interactive platform for contributors to provide information that they feel will benefit other AreaCon users and/or better the overall project. Note that high-level information about the project is also provided on the project page; however, more extensive documentation and low-level details is hosted here.

##What is AreaCon?

AreaCon is a free open source C++ library for performing area-constrained partitioning operations on convex, 2D polygonal regions. It is intended primarily for use in robot and mobile sensor network applications in which the workspace is to be divided among the available agents in an optimal way. AreaCon allows the user to specify the final weighted area of each of the resultant regions, thus providing a natural load-balancing that is useful in a variety of static and dynamic coverage applications, as well as a variety of applications that involve optimal division of workload. Specifically, given a prior density defined over a polygonal region of interest, AreaCon provides a numerical implementation of a theoretically rigorous, bio-inspired algorithm that systematically divides the region into a set of disjoint, convex, and centroidal regions with pre-specified areas. The entire library consists of a single compilation unit (one .hpp and one .cpp file), which has dependence on a single free and open source third party library (the Clipper Library). It can therefore be seamlessly integrated into larger, more complex planning codes that require simple load-balancing steps without the weight of a larger computational geometry library.

AreaCon v.1 provides the following on planar, convex polygonal environments:

  • Area-constrained partitioning over arbitrary density functions
  • Centroid computation
  • A variety of useful geometric structures and associated functions

Note that although AreaCon only provides explicit support for convex polygonal environments, it supports arbitrary density functions. Therefore, the library can also be used for partitioning on a much larger class of planar environments by strategically defining regions of zero density. Exact or arbitrary precision arithmetic is avoided for additional robustness in numerical implementation. However, functionality is still somewhat sensitive to a variety of algorithmic parameters (step-sizes, stopping-criteria, integration parameters, etc.). If these parameters are chosen poorly or the scale of the underlying density varies wildly, the library can and will return errors. Despite this, if parameters are chosen properly the library will produce high-quality results for a number of environments and densities. In addition, reasonable results can be obtained for most "regular" workspaces using the provided default parametric values.

##Dependencies

AreaCon relies on the Clipper Library to perform crucial geometric operations on polygonal sets. The Clipper library is an open-source library is distributed under the Boost Software License (see the License.txt file).

For convenience, source code for the version of the Clipper library that is required by AreaCon is included with the source code in this repository. Source code for the most recent version of the Clipper Library is available here.

##Basic Usage

AreaCon provides a straightforward tool for performing area-constrained partitioning operations in the context of C++ projects. To use AreaCon in your C++ program:

  • Download the zip file on the "code" page,
  • Unzip and extract the files,
  • Place an #include "areacon.hpp" directive at the beginning of your program, and
  • Link your code with "areacon.cpp" and "clipper.cpp" when compiling.

You can now use AreaCon in your program!

AreaCon can be used in a variety of different ways. However, calls to AreaCon for use general partitioning operations will usually follow these basic steps:

  • Define the region to be partitioned, the number of regions to be used, and the desired areas of the resultant regions
  • Define the density vector (see "Defining Densities" Page)
  • Create and initialize a partition object, and
  • Call the "CalculatePartition" function.

That's all there is to it! Note that AreaCon can also be used for a variety of other basic geometric operations, e.g., finding centroids. Source code documentation is included in pdf form with the AreaCon download, or can be found here. Additional tips and troubleshooting can be found on the FAQ page.

##Citing AreaCon

Please cite AreaCon wherever possible. For convenience, a bibtex citation is provided below:

@Misc{AreaCon:16,
  author =        {J.R. Peters and Contributors},
  title =         {The {AreaCon} Library},
  howpublished =  {\texttt{http://www.areacon.org}},
  year =          {2016},
  note =          {v. 1},
  abstract =      {A C++ library for area-constrained partitioning.},
}
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.