### Navigation

- index
- modules
- next
- previous
- Home »
- Contents »
- InaSAFE’s API documentation »
- Package::safe »
- Package::safe.common »

# Module: safe.common.polygon

Polygon, line and point algorithms.

Tip

The main public functions are:
  separate_points_by_polygon: Fundamental clipper intersection: Determine intersections of lines
Some more specific or helper functions include:
  inside_polygon is_inside_polygon outside_polygon is_outside_polygon point_on_line

`safe.common.polygon.``clip_grid_by_polygons`(A, geotransform, polygons, inner_rings=None)

  Clip raster grid by polygon

  Input

    A: MxN array of grid points geotransform: 6-tuple used to locate A geographically

    > (top left x, w-e pixel resolution, rotation,
    >   top left y, rotation, n-s pixel resolution)

    polygons: list of polygons, each an array of vertices inner_rings: list of list of holes - each an array of vertices

  Output
    points_covered: List of (points, values) - one per input polygon.

  Implementing algorithm suggested in https://github.com/AIFDR/inasafe/issues/91#issuecomment-7025120

  Note: Grid points are considered to be pixel-registered which means

    that each point represents the center of its grid cell. The required half cell shifts are taken care of by the function geotransform2axes

    If multiple polygons overlap, the one first encountered will be used

`safe.common.polygon.``clip_line_by_polygon`(line, polygon, closed=True, polygon_bbox=None, check_input=True)

  Clip line segments by polygon

  Input
    line: Sequence of line nodes: [[x0, y0], [x1, y1], ...] or
      the equivalent Nx2 numpy array

    polygon: list or Nx2 array of polygon vertices closed: (optional) determine whether points on boundary should be regarded as belonging to the polygon (closed = True) or not (closed = False) - False is not recommended here polygon_bbox: Provide bounding box around polygon if known.

    > This is a small optimisation

    check_input: Allows faster execution if set to False

  Outputs

    inside_lines: Clipped lines that are inside polygon outside_lines: Clipped lines that are outside polygon

    Both outputs lines take the form of lists of Nx2 numpy arrays, i.e. each line is an array of multiple segments

  Example:

  > U = [[0,0], [1,0], [1,1], [0,1]] # Unit square

  > # Simple horizontal fully intersecting line line = [[-1, 0.5], [2, 0.5]]

  > inside_line_segments, outside_line_segments = clip_line_by_polygon(line, polygon)

  > print numpy.allclose(inside_line_segments,
  >   [[[0, 0.5], [1, 0.5]]])
  > print numpy.allclose(outside_line_segments,
  >   [[[-1, 0.5], [0, 0.5]],
  >     [[1, 0.5], [2, 0.5]]])

  Remarks:

    The assumptions listed in separate_points_by_polygon apply

    Output line segments are listed as separate lines i.e. not joined

`safe.common.polygon.``clip_lines_by_polygon`(lines, polygon, closed=True, check_input=True)

  Clip multiple lines by polygon

  Input
    lines: Sequence of polylines: [[p0, p1, ...], [q0, q1, ...], ...]
      where pi and qi are point coordinates (x, y).

    polygon: list or Nx2 array of polygon vertices closed: (optional) determine whether points on boundary should be

    > regarded as belonging to the polygon (closed = True) or not (closed = False) - False is not recommended here This parameter can also be None in which case it is undefined whether a line on the boundary will fall inside or outside. This will make the algorithm about 20% faster.

    check_input: Allows faster execution if set to False

  Output

    inside_lines: Dictionary of lines that are inside polygon outside_lines: Dictionary of lines that are outside polygon

    Elements in output dictionaries can be a list of multiple lines. One line is a numpy array of vertices.

    Both output dictionaries use the indices of the original line as keys. This makes it possible to track which line the new clipped lines come from, if one e.g. wants to assign the original attribute values to clipped lines.

  This is a wrapper around clip_line_by_polygon

