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

Are there any restrictions on who or what projects can use AreaCon?

All of the codes contained on this site are open-source, subject to terms specified here .

How do I cite AreaCon?

Please use the bibtex citation found here.

How do I contribute to AreaCon?

See Authors and Contributors.

AreaCon is taking a very long time or is getting stuck when calculating partitions. How can I speed it up?

The performance of AreaCon, i.e., convergence speed, is dependent upon a variety of factors including, but not limited to, the number of regions used, the size of the polygon of interest, the nature of the underlying density function, and the degree of accuracy required. For a given problem setup, performance can be optimized by adjusting algorithmic parameters.

If AreaCon is taking an unreasonably long time, it is usually an indicator of poor parameter choice. For tips and in-depth information about choosing parameters wisely, see the discussion on the Wiki.

Occasionally, the problem scaling can also cause poor performance. AreaCon operates best over length scales on the order of ones or tens, so it is usually beneficial to scale problem dimensions to be on this order of magnitude. Mismatches in length scales, e.g., densities with both coarse and fine level features, should also be avoided if possible.

If none of the adjustments mentioned result in reasonable performance, it may be necessary to consider manipulating the problem structure, e.g., choose fewer regions, a smaller area, or a different density function.

Why don't the calculated regions have the correct area?

If the algorithm converges, i.e., the script finishes, but the calculated regions do not have the correct area, the most likely culprit is numerical error. As previously mentioned, AreaCon is a numerical implementation of a continuous-time algorithm and thus there are a number of algorithmic parameters that can affect the library's convergence properties. It is important to choose these parameters wisely, based on the particular problem of interest to ensure useful results. For a thorough discussion about choosing appropriate parameters, visit the Wiki.

Decreasing the parameters "volume_tolerance" and "convergence_criterion", while simultaneously increasing "max_iterations_volume" will usually fix accuracy issues. Note however, that it may also be necessary to decrease "weights_step" upon adjusting the aforementioned parameters to maintain numerical stability. Using finer density grids can also sometimes help (increasing "Nx" and "Ny").

Can I use AreaCon to calculate a partition of a non-convex region?

Possibly...AreaCon is not explicitly designed for use with non-convex regions. If a partitioning operation is initialized directly with a non-convex region, AreaCon may or may not produce a valid solution.

However, the prior density function that is used is not required to be non-zero over the entire convex region. Therefore, an alternative approach to partitioning of a non-convex region would be to bound the region with a (convex) bounding box, specify the box as the partitioning area, and create a prior density that is zero at every grid point that is not located in the original non-convex region. Using the result, a partition of the non-convex region can be created by intersecting each region resulting from the bounding box partition. Note, however, that this method may cause oddly shaped or disconnected regions, and may produce centers that do not actually lie in the region.

The partitioning operation seems to produce large regions where the density is high, and small regions where the density is low. Is this right?

This could be correct if the desired areas are unbalanced. For example, if the partition has only 2 regions with specified desired areas of, say, 0.1 and 0.9, then this sort of behavior is certainly possible.

The more likely scenario, however, is that the density vector is not oriented correctly. That is, the entries of Density::Values are not aligned with what was intended. The values should be stored so that the value of the prior density at the (i,j)th grid point appears in Density::Values[Ny*i+j]. See the Wiki for a more thorough discussion.

Does AreaCon have any built-in tools for creating/correctly orienting standard prior density functions, e.g., Gaussians?

The current version of AreaCon, unfortunately, does not contain explicit functions for creating density vectors. This is a potential addition to future versions.

However, there are a number of freely available libraries (that are not explicitly associated with AreaCon) that contain tools for creating and working with probability density functions, especially those based on common distributions. It is relatively straightforward to utilize these, or other methods, to create a properly oriented density grid for use with AreaCon (see Wiki).

Is there a way to visualize the results of the partitioning operation?

The current version of AreaCon does not contain built-in functions for creating images or video. This is a potential addition to future versions. For now, AreaCon does contain functions that will write the results of partitioning operations (and the underlying density function) to text files. Using these files, it is straightforward to write scripts in other platforms (Matlab, for example) to read in the data and plot the result.