AreaCon

An open source C++ library for performing area-constrained partitioning operations on convex, 2D polygonal regions

About 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 Polygon Clipper Library). It can therefore be seamlessly integrated into 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:

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.

Basic Usage

To use AreaCon in your C++ program:

  1. Download the AreaCon library using the links at the top of the page.
  2. Unzip and extract the files,
  3. Place an #include "areacon.hpp" directive at the beginning of your program, and
  4. 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, general calls to AreaCon for use in area-constrained partitioning will usually follow these basic steps:
  1. Define the region to be partitioned, the number of regions to be used, and the desired areas of the resultant regions
  2. Define the density vector (discussion)
  3. Create and Initialize a partition object, and
  4. 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. Detailed source code documentation is included in pdf form with the AreaCon download, or can be found here. Some useful tips and troubleshooting advice can be found on the FAQ page, and more detailed discussion about the functionality of AreaCon can be found on the Wiki.

I am very interested to learn what type of projects have utilized AreaCon, so please feel free to contact me and let me know!

Citing AreaCon: Please cite AreaCon if wherever possible. For your 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.},
}

Quick Start Example

In-depth discussions about usage including how to create polygons, define prior density functions, choose algorithmic parameters, and initialize partition objects, as well as some helpful numerical examples can be found on the Wiki. However, as a quick-start guide that will illustrate generic usage, we offer the following example.

Partitioning Over a Uniform Prior: Consider a polygonal region with vertices (0,0), (5,0), (10,5), (10,10), (0,10) and uniform density. Suppose we wanted to partition the region into 3 disjoint sub-regions with relative (weighted) areas 0.2, 0.5, and 0.3. To perform this operation using AreaCon, simply run the following code:


//include the AreaCon header

#include areacon.h

using namespace AreaCon;

int main(void){

//Create the polygon to be partitioned (vertices must be listed 
in counter-clockwise order).
std::vector vertices = {Point(0,0), Point(5,0), Point(10,5), Point(10,10), Point(0,10)};
Poly Region(vertices);

//Define the number of regions and the desired areas
int NRegions = 3;
std::vector desired_area = {0.2, 0.5, 0.3};


//Create a uniform density grid (will be normalized automatically)
int Nx = 100, Ny = 100;
std::vector values(10000,0.1);
Density Prior(Region, Nx, Ny, values);

//Create a partition object
Partition Example_Partition(NRegions, Prior, desired_area);

//Initialize the centers (generators) and weights (Here, we'll use default parameters).
Example_Partition.InitializePartition();

//Find Partition
Example_Partition.CalculatePartition(false);
}

That's it!! The resulting partition and generators are then stored in Example_Partition.Covering and Example_Partition.Centers, respectively, and can be accessed using the Partition::GetCovering and Partition::GetCenters functions. A plot of the result is shown below:

Authors and Contributors

The AreaCon library's core components were written and developed by Jeffrey R. Peters (@jrpeters), with helpful insight from a variety of people including Amit Surana, William Sisson, Alexander Shilov, Grant Taylor, Terry Turpin, Rush Patel, and Francesco Bullo. The algorithms used by area-con are based primarily off of work by Rush Patel, Paolo Frasca, and Francesco Bullo (see References).

To report a bug, suggest a fix, or contribute to AreaCon, please do so via the GitHub page. Contributors are also encouraged to edit the project's Wiki , so as to build as comprehensive of a documentation as possible. Note that contributions can include usage examples or code-snippets that may be useful to other users.

Any issues, questions, or comments can also be sent directly to me via email, but please check the FAQ page and the Wiki first to make sure that the issue hasn't already been addressed. I also welcome any general comments or suggestions on how to improve the code, so feel free to pass those along.

License

Copyright © 2016. The Regents of the University of California. All rights reserved. Licensed pursuant to the terms and conditions available for viewing here.

The Clipper library, as used by AreaCon, is also subject to the following:

Copyright © 2016. The Regents of the University of California. Distributed under the Boost Software License, Version 1.0. Terms and Conditions.

Acknowledgments

AreaCon was originally developed as a part of a research effort sponsored by the U.S. Army Research Office and the Regents of the University of California, through Contract Number W911NF-09-D-0001 for the Institute for Collaborative Biotechnologies, and that the content of the information does not necessarily reflect the position or the policy of the Government or the Regents of the University of California, and no official endorsement should be inferred.

Home

Documentation

References

Links

Wiki

FAQ

Contact