`safe.common.polygon.``clip_lines_by_polygons`(lines, polygons, check_input=True, closed=True)

  Clip multiple lines by multiple polygons

  Args:
    lines: Sequence of polylines: [[p0, p1, ...], [q0, q1, ...], ...]
      where pi and qi are point coordinates (x, y).

    polygons: list of polygons, each an array of vertices closed: optional parameter to determine whether lines that fall on

    > an polygon boundary should be considered to be inside (closed=True), outside (closed=False) or undetermined (closed=None). The latter case will speed the algorithm up but lines on boundaries may or may not be deemed to fall inside the polygon and so will be indeterministic

  Returns:
    lines_covered: List of polylines inside a polygon
      - one per input polygon.

  If multiple polygons overlap, the one first encountered will be used

`safe.common.polygon.``generate_random_points_in_bbox`(polygon, N, seed=None)

  Generate random points in polygon bounding box

`safe.common.polygon.``in_and_outside_polygon`(points, polygon, closed=True, holes=None, check_input=True)

  Separate a list of points into two sets inside and outside a polygon

  Input

    points: (tuple, list or array) of coordinates polygon: list or Nx2 array of polygon vertices closed: Set to True if points on boundary are considered

    > to be ‘inside’ polygon

    holes: list of polygons representing holes. Points inside either of
      these are considered outside polygon
  Output
    inside: Indices of points inside the polygon outside: Indices of points outside the polygon

  See separate_points_by_polygon for more documentation

`safe.common.polygon.``inside_polygon`(points, polygon, closed=True, holes=None, check_input=True)

  Determine points inside a polygon

  Functions inside_polygon and outside_polygon have been defined in terms of separate_by_polygon which will put all inside indices in the first part of the indices array and outside indices in the last

  See separate_points_by_polygon for documentation

  points and polygon can be a geospatial instance, a list or a numeric array

  holes: list of polygons representing holes. Points inside either of these are not considered inside_polygon

`safe.common.polygon.``intersection`(line0, line1)

  Returns intersecting point between two line segments.

  If the lines are parallel or coincide partly (i.e. share a common segment), they are considered to not intersect.

  Inputs:
    line0: A simple line segment defined by two end points:
      [[x0, y0], [x1, y1]]
    line1: A collection of line segments vectorised following the format
      line[0, 0, :] = x2 line[0, 1, :] = y2 line[1, 0, :] = x3 line[1, 1, :] = y3
  Output:
    intersections: Nx2 array with intersection points or nan
      (in case of no intersection) If line1 consisted of just one line, None is returned for backwards compatibility

  Notes

  A vectorised input line can be constructed either as list: line1 = [[[0, 24, 0, 15], # x2

  > > [12, 0, 24, 0]], # y2

  > [[24, 0, 0, 5], # x3
  >   [0, 12, 12, 15]]] # y3

  or as an array

  line1 = numpy.zeros(16).reshape(2, 2, 4) # Four segments line1[0, 0, :] = [0, 24, 0, 15] # x2 line1[0, 1, :] = [12, 0, 24, 0] # y2 line1[1, 0, :] = [24, 0, 0, 5] # x3 line1[1, 1, :] = [0, 12, 12, 15] # y3

  To select array of intersections from result, use the following idiom:

  value = intersection(line0, line1) mask = -numpy.isnan(value[:, 0]) v = value[mask]

`safe.common.polygon.``is_inside_polygon`(point, polygon, closed=True)

  Determine if one point is inside a polygon

  See inside_polygon for more details

`safe.common.polygon.``is_outside_polygon`(point, polygon, closed=True)

  Determine if one point is outside a polygon

  See outside_polygon for more details

`safe.common.polygon.``join_line_segments`(segments, rtol=1e-12, atol=1e-12)

  Join adjacent line segments

  Input
    segments: List of distinct line segments [[p0, p1], [p2, p3], ...] rtol, atol: Optional tolerances passed on to numpy.allclose
  Output
    list of Nx2 numpy arrays each corresponding to a continuous line formed from consecutive segments

