6
$\begingroup$

I have an arbitrary polygon that I need to roughly represent using circles. Any point inside the polygon must lie inside a circle.

There will be points outside the polygon that will fall under a circle. I want to minimize this as much as possible. I believe there will be a trade off between the number of circles used and the amount of space covered outside the polygon.

I am limited to the number of circles I can use. It will be in the order of 1 to 10. Ideally I would like an algorithm that takes the number of circles and gives me ideal positions and radius'

Here is the simplest solution. Place a circle at the center of the polygon with a radius equal to the furthest point from the center. It looks something like this:

1 Circle

Ideally I would like something like this:

4 Circles

Is there an algorithm to solve a problem like this? Does this problem have a name?

For context I am working with GeoFences which can be defined as points with a radius. The solution needs to know when you enter the polygon.

$\endgroup$
4
  • $\begingroup$ Are your polygons all nearly rectangular like the one above, or any polygon imaginable? $\endgroup$ Aug 26, 2014 at 2:01
  • 1
    $\begingroup$ You may want to look up collision detection, because that's essentially the problem you're trying to solve. Approximating shapes with circles is just one method, but you might find an existing algorithm that works well for you. $\endgroup$ Aug 26, 2014 at 2:11
  • 1
    $\begingroup$ @forallepsilon they are arbitrary shapes representing areas on a map. $\endgroup$ Aug 26, 2014 at 2:14
  • $\begingroup$ Did you ever find a solution? I have a very similar proglem. $\endgroup$
    – fbl
    May 21, 2016 at 14:57

1 Answer 1

1
$\begingroup$

I don't know of an algorithm that solves this problem, but there is an algorithm that solves a similar problem. It's called the medial axis transform (source) (source), or computing the straight skeleton of a polygon. The result can be interpreted as an infinite number of circles that perfectly recover the original polygon. If you are looking to minimize the area outside, and don't care about the number of circles, then this algorithm is optimal.

In order to get a realistic answer, as you mentioned, you need to define a tradeoff between the number of circles and the extra area covered. It is probably possible to do some post-processing on the skeleton to get a reasonable result. I have also seen implementations that consider circles of a fixed size, which makes the problem much simpler. As a warning though, this problem looks a lot like the NP-hard bin packing problem, so it may be hard to find a good solution that runs quickly.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .