class_docstr: A query-only R-tree spatial index created using the
  Sort-Tile-Recursive (STR) [1]_ algorithm.
  
  The tree indexes the bounding boxes of each geometry.  The tree is
  constructed directly at initialization and nodes cannot be added or
  removed after it has been created.
  
  All operations return indices of the input geometries.  These indices
  can be used to index into anything associated with the input geometries,
  including the input geometries themselves, or custom items stored in
  another object of the same length as the geometries.
  
  Bounding boxes limited to two dimensions and are axis-aligned (equivalent to
  the ``bounds`` property of a geometry); any Z values present in geometries
  are ignored for purposes of indexing within the tree.
  
  Any mixture of geometry types may be stored in the tree.
  
  Note: the tree is more efficient for querying when there are fewer
  geometries that have overlapping bounding boxes and where there is greater
  similarity between the outer boundary of a geometry and its bounding box.
  For example, a MultiPolygon composed of widely-spaced individual Polygons
  will have a large overall bounding box compared to the boundaries of its
  individual Polygons, and the bounding box may also potentially overlap many
  other geometries within the tree.  This means that the resulting tree may be
  less efficient to query than a tree constructed from individual Polygons.
  
  Parameters
  ----------
  geoms : sequence
      A sequence of geometry objects.
  node_capacity : int, default 10
      The maximum number of child nodes per parent node in the tree.
  
  References
  ----------
  .. [1] Leutenegger, Scott T.; Edgington, Jeffrey M.; Lopez, Mario A.
     (February 1997). "STR: A Simple and Efficient Algorithm for
     R-Tree Packing".
     https://ia600900.us.archive.org/27/items/nasa_techdoc_19970016975/19970016975.pdf
