Polygon, line and point algorithms.
Tip
Clip raster grid by 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 geotransform_to_axes().
If multiple polygons overlap, the one first encountered will be used.
| Parameters: |
|
|---|---|
| Returns: | Tuple of (points_covered, grid_covered). points_covered = List of tuple (points, values) - points covered and its value per polygon. values_covered = grid_data that coincide with the polygons |
Clip line segments by polygon
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
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]]])
The assumptions listed in separate_points_by_polygon apply
Output line segments are listed as separate lines i.e. not joined
Clip multiple lines by polygon
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
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
Clip multiple lines by multiple polygons
where pi and qi are point coordinates (x, y).
polygons: list of polygons, each an array of vertices
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.
Note
If multiple polygons overlap, the one first encountered will be used.
Generate random points in polygon bounding box
Separate a list of points into two sets inside and outside a polygon
| Parameters: |
|
|---|
inside: Indices of points inside the polygon
outside: Indices of points outside the polygon
See separate_points_by_polygon for more documentation
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
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.
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]
Determine if one point is inside a polygon
See inside_polygon for more details
Determine if one point is outside a polygon
See outside_polygon for more details
Join adjacent line segments
Convert dictionary of lines to list of Nx2 arrays
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
Determine if a point is on a line segment
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
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()
Convert polygon to segments structure suitable for use in intersection
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
Populate given polygon with uniformly distributed points.
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
Determine whether points are inside or outside a polygon.
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
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
falling inside the polygon
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
Algorithm is based on work by Darel Finley, http://www.alienryderflex.com/polygon/