original_docstring: Organize a list of coordinate rings into one or more polygons with holes.
      Returns a list of polygons, where each polygon is composed of a single exterior
      ring, and one or more interior holes.
  
      Rings must be closed, and cannot intersect each other (non-self-intersecting polygon).
      Rings are determined as exteriors if they run in clockwise direction, or interior
      holes if they run in counter-clockwise direction. This method is used to construct
      GeoJSON (multi)polygons from the shapefile polygon shape type, which does not
      explicitly store the structure of the polygons beyond exterior/interior ring orientation. 
      
docstring: Organize a list of coordinate rings into one or more polygons with holes.
  Returns a list of polygons, where each polygon is composed of a single exterior
  ring, and one or more interior holes.
  
  Rings must be closed, and cannot intersect each other (non-self-intersecting polygon).
  Rings are determined as exteriors if they run in clockwise direction, or interior
  holes if they run in counter-clockwise direction. This method is used to construct
  GeoJSON (multi)polygons from the shapefile polygon shape type, which does not
  explicitly store the structure of the polygons beyond exterior/interior ring orientation.
docstring_tokens: Organize a list of coordinate rings into one or more polygons with holes . Returns a list of polygons where each polygon is composed of a single exterior ring and one or more interior holes . Rings must be closed and cannot intersect each other ( non - self - intersecting polygon ) . Rings are determined as exteriors if they run in clockwise direction or interior holes if they run in counter - clockwise direction . This method is used to construct GeoJSON ( multi ) polygons from the shapefile polygon shape type which does not explicitly store the structure of the polygons beyond exterior / interior ring orientation .
code: def organize_polygon_rings(rings):
      '''Organize a list of coordinate rings into one or more polygons with holes.
      Returns a list of polygons, where each polygon is composed of a single exterior
      ring, and one or more interior holes.
  
      Rings must be closed, and cannot intersect each other (non-self-intersecting polygon).
      Rings are determined as exteriors if they run in clockwise direction, or interior
      holes if they run in counter-clockwise direction. This method is used to construct
      GeoJSON (multi)polygons from the shapefile polygon shape type, which does not
      explicitly store the structure of the polygons beyond exterior/interior ring orientation. 
      '''
      # first iterate rings and classify as exterior or hole
      exteriors = []
      holes = []
      for ring in rings:
          # shapefile format defines a polygon as a sequence of rings
          # where exterior rings are clockwise, and holes counterclockwise
          if signed_area(ring) < 0:
              # ring is exterior
              exteriors.append(ring)
          else:
              # ring is a hole
              holes.append(ring)
                  
      # if only one exterior, then all holes belong to that exterior
      if len(exteriors) == 1:
          # exit early
          poly = [exteriors[0]] + holes
          polys = [poly]
          return polys
  
      # multiple exteriors, ie multi-polygon, have to group holes with correct exterior
      # shapefile format does not specify which holes belong to which exteriors
      # so have to do efficient multi-stage checking of hole-to-exterior containment
      elif len(exteriors) > 1:
          # exit early if no holes
          if not holes:
              polys = []
              for ext in exteriors:
                  poly = [ext]
                  polys.append(poly)
              return polys
          
          # first determine each hole's candidate exteriors based on simple bbox contains test
          hole_exteriors = dict([(hole_i,[]) for hole_i in xrange(len(holes))])
          exterior_bboxes = [ring_bbox(ring) for ring in exteriors]
          for hole_i in hole_exteriors.keys():
              hole_bbox = ring_bbox(holes[hole_i])
              for ext_i,ext_bbox in enumerate(exterior_bboxes):
                  if bbox_contains(ext_bbox, hole_bbox):
                      hole_exteriors[hole_i].append( ext_i )
  
          # then, for holes with still more than one possible exterior, do more detailed hole-in-ring test
          for hole_i,exterior_candidates in hole_exteriors.items():
              
              if len(exterior_candidates) > 1:
                  # get hole sample point
                  hole_sample = ring_sample(holes[hole_i], ccw=True)
                  # collect new exterior candidates
                  new_exterior_candidates = []
                  for ext_i in exterior_candidates:
                      # check that hole sample point is inside exterior
                      hole_in_exterior = ring_contains_point(exteriors[ext_i], hole_sample)
                      if hole_in_exterior:
                          new_exterior_candidates.append(ext_i)
  
                  # set new exterior candidates
                  hole_exteriors[hole_i] = new_exterior_candidates
  
          # if still holes with more than one possible exterior, means we have an exterior hole nested inside another exterior's hole
          for hole_i,exterior_candidates in hole_exteriors.items():
              
              if len(exterior_candidates) > 1:
                  # exterior candidate with the smallest area is the hole's most immediate parent
                  ext_i = sorted(exterior_candidates, key=lambda x: abs(signed_area(exteriors[x])))[0]
                  hole_exteriors[hole_i] = [ext_i]
  
          # separate out holes that are orphaned (not contained by any exterior)
          orphan_holes = []
          for hole_i,exterior_candidates in list(hole_exteriors.items()):
              if not exterior_candidates:
                  warnings.warn('Shapefile shape has invalid polygon: found orphan hole (not contained by any of the exteriors); interpreting as exterior.')
                  orphan_holes.append( hole_i )
                  del hole_exteriors[hole_i]
                  continue
  
          # each hole should now only belong to one exterior, group into exterior-holes polygons
          polys = []
          for ext_i,ext in enumerate(exteriors):
              poly = [ext]
              # find relevant holes
              poly_holes = []
              for hole_i,exterior_candidates in list(hole_exteriors.items()):
                  # hole is relevant if previously matched with this exterior
                  if exterior_candidates[0] == ext_i:
                      poly_holes.append( holes[hole_i] )
              poly += poly_holes
              polys.append(poly)
  
          # add orphan holes as exteriors
          for hole_i in orphan_holes:
              ext = holes[hole_i] # could potentially reverse their order, but in geojson winding order doesn't matter
              poly = [ext]
              polys.append(poly)
  
          return polys
  
      # no exteriors, be nice and assume due to incorrect winding order
      else:
          warnings.warn('Shapefile shape has invalid polygon: no exterior rings found (must have clockwise orientation); interpreting holes as exteriors.')
          exteriors = holes # could potentially reverse their order, but in geojson winding order doesn't matter
          polys = [[ext] for ext in exteriors]
          return polys
