Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In QGIS, I have a vector polygon of a fixed size and shape. I also have a set of circles of a fixed radius and fixed location, which cover part of the polygon. What I would like to do is remove as many of the circles as possible while leaving as few gaps as possible, a gap being an area not covered by the circles. No circle should have overlap with another circle of more than 90% (or 80% or 70%- I am trying to run a few scenarios) of its area. I would also like to treat circles which go off the edge of the polygon in the same way as overlap, i.e. a circle with more than 90% of its area not covering the polygon would be eliminated. Inevitably there will be times when two or more circles could be chosen, I would like to prioritize them based on specific attributes. Here is a picture of the complete set of circles(pink) and the polygon I need them to cover (blue).

enter image description here

I am new to GIS and any extra elaboration on how to implement is greatly appreciated.

share|improve this question
You need to begin with a more objective, quantitative statement of your problem: what is your definition of a "gap"? How will you measure how "few" of them there are? Precisely how would the "prioritization" interact with the objective of minimizing gaps? – whuber Apr 23 '13 at 14:53
Furthermore pictures say more than words, so if you can add a screenshot displaying your problem that would ease up everything for people trying to help you. If you're not allowed to post an image, simply include the link to an imagehoster – Curlew Apr 23 '13 at 15:45
Very similar to this question:… – Kirk Kuykendall Apr 25 '13 at 3:58
I dont see anything but semantic similarity. This is subtractive, and the circles location is fixed not variable like in your example. Im not packing. – hdh Apr 29 '13 at 9:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.