class_docstr_tok: ["A","query-only","R-tree","spatial","index","created","using","the","Sort-Tile-Recursive","(","STR",")","[","1","]","_","algorithm",".","The","tree","indexes","the","bounding","boxes","of","each","geometry",".","The","tree","is","constructed","directly","at","initialization","and","nodes","can","not","be","added","or","removed","after","it","has","been","created",".","All","operations","return","indices","of","the","input","geometries",".","These","indices","can","be","used","to","index","into","anything","associated","with","the","input","geometries",",","including","the","input","geometries","themselves",",","or","custom","items","stored","in","another","object","of","the","same","length","as","the","geometries",".","Bounding","boxes","limited","to","two","dimensions","and","are","axis-aligned","(","equivalent","to","the","``","bounds","``","property","of","a","geometry",")",";","any","Z","values","present","in","geometries","are","ignored","for","purposes","of","indexing","within","the","tree",".","Any","mixture","of","geometry","types","may","be","stored","in","the","tree",".","Note",":","the","tree","is","more","efficient","for","querying","when","there","are","fewer","geometries","that","have","overlapping","bounding","boxes","and","where","there","is","greater","similarity","between","the","outer","boundary","of","a","geometry","and","its","bounding","box",".","For","example",",","a","MultiPolygon","composed","of","widely-spaced","individual","Polygons","will","have","a","large","overall","bounding","box","compared","to","the","boundaries","of","its","individual","Polygons",",","and","the","bounding","box","may","also","potentially","overlap","many","other","geometries","within","the","tree",".","This","means","that","the","resulting","tree","may","be","less","efficient","to","query","than","a","tree","constructed","from","individual","Polygons",".","Parameters","--","--","--","--","--","geoms",":","sequence","A","sequence","of","geometry","objects",".","node_capacity",":","int",",","default","10","The","maximum","number","of","child","nodes","per","parent","node","in","the","tree",".","References","--","--","--","--","--","..","[","1","]","Leutenegger",",","Scott","T.",";","Edgington",",","Jeffrey","M.",";","Lopez",",","Mario","A",".","(","February","1997",")",".","``","STR",":","A","Simple","and","Efficient","Algorithm","for","R-Tree","Packing","''",".","https",":","\/\/ia600900.us.archive.org\/27\/items\/nasa_techdoc_19970016975\/19970016975.pdf"]
docstr: Return the integer indices of all combinations of each input geometry
  and tree geometries where the bounding box of each input geometry
  intersects the bounding box of a tree geometry.
  
  If the input geometry is a scalar, this returns an array of shape (n, ) with
  the indices of the matching tree geometries.  If the input geometry is an
  array_like, this returns an array with shape (2,n) where the subarrays
  correspond to the indices of the input geometries and indices of the
  tree geometries associated with each.  To generate an array of pairs of
  input geometry index and tree geometry index, simply transpose the
  result.
  
  If a predicate is provided, the tree geometries are first queried based
  on the bounding box of the input geometry and then are further filtered
  to those that meet the predicate when comparing the input geometry to
  the tree geometry:
  predicate(geometry, tree_geometry)
  
  The 'dwithin' predicate requires GEOS >= 3.10.
  
  Bounding boxes are limited to two dimensions and are axis-aligned
  (equivalent to the ``bounds`` property of a geometry); any Z values
  present in input geometries are ignored when querying the tree.
  
  Any input geometry that is None or empty will never match geometries in
  the tree.
  
  Parameters
  ----------
  geometry : Geometry or array_like
      Input geometries to query the tree and filter results using the
      optional predicate.
  predicate : {None, 'intersects', 'within', 'contains', 'overlaps', 'crosses','touches', 'covers', 'covered_by', 'contains_properly', 'dwithin'}, optional
      The predicate to use for testing geometries from the tree
      that are within the input geometry's bounding box.
  distance : number or array_like, optional
      Distances around each input geometry within which to query the tree
      for the 'dwithin' predicate.  If array_like, shape must be
      broadcastable to shape of geometry.  Required if predicate='dwithin'.
  
  Returns
  -------
  ndarray with shape (n,) if geometry is a scalar
      Contains tree geometry indices.
  
  OR
  
  ndarray with shape (2, n) if geometry is an array_like
      The first subarray contains input geometry indices.
      The second subarray contains tree geometry indices.
  
  Examples
  --------
  >>> from shapely import box, Point
  >>> import numpy as np
  >>> points = [Point(0, 0), Point(1, 1), Point(2,2), Point(3, 3)]
  >>> tree = STRtree(points)
  
  Query the tree using a scalar geometry:
  
  >>> indices = tree.query(box(0, 0, 1, 1))
  >>> indices.tolist()
  [0, 1]
  
  Query using an array of geometries:
  
  >>> boxes = np.array([box(0, 0, 1, 1), box(2, 2, 3, 3)])
  >>> arr_indices = tree.query(boxes)
  >>> arr_indices.tolist()
  [[0, 0, 1, 1], [0, 1, 2, 3]]
  
  Or transpose to get all pairs of input and tree indices:
  
  >>> arr_indices.T.tolist()
  [[0, 0], [0, 1], [1, 2], [1, 3]]
  
  Retrieve the tree geometries by results of query:
  
  >>> tree.geometries.take(indices).tolist()
  [<POINT (0 0)>, <POINT (1 1)>]
  
  Retrieve all pairs of input and tree geometries:
  
  >>> np.array([boxes.take(arr_indices[0]),tree.geometries.take(arr_indices[1])]).T.tolist()
  [[<POLYGON ((1 0, 1 1, 0 1, 0 0, 1 0))>, <POINT (0 0)>],
   [<POLYGON ((1 0, 1 1, 0 1, 0 0, 1 0))>, <POINT (1 1)>],
   [<POLYGON ((3 2, 3 3, 2 3, 2 2, 3 2))>, <POINT (2 2)>],
   [<POLYGON ((3 2, 3 3, 2 3, 2 2, 3 2))>, <POINT (3 3)>]]
  
  Query using a predicate:
  
  >>> tree = STRtree([box(0, 0, 0.5, 0.5), box(0.5, 0.5, 1, 1), box(1, 1, 2, 2)])
  >>> tree.query(box(0, 0, 1, 1), predicate="contains").tolist()
  [0, 1]
  >>> tree.query(Point(0.75, 0.75), predicate="dwithin", distance=0.5).tolist()
  [0, 1, 2]
  
  >>> tree.query(boxes, predicate="contains").tolist()
  [[0, 0], [0, 1]]
  >>> tree.query(boxes, predicate="dwithin", distance=0.5).tolist()
  [[0, 0, 0, 1], [0, 1, 2, 2]]
  
  Retrieve custom items associated with tree geometries (records can
  be in whatever data structure so long as geometries and custom data
  can be extracted into arrays of the same length and order):
  
  >>> records = [
  ...     {"geometry": Point(0, 0), "value": "A"},
  ...     {"geometry": Point(2, 2), "value": "B"}
  ... ]
  >>> tree = STRtree([record["geometry"] for record in records])
  >>> items = np.array([record["value"] for record in records])
  >>> items.take(tree.query(box(0, 0, 1, 1))).tolist()
  ['A']
  
  
  Notes
  -----
  In the context of a spatial join, input geometries are the "left"
  geometries that determine the order of the results, and tree geometries
  are "right" geometries that are joined against the left geometries. This
  effectively performs an inner join, where only those combinations of
  geometries that can be joined based on overlapping bounding boxes or
  optional predicate are returned.
