An open source C++ library for performing area-constrained partitioning operations on convex, 2D polygonal regions
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.
To use AreaCon in your C++ program:
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.},
}
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:
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.
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.
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.