10

I have a large number shapefiles representing areas of interest for an analysis that will be conducted using various sources of satellite imagery (IKONOS, RapidEye, etc.). Unfortunately, the imagery doesn't use a pathrow system like Landsat for example, so the extents vary greatly.

I have shapefiles clipped to each AOI representing the extents of different imagery acquisitions, all of which have already been deemed acceptable. Some of these shapefiles have 500 or more polygons.

I need to find an approach, preferably one that can be automated (Python and ArcInfo 10 preferably, FOSS would be acceptable as well) to determine the fewest number of polygons to cover each of my areas of interest.

Chad Hawkins
  • 234
  • 1
  • 5
  • 3
    In full generality, this is an NP hard problem so it likely requires some powerful software. One approach is to frame it as an integer linear program: the polygons dissect the AOI into "atomic" polygons and each original polygon either fully covers or does not cover each atomic polygon. This information can be encoded in binary vectors. You seek to minimize the number of such vectors whose sum is 1 or larger in each component. Worked examples of how to solve similar problems are at http://mathematica.stackexchange.com/a/6888 and http://gis.stackexchange.com/a/27678. – whuber Oct 16 '12 at 16:03

2 Answers2

3

As noted by whuber generalizing this type of problem to find a high quality solution would be tricky but this approach might get you close enough without a great deal of work. Here is some pseudo code based on the following assumptions:

  1. Area of Interest A

  2. Set of polygons Y that completely cover A

    Start loop
 Iterate through Y
   Select the polygon x from Y that has greatest area of intersection with A

 Clip A with polygon x
 Remove x from Y 
 If A is null then end program

The idea is that you are iteratively reducing your Area of Interest with the satellite extent that has the largest overlap with the remaining Area of Interest. The AOI gets smaller on every iteration until nothing is left. This will probably not be an optimal solution but it should be reasonable and should run fairly quickly.

dblanchett
  • 1,356
  • 7
  • 15
0

Ok, so you have area A that represent some area and a bunch of imagery extents which can be defined as set Y.

If I have this correct, you can do a bunch of different functions:

  1. clipping the Imagery Extents by the Area A
  2. Perform a select by location using the Extent polygons and the completely contains option

You can then examine the areas of each and determine if you have self selecting polygons by doing some spatial geometry sorting using ArcPy and cursors.

Hope this help.

code base 5000
  • 840
  • 7
  • 17
  • 1
    Can you elaborate any more on how you would use the cursors? Going in I assumed it would come down to that somehow but I haven't been able to devise a methodology. I've considered starting with the top n polygons in area, eliminating from the remaining polygons those that are completely contained, and continuing to iterate in this fashion. This may be a start, but of course those polygons with the largest areas may not have very different extents. – Chad Hawkins Oct 16 '12 at 14:03