docstr_tok: ["Return","the","integer","indices","of","all","combinations","of","each","input","geometry","and","tree","geometries","where","the","bounding","box","of","each","input","geometry","intersects","the","bounding","box","of","a","tree","geometry",".","If","the","input","geometry","is","a","scalar",",","this","returns","an","array","of","shape","(","n",",",")","with","the","indices","of","the","matching","tree","geometries",".","If","the","input","geometry","is","an","array_like",",","this","returns","an","array","with","shape","(","2",",","n",")","where","the","subarrays","correspond","to","the","indices","of","the","input","geometries","and","indices","of","the","tree","geometries","associated","with","each",".","To","generate","an","array","of","pairs","of","input","geometry","index","and","tree","geometry","index",",","simply","transpose","the","result",".","If","a","predicate","is","provided",",","the","tree","geometries","are","first","queried","based","on","the","bounding","box","of","the","input","geometry","and","then","are","further","filtered","to","those","that","meet","the","predicate","when","comparing","the","input","geometry","to","the","tree","geometry",":","predicate","(","geometry",",","tree_geometry",")","The","'dwithin","'","predicate","requires","GEOS",">","=","3.10",".","Bounding","boxes","are","limited","to","two","dimensions","and","are","axis-aligned","(","equivalent","to","the","``","bounds","``","property","of","a","geometry",")",";","any","Z","values","present","in","input","geometries","are","ignored","when","querying","the","tree",".","Any","input","geometry","that","is","None","or","empty","will","never","match","geometries","in","the","tree",".","Parameters","--","--","--","--","--","geometry",":","Geometry","or","array_like","Input","geometries","to","query","the","tree","and","filter","results","using","the","optional","predicate",".","predicate",":","{","None",",","'intersects","'",",","'within","'",",","'contains","'",",","'overlaps","'",",","'crosses","'",",","'touches","'",",","'covers","'",",","'covered_by","'",",","'contains_properly","'",",","'dwithin","'","}",",","optional","The","predicate","to","use","for","testing","geometries","from","the","tree","that","are","within","the","input","geometry","'s","bounding","box",".","distance",":","number","or","array_like",",","optional","Distances","around","each","input","geometry","within","which","to","query","the","tree","for","the","'dwithin","'","predicate",".","If","array_like",",","shape","must","be","broadcastable","to","shape","of","geometry",".","Required","if","predicate='dwithin","'",".","Returns","--","--","--","-","ndarray","with","shape","(","n",",",")","if","geometry","is","a","scalar","Contains","tree","geometry","indices",".","OR","ndarray","with","shape","(","2",",","n",")","if","geometry","is","an","array_like","The","first","subarray","contains","input","geometry","indices",".","The","second","subarray","contains","tree","geometry","indices",".","Examples","--","--","--","--",">",">",">","from","shapely","import","box",",","Point",">",">",">","import","numpy","as","np",">",">",">","points","=","[","Point","(","0",",","0",")",",","Point","(","1",",","1",")",",","Point","(","2,2",")",",","Point","(","3",",","3",")","]",">",">",">","tree","=","STRtree","(","points",")","Query","the","tree","using","a","scalar","geometry",":",">",">",">","indices","=","tree.query","(","box","(","0",",","0",",","1",",","1",")",")",">",">",">","indices.tolist","(",")","[","0",",","1","]","Query","using","an","array","of","geometries",":",">",">",">","boxes","=","np.array","(","[","box","(","0",",","0",",","1",",","1",")",",","box","(","2",",","2",",","3",",","3",")","]",")",">",">",">","arr_indices","=","tree.query","(","boxes",")",">",">",">","arr_indices.tolist","(",")","[","[","0",",","0",",","1",",","1","]",",","[","0",",","1",",","2",",","3","]","]","Or","transpose","to","get","all","pairs","of","input","and","tree","indices",":",">",">",">","arr_indices.T.tolist","(",")","[","[","0",",","0","]",",","[","0",",","1","]",",","[","1",",","2","]",",","[","1",",","3","]","]","Retrieve","the","tree","geometries","by","results","of","query",":",">",">",">","tree.geometries.take","(","indices",")",".tolist","(",")","[","<","POINT","(","0","0",")",">",",","<","POINT","(","1","1",")",">","]","Retrieve","all","pairs","of","input","and","tree","geometries",":",">",">",">","np.array","(","[","boxes.take","(","arr_indices","[","0","]",")",",","tree.geometries.take","(","arr_indices","[","1","]",")","]",")",".T.tolist","(",")","[","[","<","POLYGON","(","(","1","0",",","1","1",",","0","1",",","0","0",",","1","0",")",")",">",",","<","POINT","(","0","0",")",">","]",",","[","<","POLYGON","(","(","1","0",",","1","1",",","0","1",",","0","0",",","1","0",")",")",">",",","<","POINT","(","1","1",")",">","]",",","[","<","POLYGON","(","(","3","2",",","3","3",",","2","3",",","2","2",",","3","2",")",")",">",",","<","POINT","(","2","2",")",">","]",",","[","<","POLYGON","(","(","3","2",",","3","3",",","2","3",",","2","2",",","3","2",")",")",">",",","<","POINT","(","3","3",")",">","]","]","Query","using","a","predicate",":",">",">",">","tree","=","STRtree","(","[","box","(","0",",","0",",","0.5",",","0.5",")",",","box","(","0.5",",","0.5",",","1",",","1",")",",","box","(","1",",","1",",","2",",","2",")","]",")",">",">",">","tree.query","(","box","(","0",",","0",",","1",",","1",")",",","predicate=","''","contains","''",")",".tolist","(",")","[","0",",","1","]",">",">",">","tree.query","(","Point","(","0.75",",","0.75",")",",","predicate=","''","dwithin","''",",","distance=0.5",")",".tolist","(",")","[","0",",","1",",","2","]",">",">",">","tree.query","(","boxes",",","predicate=","''","contains","''",")",".tolist","(",")","[","[","0",",","0","]",",","[","0",",","1","]","]",">",">",">","tree.query","(","boxes",",","predicate=","''","dwithin","''",",","distance=0.5",")",".tolist","(",")","[","[","0",",","0",",","0",",","1","]",",","[","0",",","1",",","2",",","2","]","]","Retrieve","custom","items","associated","with","tree","geometries","(","records","can","be","in","whatever","data","structure","so","long","as","geometries","and","custom","data","can","be","extracted","into","arrays","of","the","same","length","and","order",")",":",">",">",">","records","=","[","...","{","``","geometry","''",":","Point","(","0",",","0",")",",","``","value","''",":","``","A","''","}",",","...","{","``","geometry","''",":","Point","(","2",",","2",")",",","``","value","''",":","``","B","''","}","...","]",">",">",">","tree","=","STRtree","(","[","record","[","``","geometry","''","]","for","record","in","records","]",")",">",">",">","items","=","np.array","(","[","record","[","``","value","''","]","for","record","in","records","]",")",">",">",">","items.take","(","tree.query","(","box","(","0",",","0",",","1",",","1",")",")",")",".tolist","(",")","[","'","A","'","]","Notes","--","--","-","In","the","context","of","a","spatial","join",",","input","geometries","are","the","``","left","''","geometries","that","determine","the","order","of","the","results",",","and","tree","geometries","are","``","right","''","geometries","that","are","joined","against","the","left","geometries",".","This","effectively","performs","an","inner","join",",","where","only","those","combinations","of","geometries","that","can","be","joined","based","on","overlapping","bounding","boxes","or","optional","predicate","are","returned","."]
code: def query(self, geometry, predicate=None, distance=None):
      """
          Return the integer indices of all combinations of each input geometry
          and tree geometries where the bounding box of each input geometry
          intersects the bounding box of a tree geometry.
  
          If the input geometry is a scalar, this returns an array of shape (n, ) with
          the indices of the matching tree geometries.  If the input geometry is an
          array_like, this returns an array with shape (2,n) where the subarrays
          correspond to the indices of the input geometries and indices of the
          tree geometries associated with each.  To generate an array of pairs of
          input geometry index and tree geometry index, simply transpose the
          result.
  
          If a predicate is provided, the tree geometries are first queried based
          on the bounding box of the input geometry and then are further filtered
          to those that meet the predicate when comparing the input geometry to
          the tree geometry:
          predicate(geometry, tree_geometry)
  
          The 'dwithin' predicate requires GEOS >= 3.10.
  
          Bounding boxes are limited to two dimensions and are axis-aligned
          (equivalent to the ``bounds`` property of a geometry); any Z values
          present in input geometries are ignored when querying the tree.
  
          Any input geometry that is None or empty will never match geometries in
          the tree.
  
          Parameters
          ----------
          geometry : Geometry or array_like
              Input geometries to query the tree and filter results using the
              optional predicate.
          predicate : {None, 'intersects', 'within', 'contains', 'overlaps', 'crosses',\
  'touches', 'covers', 'covered_by', 'contains_properly', 'dwithin'}, optional
              The predicate to use for testing geometries from the tree
              that are within the input geometry's bounding box.
          distance : number or array_like, optional
              Distances around each input geometry within which to query the tree
              for the 'dwithin' predicate.  If array_like, shape must be
              broadcastable to shape of geometry.  Required if predicate='dwithin'.
  
          Returns
          -------
          ndarray with shape (n,) if geometry is a scalar
              Contains tree geometry indices.
  
          OR
  
          ndarray with shape (2, n) if geometry is an array_like
              The first subarray contains input geometry indices.
              The second subarray contains tree geometry indices.
  
          Examples
          --------
          >>> from shapely import box, Point
          >>> import numpy as np
          >>> points = [Point(0, 0), Point(1, 1), Point(2,2), Point(3, 3)]
          >>> tree = STRtree(points)
  
          Query the tree using a scalar geometry:
  
          >>> indices = tree.query(box(0, 0, 1, 1))
          >>> indices.tolist()
          [0, 1]
  
          Query using an array of geometries:
  
          >>> boxes = np.array([box(0, 0, 1, 1), box(2, 2, 3, 3)])
          >>> arr_indices = tree.query(boxes)
          >>> arr_indices.tolist()
          [[0, 0, 1, 1], [0, 1, 2, 3]]
  
          Or transpose to get all pairs of input and tree indices:
  
          >>> arr_indices.T.tolist()
          [[0, 0], [0, 1], [1, 2], [1, 3]]
  
          Retrieve the tree geometries by results of query:
  
          >>> tree.geometries.take(indices).tolist()
          [<POINT (0 0)>, <POINT (1 1)>]
  
          Retrieve all pairs of input and tree geometries:
  
          >>> np.array([boxes.take(arr_indices[0]),\
  tree.geometries.take(arr_indices[1])]).T.tolist()
          [[<POLYGON ((1 0, 1 1, 0 1, 0 0, 1 0))>, <POINT (0 0)>],
           [<POLYGON ((1 0, 1 1, 0 1, 0 0, 1 0))>, <POINT (1 1)>],
           [<POLYGON ((3 2, 3 3, 2 3, 2 2, 3 2))>, <POINT (2 2)>],
           [<POLYGON ((3 2, 3 3, 2 3, 2 2, 3 2))>, <POINT (3 3)>]]
  
          Query using a predicate:
  
          >>> tree = STRtree([box(0, 0, 0.5, 0.5), box(0.5, 0.5, 1, 1), box(1, 1, 2, 2)])
          >>> tree.query(box(0, 0, 1, 1), predicate="contains").tolist()
          [0, 1]
          >>> tree.query(Point(0.75, 0.75), predicate="dwithin", distance=0.5).tolist()
          [0, 1, 2]
  
          >>> tree.query(boxes, predicate="contains").tolist()
          [[0, 0], [0, 1]]
          >>> tree.query(boxes, predicate="dwithin", distance=0.5).tolist()
          [[0, 0, 0, 1], [0, 1, 2, 2]]
  
          Retrieve custom items associated with tree geometries (records can
          be in whatever data structure so long as geometries and custom data
          can be extracted into arrays of the same length and order):
  
          >>> records = [
          ...     {"geometry": Point(0, 0), "value": "A"},
          ...     {"geometry": Point(2, 2), "value": "B"}
          ... ]
          >>> tree = STRtree([record["geometry"] for record in records])
          >>> items = np.array([record["value"] for record in records])
          >>> items.take(tree.query(box(0, 0, 1, 1))).tolist()
          ['A']
  
  
          Notes
          -----
          In the context of a spatial join, input geometries are the "left"
          geometries that determine the order of the results, and tree geometries
          are "right" geometries that are joined against the left geometries. This
          effectively performs an inner join, where only those combinations of
          geometries that can be joined based on overlapping bounding boxes or
          optional predicate are returned.
          """
  
      geometry = np.asarray(geometry)
      is_scalar = False
      if geometry.ndim == 0:
          geometry = np.expand_dims(geometry, 0)
          is_scalar = True
  
      if predicate is None:
          indices = self._tree.query(geometry, 0)
          return indices[1] if is_scalar else indices
  
      # Requires GEOS >= 3.10
      elif predicate == "dwithin":
          if lib.geos_version < (3, 10, 0):
              raise UnsupportedGEOSVersionError(
                  "dwithin predicate requires GEOS >= 3.10"
              )
          if distance is None:
              raise ValueError(
                  "distance parameter must be provided for dwithin predicate"
              )
          distance = np.asarray(distance, dtype="float64")
          if distance.ndim > 1:
              raise ValueError(
                  "Distance array should be one dimensional"
              )
  
          try:
              distance = np.broadcast_to(distance, geometry.shape)
          except ValueError:
              raise ValueError(
                  "Could not broadcast distance to match geometry"
              )
  
          indices = self._tree.dwithin(geometry, distance)
          return indices[1] if is_scalar else indices
  
      predicate = BinaryPredicate.get_value(predicate)
      indices = self._tree.query(geometry, predicate)
      return indices[1] if is_scalar else indices
  
file_path: shapely/shapely/strtree.py
imports: from typing import Any, Iterable, Union
  import numpy
  from shapely import lib
  from shapely._enum import ParamEnum
  from shapely.decorators import UnsupportedGEOSVersionError
  from shapely.geometry.base import BaseGeometry
  from shapely.predicates import is_empty, is_missing
label_desc: Use image node_id 5 for calling the STRtree obj's underlying member method code with example usage: obj.query(geometry, predicate, distance) and returns: unknown, unknown, unknown