Packing an irregular polygon with different sized circles
I'm trying to write a program in Python with Shapely that takes in shape files (right now congressional districts) and "packs" them with circles. The end goal is to have the center points and radii of the circles. I'd like to cover the maximum area with the least amount of circles.
All of the resources I've found via Google so far are about circle packing within standard geometric objects like squares/circles/triangles etc... So my instinct is to try and turn these shapes into triangles or something and then apply some existing algorithm to the simpler shapes.
Does this seem like the right path for problem solving if the shapes have lots of small concave edges? Or is there some algorithm I haven't been able to find via Google that anyone knows of that does this already?
You might start with this seminal paper, and then move backward & forward in time using Google Scholar:
Bern, Marshall, and David Eppstein. "Quadrilateral meshing by circle packing." International Journal of Computational Geometry & Applications 10.04 (2000): 347-360.
Part of Fig.1
In particular, much of the paper is on packing polygons with circles to achieve specific properties, e.g.,
- Compute the area of intersection between a circle and a triangle?
- Behavioral difference between constructing a `Nef_polyhedron_3` directly from OFF file and constructing from a `Polyhedron_3` built from the same file
- Catmull-Rom interpolation on SVG Paths
- Intersection between AABB and a capsule (swept sphere)
- Compute minimum area convex k-gon in 2d
- Difference between algorithm solution and MATLAB CVX solution in Graphical LASSO?
- k-way triangle set intersection and triangulation
- How to find the intersection point of a 3D curve and a 3D surface?
- Extending a line segment to fit into a bounding box
- Find visibility polyhedron given a point inside it
- While finding count of points inside some shape using KD-Tree, do we need to check areas intersection, or just compare depth-appropriate properties?
- Check if a 3D point lies inside a 3D platonic solid?
- How to check a point is inside an ellipsoid with orientation?
- In solidworks, is there a way to get the direction cosines of a surface normal?
- How to find overlapping area of convex coplanar polygons in 3D?
- Compensate IMU pan/tilt
- derive (approximate) rotation transform matrix (numpy) on a unit sphere given a mapping of vectors (n=12)
- Find two furthest points in a point set in linear time (2-approximation algorithm)
- Difference between quadtree and kd-tree
- How do I compute, in O(n) time, a convex hull of a set of points which are sorted by x-coordinate?
- Check if a point projected on a line segment is not outside it
- Segment Intersection
- How to convert spherical geometry to ellipsoid geometry c++ vertex generation
- Closest edge to a rectangle in a plane of rectangles
- What is most efficient way to find the intersection of a line and a circle in python?
- Initializing Half-edge data structure from vertices
- How to draw a circle in GNU Octave
- Calculate the outline of an abstract shape with holes
- What is the algorithm for finding the center of a circle from three points?
- Fast footpoint computation over polygonal lines in MATLAB