code_tokens: def organize_polygon_rings ( rings ) : exteriors = [ ] holes = [ ] for ring in rings : if signed_area ( ring ) < 0 : exteriors . append ( ring ) else : holes . append ( ring ) if len ( exteriors ) == 1 : poly = [ exteriors [ 0 ] ] + holes polys = [ poly ] return polys elif len ( exteriors ) > 1 : if not holes : polys = [ ] for ext in exteriors : poly = [ ext ] polys . append ( poly ) return polys hole_exteriors = dict ( [ ( hole_i , [ ] ) for hole_i in xrange ( len ( holes ) ) ] ) exterior_bboxes = [ ring_bbox ( ring ) for ring in exteriors ] for hole_i in hole_exteriors . keys ( ) : hole_bbox = ring_bbox ( holes [ hole_i ] ) for ext_i , ext_bbox in enumerate ( exterior_bboxes ) : if bbox_contains ( ext_bbox , hole_bbox ) : hole_exteriors [ hole_i ] . append ( ext_i ) for hole_i , exterior_candidates in hole_exteriors . items ( ) : if len ( exterior_candidates ) > 1 : hole_sample = ring_sample ( holes [ hole_i ] , ccw = True ) new_exterior_candidates = [ ] for ext_i in exterior_candidates : hole_in_exterior = ring_contains_point ( exteriors [ ext_i ] , hole_sample ) if hole_in_exterior : new_exterior_candidates . append ( ext_i ) hole_exteriors [ hole_i ] = new_exterior_candidates for hole_i , exterior_candidates in hole_exteriors . items ( ) : if len ( exterior_candidates ) > 1 : ext_i = sorted ( exterior_candidates , key = lambda x : abs ( signed_area ( exteriors [ x ] ) ) ) [ 0 ] hole_exteriors [ hole_i ] = [ ext_i ] orphan_holes = [ ] for hole_i , exterior_candidates in list ( hole_exteriors . items ( ) ) : if not exterior_candidates : warnings . warn ( 'Shapefile shape has invalid polygon: found orphan hole (not contained by any of the exteriors); interpreting as exterior.' ) orphan_holes . append ( hole_i ) del hole_exteriors [ hole_i ] continue polys = [ ] for ext_i , ext in enumerate ( exteriors ) : poly = [ ext ] poly_holes = [ ] for hole_i , exterior_candidates in list ( hole_exteriors . items ( ) ) : if exterior_candidates [ 0 ] == ext_i : poly_holes . append ( holes [ hole_i ] ) poly += poly_holes polys . append ( poly ) for hole_i in orphan_holes : ext = holes [ hole_i ] poly = [ ext ] polys . append ( poly ) return polys else : warnings . warn ( 'Shapefile shape has invalid polygon: no exterior rings found (must have clockwise orientation); interpreting holes as exteriors.' ) exteriors = holes polys = [ [ ext ] for ext in exteriors ] return polys
short_docstring: Organize a list of coordinate rings into one or more polygons with holes.
short_docstring_tokens: Organize a list of coordinate rings into one or more polygons with holes .
comment: '''Organize a list of coordinate rings into one or more polygons with holes.
      Returns a list of polygons, where each polygon is composed of a single exterior
      ring, and one or more interior holes.
  
      Rings must be closed, and cannot intersect each other (non-self-intersecting polygon).
      Rings are determined as exteriors if they run in clockwise direction, or interior
      holes if they run in counter-clockwise direction. This method is used to construct
      GeoJSON (multi)polygons from the shapefile polygon shape type, which does not
      explicitly store the structure of the polygons beyond exterior/interior ring orientation. 
      '''$SEP$# first iterate rings and classify as exterior or hole
  $SEP$# shapefile format defines a polygon as a sequence of rings
  $SEP$# where exterior rings are clockwise, and holes counterclockwise
  $SEP$# ring is exterior
  $SEP$# ring is a hole
  $SEP$# if only one exterior, then all holes belong to that exterior
  $SEP$# exit early
  $SEP$# multiple exteriors, ie multi-polygon, have to group holes with correct exterior
  $SEP$# shapefile format does not specify which holes belong to which exteriors
  $SEP$# so have to do efficient multi-stage checking of hole-to-exterior containment
  $SEP$# exit early if no holes
  $SEP$# first determine each hole's candidate exteriors based on simple bbox contains test
  $SEP$# then, for holes with still more than one possible exterior, do more detailed hole-in-ring test
  $SEP$# get hole sample point
  $SEP$# collect new exterior candidates
  $SEP$# check that hole sample point is inside exterior
  $SEP$# set new exterior candidates
  $SEP$# if still holes with more than one possible exterior, means we have an exterior hole nested inside another exterior's hole
  $SEP$# exterior candidate with the smallest area is the hole's most immediate parent
  $SEP$# separate out holes that are orphaned (not contained by any exterior)
  $SEP$# each hole should now only belong to one exterior, group into exterior-holes polygons
  $SEP$# find relevant holes
  $SEP$# hole is relevant if previously matched with this exterior
  $SEP$# add orphan holes as exteriors
  $SEP$# could potentially reverse their order, but in geojson winding order doesn't matter
  $SEP$# no exteriors, be nice and assume due to incorrect winding order
  $SEP$# could potentially reverse their order, but in geojson winding order doesn't matter
  