`safe.common.polygon.``line_dictionary_to_geometry`(D)

  Convert dictionary of lines to list of Nx2 arrays

  Input
    D: Dictionary of lines e.g. as produced by clip_lines_by_polygon
  Output:
    List of Nx2 arrays suitable as geometry input to class Vector

`safe.common.polygon.``outside_polygon`(points, polygon, closed=True, holes=None, check_input=True)

  Determine points outside a polygon

  Functions inside_polygon and outside_polygon have been defined in terms of separate_by_polygon which will put all inside indices in the first part of the indices array and outside indices in the last

  See separate_points_by_polygon for documentation

  holes: list of polygons representing holes. Points inside either of
    these are considered outside polygon

`safe.common.polygon.``point_on_line`(points, line, rtol=1e-05, atol=1e-08, check_input=True)

  Determine if a point is on a line segment

  Input
    points: Coordinates of either
      - one point given by sequence [x, y]
      - multiple points given by list of points or Nx2 array
    line: Endpoint coordinates [[x0, y0], [x1, y1]] or
      the equivalent 2x2 numeric array with each row corresponding to a point.

    rtol: Relative error for how close a point must be to be accepted atol: Absolute error for how close a point must be to be accepted

  Output
    True or False

  Notes

  Line can be degenerate and function still works to discern coinciding points from non-coinciding.

  Tolerances rtol and atol are used with numpy.allclose()

`safe.common.polygon.``polygon2segments`(polygon)

  Convert polygon to segments structure suitable for use in intersection

  Args:
    polygon: Nx2 array of polygon vertices
  Returns:

    A collection of line segments (x0, y0) -> (x1, y1) vectorised following the format

    > line[0, 0, :] = x0 line[0, 1, :] = y0 line[1, 0, :] = x1 line[1, 1, :] = y1

`safe.common.polygon.``populate_polygon`(polygon, number_of_points, seed=None, exclude=None)

  Populate given polygon with uniformly distributed points.

  Input:

    polygon - list of vertices of polygon number_of_points - (optional) number of points seed - seed for random number generator (default=None) exclude - list of polygons (inside main polygon) from where points

    > should be excluded

  Output:
    points - list of points inside polygon
  Examples:
    populate_polygon( [[0,0], [1,0], [1,1], [0,1]], 5 ) will return five randomly selected points inside the unit square

`safe.common.polygon.``separate_points_by_polygon`(points, polygon, polygon_bbox=None, closed=True, check_input=True, use_numpy=True)

  Determine whether points are inside or outside a polygon.

  Args:

    - points: Tuple of (x, y) coordinates, or list of tuples

    - polygon: list or Nx2 array of polygon vertices

    - polygon_bbox: (optional) bounding box for polygon

    - closed: (optional) determine whether points on boundary should be

        regarded as belonging to the polygon (closed = True) or not (closed = False). If None, boundary is left undefined, i.e. some points on boundary may be deemed to be inside while others may be deemed to be outside. This options makes the code faster.

    - check_input: Allows faster execution if set to False

    - use_numpy: Use the fast numpy implementation

  Returns:
    - indices_inside_polygon: array of indices of points

        falling inside the polygon

    - indices_outside_polygon: array of indices of points

        falling outside the polygon

  Raises: A generic Exception is raised for unexpected input.

  Example:

  > U = [[0,0], [1,0], [1,1], [0,1]] # Unit square separate_points_by_polygon( [[0.5, 0.5], [1, -0.5], [0.3, 0.2]], U)

  > will return the indices [0, 2, 1] and count == 2 as only the first and the last point are inside the unit square

  Remarks:
    The vertices may be listed clockwise or counterclockwise and the first point may optionally be repeated. Polygons do not need to be convex. Polygons can have holes in them and points inside a hole is regarded as being outside the polygon.

  Algorithm is based on work by Darel Finley, http://www.alienryderflex.com/polygon/

This module forms part of the InaSAFE tool.

### Navigation

- index
- modules
- next
- previous
- Home »
- Contents »
- InaSAFE’s API documentation »
- Package::safe »
- Package::safe.common »