3

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.

whuber
  • 69,783
  • 15
  • 186
  • 281
hdh
  • 43
  • 5
  • 1
    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
  • 1
    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: http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-number-of-points-within-constrained-area-at-a-minimum – Kirk Kuykendall Apr 25 '13 at 03: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 09:49

0 Answers0