Overview

The high level modules contain the functions to create and manipulate regions and moving regions. For example, functions to generate regions and set operations over regions exist in these libraries.

The utility modules contain functions that, for the most part, pertain to lists of line segments and halfsegments. For example, line segment intersection code exists there. More advanced utilities, such as functions that will identify cycles in regions, etc., are also there

The example module contains some example code using the modules.

High Level Modules

Region Module

High level functions for regions. Region creation, set operations, etc.

pyspatiotemporalgeom.region.createCountPartition(segList, laList, lbList)[source]

NOTE. The output of this function is automatically written to a file. see the source code...

Creates a spatial partition from a set of regions. Each resulting segment will also have a label that indicates how many region interiors (from the original set of regions) lies above and below the segment. So, we essentially get a heat map of vector regions. Each segment in a cycle in the resulting partition will have the same interior label (for the interior of the cycle), since that cycle represents the area covered by a fixed numeber of input regions.

ASSUMPTIONS

  1. segList contains line segments representing a set of well-formed regions
  2. laList and lbList are parallel arrays with segList indicating the labels of their associated segment.
  3. laList and lbList contain values of 1 and -1 (1 for interior, -1 for exterior)
  4. See the following paper for details: M. McKenney, B. Olsen, “Algorithms for Fundamental Spatial Aggregate Operations Over Regions,” BIGSPATIAL at 21st ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, November 2013, Orlando, FL, USA.

input:

segList: A list of line segments representing a SET of well formed regions. To generate this set from a 2 hseg representations, you would extract the segs from each hseg list, and then concatenate them into a single list.

laList: a list of label values. The first value corresponds to the above label of the first segment in the seg list, the second corresponds to the second segment in the segList, etc. MUST HAVE A VALUE OF -1 (exterior) or 1 (interior).

lbList: Similar to laList, but representing the label (whether the interior or extior of the associated region) lies below the segment. MUST HAVE A VALUE OF -1 (exterior) or 1 (interior).

pyspatiotemporalgeom.region.createRegionFavorLargeCyclesFromSegs(segs)[source]

Behavior is similar to createRegionFromSegs, however, createRegionFromSegs will tend to return many smaller cycles if given input with many intersecting segments. This function will tend to return fewer larger cycles. One side effect of this is that no two cycles will share an endpoint in the resulting region returned from this function. In other words, all cycles are disjoint, although cycles may be inside other cycles.

pyspatiotemporalgeom.region.createRegionFromSegs(segs)[source]

Constructs a well formed region from an input set line segments.

input:

segs: a list of line segments in the format [((x1,y1),(x2,y2)),((x3,y3),(x4,y4)),...] Intersecting segments will be broken at intersection points. If not cycle is present, no region will be returned.

returns:

hsegs: an ordered list of half segments with valid labels.

A half segment is a tuple with the following:
((x,y)(x,y), labelAbove, labelBelow)

labels are integral values

an interior label will be positive. An exterior label will be -1. The side of the hseg on which the interior (exterior) of the region lies will have an interior (exterior) label.

hsegs will be ordered in half segment order

Each cycle in hsegs will have its own unique label number

pyspatiotemporalgeom.region.difference(hsegs1, hsegs2)[source]

NON-symmetric difference. for R1 and R2, defined as R1 - (R1 cap R2).

Regions are asssumed to have valid labelling. this function will return a properly labeled region

input:

hsegs1: a well formed and properly labeled region.

hsegs2: a well formed and properly labeled region.

output:

an hseg list consisiting of the difference of the input regions.

pyspatiotemporalgeom.region.getOuterCycle(hsegs)[source]

extracts the leftmost outer cycle from a region (the first one encountered in halfsegment order)

input:

hsegs: a well formed region represented as a list of halfsegments.

output:

hseg list: a well formed region represented as a list of halfsegments. The region will contain a single cycle and no holes (i.e., a simple region).

pyspatiotemporalgeom.region.getRandomIntegerRegion(numRandomSegsToGenerate=50, percentOfSegsToRemove=0.05)[source]

The output of this function will have INTEGER coordinates. This constraint greatly increases the computation time of this function. In general, the non-integer version is much faster, and is fine for most uses.

generates a region from random segments. input:

numRandomSegsToGenerate: the number of random segs to generate. The actual region
will have many fewer segs than this. Higher numbers will typically generate more complex regions. The region will be constructed by intersecting the reandom segs, and finding a region among the resulting segs.
percentOfSegsToRemove: Once random segments are generated and intersected such that all
segments only intersect at endpoints, some segments will be removed at random. This parameter indicates the percentage of overall segs that will be removed. A higher number typically causes regions to have less regular shapes. Note that a high percentage may require a larger number of random segs to be generated.

returns:

hsegs: an ordered list of half segments with valid labels.

A half segment is a tuple with the following:
((x,y)(x,y), labelAbove, labelBelow)

labels are integral values

an interior label will be positive. An exterior label will be -1. The side of the hseg on which the interior (exterior) of the region lies will have an interior (exterior) label.

hsegs will be ordered in half segment order

Each cycle in hsegs will have its own unique label number

pyspatiotemporalgeom.region.getRandomRegion(numRandomSegsToGenerate=50, minBound=0, maxBound=10000, percentOfSegsToRemove=0.05)[source]

generates a region from random segments. input:

numRandomSegsToGenerate: the number of random segs to generate. The actual region
will have many fewer segs than this. Higher numbers will typically generate more complex regions. The region will be constructed by intersecting the reandom segs, and finding a region among the resulting segs.
percentOfSegsToRemove: Once random segments are generated and intersected such that all
segments only intersect at endpoints, some segments will be removed at random. This parameter indicates the percentage of overall segs that will be removed. A higher number typically causes regions to have less regular shapes. Note that a high percentage may require a larger number of random segs to be generated.

returns:

hsegs: an ordered list of half segments with valid labels.

A half segment is a tuple with the following:
((x,y)(x,y), labelAbove, labelBelow)

labels are integral values

an interior label will be positive. An exterior label will be -1. The side of the hseg on which the interior (exterior) of the region lies will have an interior (exterior) label.

hsegs will be ordered in half segment order

Each cycle in hsegs will have its own unique label number

pyspatiotemporalgeom.region.giveUniqueLabelToEachCycle(hsegs, getOnlyOuterCycle=False)[source]

takes an input region, and alters its interior labels such that each individual cycle in the region has its own unique interior label number. Cycles that share a point (cycles that touch at a point) also have their own cycle numbers. If the second argument is true, only the leftmost outer cycle will be returned

input:

hsegs: a well formed region as a list of halfsegments

getOnlyOuterCycle: default value = False. If set to True, will return only a single cycle; the leftmost outer cycle in the region

output:

hseg list: a well-formed region represented as a list of halfsegments. Each minimal cycle will have a unique interior label number,

pyspatiotemporalgeom.region.intersection(hsegs1, hsegs2)[source]

Assumes that hsegs1 and hsegs2 are valid regions, created with def createRegionFromSegs.

regions are assumed to have valid labelling.

This function will relabel them to compute the intersction

input:

hsegs1: a well formed and properly labeled region.

hsegs2: a well formed and properly labeled region.

output:

an hseg list consisiting of the intersection of the input regions.

pyspatiotemporalgeom.region.pointInPolygon(x, y, poly)[source]

Point in polygon test. Works for complex regions (multiple faces, holes, faces in holes, etc.)

Input:

  • x: the X value of the point to be tested
  • y: the Y valu of the point to be tested
  • poly: a list of 2D segments in the usual format: ((x1,y1),(x2,y2))

Output:

  • boolean value. True if the point is in the polygon OR if the point is on the boundary. False otherwise

Note, this may be sensitive to floating poitn rounding errors, might need to allow some tolerance in the left hand turn test.

pyspatiotemporalgeom.region.union(hsegs1, hsegs2)[source]

Computes the union of two well formed regions.

Assumes that hsegs1 and hsegs2 are valid regions, for instance, they have been created with def createRegionFromSegs.

regions are assumed to have valid labelling. This function will relabel them to compute the union

input:

hsegs1: a well formed and properly labeled region.

hsegs2: a well formed and properly labeled region.

output:

an hseg list consisiting of the union of the input regions.

pyspatiotemporalgeom.region.writeRegionToFile(theRegion, theFileName)[source]

Write the region to a file.

file will be a text file. Floating point rounding WILL happen in the float to text conversion. Only use this if floating point rounding is OK (for instance, for visualizing the region).

The resulting file will have 1 halfsegment per line. Both left and right halfsegments are written. The file will have the following format:

x1 y1 x2 y2 x3 y3 x4 y4 la lb ...

input:

theRegion: A list of halfsegments

theFilename: the name of the file that will be written.

pyspatiotemporalgeom.region.writeRegionToHexFile(theRegion, theFileName)[source]

Write the region to a file in HEXADECIMAL FORMAT. Meant to be a more portable file with a format that is easy to read and process in any programming language. NOTE that endianness is NOT checked for!

file will be a text file. Floating point values are represented as hexadecimal, and thus, are represented EXACTLY in floating point format. Use this if you need the exact floating point values.

The resulting file will have 1 halfsegment per line. Both left and right halfsegments are written. The file will have the following format (except each floating point number will be in hexadecimal format labels are just represented as text):

x1 y1 x2 y2 x3 y3 x4 y4 la lb ...

input:

theRegion: A list of halfsegments

theFilename: the name of the file that will be written.

Interval Region Module

High level functions for interval regions.

intervalRegion.py

Code to define and manipulate interval regions

pyspatiotemporalgeom.intervalRegion.findWhatLineIntersectionPointBelongsTo(points, segs)[source]

Figures out what points come from what segments

Input:

  • points: List of points to check
  • segs: List of segments

Output:

  • a list of points that pass the collinear value tests
pyspatiotemporalgeom.intervalRegion.getPointToTimeDictionary(tris, intersectionPointList, DEBUG=False)[source]

Appends time with corresponding points and returns the points as a dictionary (if the points pass the polygon test)

Input:

  • tris:
  • intersectionPointList: List of intersection points

Output:

  • a dictionary of intersection points with times
pyspatiotemporalgeom.intervalRegion.getRegionAtTime(intervalRegion, time)[source]

Extract a region from an interval region.

Input:

Output:

  • a list of segments where segments have the type: ((x1,y1),(x2,y2)). The segments will form a valid region.
pyspatiotemporalgeom.intervalRegion.getTemporalCoverageGeometriesAndTimes(intervalRegion, endPoints=None)[source]

Compute temporal coverage geometries and their associated times. Currently, only constructs point geomoetries, but this will change in future releases.

See the following paper for details:

  1. McKenney, R. Frye, Z. Benchly, and L. Maughan, “Temporal Coverage Aggregates Over Moving Region Streams.” IWGS at 22nd ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, November 2014, Dallas, TX, USA f

Input:

Output:

A dict() mapping points to a list of durations that the particular point is covered by the interval region (if the duration is non-zero)

pyspatiotemporalgeom.intervalRegion.interpolateRegions(region1, region2, startTime, endTime, noTriIntersectionChecks=False)[source]

This is just a wrapper that calls pyspatiotemporalgeom.utilities.regionInterpolater.interpolate(). The documentation for that function is copied here:

This is where the magic happens. Create an interpolation between two well-formed regions over a time interval (defined by startTime and endTime) such that at every instant within that time interval, the region resulting from the interpolation at that instant conforms to the type definition of complex regions as defined in [1]. Note that the various region generators and region creation functions int he region.py file create well formed regions according to [1]. In otherwords, the moving region resulting from this function conforms to the type definition of moving regions in [2].

This function is an extension of the algorithm in [3] to handle both simple (1 simple cycle with no holes) regions and complex regions.

[1] Markus Schneider and Thomas Behr. 2006. Topological relationships between complex spatial objects. ACM Trans. Database Syst. 31, 1 (March 2006), 39-81. DOI=10.1145/1132863.1132865 http://doi.acm.org/10.1145/1132863.1132865

[2] Ralf Hartmut Guting, Michael H. Bohlen, Martin Erwig, Christian S. Jensen, Nikos A. Lorentzos, Markus Schneider, and Michalis Vazirgiannis. 2000. A foundation for representing and querying moving objects. ACM Trans. Database Syst. 25, 1 (March 2000), 1-42. DOI=10.1145/352958.352963 http://doi.acm.org/10.1145/352958.352963

[3] Mark McKenney and James Webb. 2010. Extracting moving regions from spatial data. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS ‘10). ACM, New York, NY, USA, 438-441. DOI=10.1145/1869790.1869856 http://doi.acm.org/10.1145/1869790.1869856

Input:

  1. r1, r2: two well formed regions represented as lists of hlafsegments. Any of the region creation functions in region.py will do.
  2. startTime, endTime: two numbers defining a time interval. These numbers are used as the 3D dimension when extrapolating into 3D space.
  3. noTriIntersectionChecks. See paper [3]. The algorithm first creates an interpolation between the input regions. It is possible that the interpolation will result in a self-intersecting region at some point. The triangle/triangle intersection test is then performed. This test is very computationally intensive (especially for python) and can take a LONG time to compute. If you pass a True for this argument, the tri/tri intersection test is skipped, and the interpolation returned AS-IS (possibly with self-intersections). This makes the algorithm O(n \lg n) instead of O(n^2).

Output:

A 3-tuple. See [3]. The algorithm will create at MOST, 3 interval regions to describe the interpolation of r1 to r2 over the defined time interval. Not all 3 interval regions are always required, so 1 or 2 of the values in the tuple may be None, but a 3 tuple is ALWAYS returned. If the noTriIntersectionChecks argument is set to True, or the original interpolation succeeds, then the return value will look like this: (None, triList, None).

Any non-None value in the return tuple will be a list of trinagles describing the movinement of line segments in r1 as they travel across the defined interval to r2 (between intermediate states of r1 and r2 if necessary).

pyspatiotemporalgeom.intervalRegion.maxPointCoverage(points)[source]

This returns the point or points with the maximum coverage time.

Input:

  • points: the points to be checked

Output:

  • a list of points that cover the maximum coverage
pyspatiotemporalgeom.intervalRegion.minPointCoverage(points)[source]

This returns the point or points with the minimum coverage time.

Input:

  • points: the points to be checked

Output:

  • a list of points that cover the minimum coverage

Component Moving Region Module

High level functions for component moving regions. Includes the cIntervalRegion class.

pyspatiotemporalgeom.componentMovingRegion.assignFacesToFacesLinesPoints(intervalReg, faceS, faceD, lineD, pointD)[source]

given a component interval region that is set up with source and destination objects, map the faces in a source structural region resulting from a face list resulting from a set operation to faces, points, lines, in the destination structural region of the interval region

At the moment, we map a face to every other structure that shares its label. This needs to be addressed in the future.

Input:

intervalReg
An interval region with source and destination objects already created
faceS:
A 2 level dictionary of mapIDs->cycleID->listOfSegments. cycleID is just a temporary identifier. listOfSegments is a list of line segments that form a cycle. faceS pertains to the source structural region in an interval region
faceD:
Identical to faceS, but for the destination structural region in the interval regions
lineD:
Identical to faceD, but the list of segments defines a connected simple line.
pointD:
a Dictionary that maps mapIDs->listOfPoints. listOfPoints is a list of simple points that carry the mapID.
pyspatiotemporalgeom.componentMovingRegion.assignHolesToHolesLinesPoints(intervalReg, holeS, holeD, lineD, pointD)[source]

given a component interval region that is set up with source and destination objects, map the holes in a source structural region resulting from a hole list resulting from a set operation to holes, points, lines, in the destination structural region of the interval region

At the moment, we map a hole to every other structure that shares its label. This needs to be addressed in the future.

Input:

intervalReg
An interval region with source and destination objects already created
holeS:
A 2 level dictionary of mapIDs->cycleID->listOfSegments. cycleID is just a temporary identifier. listOfSegments is a list of line segments that form a cycle. holeS pertains to the source structural region in an interval region
holeD:
Identical to holeS, but for the destination structural region in the interval regions
lineD:
Identical to holeD, but the list of segments defines a connected simple line.
pointD:
a Dictionary that maps mapIDs->listOfPoints. listOfPoints is a list of simple points that carry the mapID.
pyspatiotemporalgeom.componentMovingRegion.assignLinesPointsToFaces(intervalReg, lineS, pointS, faceD)[source]

given a component interval region that is set up with source and destination objects, map the lines and points in a source structural region to faces in the destination region this is used with set operations

At the moment, we map a line/point to every face that shares its label. This needs to be addressed in the future.

Input:

intervalReg
An interval region with source and destination objects already created
lineS:
A 2 level dictionary of mapIDs->simpleLineID->listOfSegments. simpleLineID is just a temporary identifier. listOfSegments is a list of line segments that form a cycle. lineS pertains to the source structural region in an interval region
pointS:

a Dictionary that maps mapIDs->listOfPoints. listOfPoints is a list of simple points that carry the mapID.

faceD:
A 2 level dictionary of mapIDs->cycleID->listOfSegments. cycleID is just a temporary identifier. listOfSegments is a list of line segments that form a cycle. faceD pertains to the destination structural region in an interval region
pyspatiotemporalgeom.componentMovingRegion.assignLinesPointsToHoles(intervalReg, lineS, pointS, holeD)[source]

given a component interval region that is set up with source and destination objects, map the lines and points in a source structural region to holes in the destination region this is used with set operations

At the moment, we map a line/point to every hole that shares its label. This needs to be addressed in the future.

Input:

intervalReg
An interval region with source and destination objects already created
lineS:
A 2 level dictionary of mapIDs->simpleLineID->listOfSegments. simpleLineID is just a temporary identifier. listOfSegments is a list of line segments that form a cycle. lineS pertains to the source structural region in an interval region
pointS:
a Dictionary that maps mapIDs->listOfPoints. listOfPoints is a list of simple points that carry the mapID.
holeD:
A 2 level dictionary of mapIDs->cycleID->listOfSegments. cycleID is just a temporary identifier. listOfSegments is a list of line segments that form a cycle. holeD pertains to the destination structural region in an interval region
class pyspatiotemporalgeom.componentMovingRegion.cIntervalRegion[source]

A Component Interval Region describes the movement of a moving region over a single time interval. Thus, a CIR is defined as a pair of structural regions (the source and destination) respectively associated with a timestamp. Structures from the source are mapped to structured in the destination in order to represent how the components move across the interval. The region interpolator function is used to actually create the movement.

getMotionTriangles(returnSingleListOfAllTris=False)[source]

Return a list of motion triangles indicating the movement implied by the mapping of structures

NOTE: line and point mappings are not yet implemented

Input:

returnSingleListOfAllTris

if set to True, the function returns a single list of ALL motion triangles describing the motion of all structures in this interval region.

If set to False (the default), the function will return the motion triangles such that the triangles for each component are in thier own list. See the return type descripion

Returns:

If returnSingleListOfAllTris=True
A list of Triangles. Each triangle is a 3 tuple of 3D points: ((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)). Two points will always share a Z value (defining a segment in the plane) and will ALWAYS be the first 2 points in the triple (that is: z1 == z2).
If returnSingleListOfAllTris=True

A list of tuples where each tuple holds the ID of the component in the source region, the ID of the component in the destination region, and the triangles describing the motion of that component across the interval.

[(sID1, dID1, [((x1,y1,z1),(x2,y2,z2),(x3,y3,z3)), ... ]), ... ,(sIDN, dIDN, triangleList)]

where the first 2 Z values in each triangle are always equivalent (ie, they define a line segment in the X,Y plane).

getStructuralRegionAtTime(time)[source]

Exctract the structural region defined by this component interval region at time time.

Call the interpolator, get the triangles, extract the region from those triangles

Input:

time:
The time at which to extract the structural regions

Returns:

None:
If the time is outside the bounds of this interval regions
structural region:
otherwise
mapComponent(sourceComponentID, destComponentIDs)[source]

Add components to the component mapping in order to represent movement across the interval.

The function ensures that the component IDS exist in the source and dest region, then adds the pair to the mapping.

Input:

sourceComponentID:
The ID of the component in the source structural region that will map to component[s] in the destination structural region
destComponentIDs:
An integer or an iterable of integers representing IDs of components in the destionation region that the source component will map to.

Returns:

True:
if the IDs all exist in the respective source and destination structural regions
False:
otherwise
printToFileFor3DVis(openFileObject)[source]

print the component interval region to a file formatted for visualtization.

data is printed one segment on each line. Each segment is printed with 3D coordinates.

Input:

openFileObject:
a file object that has been opened for writing.
pyspatiotemporalgeom.componentMovingRegion.computeMapsAtTimeInstants(zList, cir1, cir2)[source]

Compute a map overlay of the structural regions defined by cir1 and cir2 at each time in the zList

Input:

zList
A list of time values. Sorted from earliest to latest
cir1 and cir2
component interval regions. It is assumed they are aligned in the sense that they have equivalent source and destination times.

Output:

A list maps where each map is a tuple containing: the time instant, a list of segments, above labels for the segments, below labels for the segments, and the label to label list dictionary:

[(zval, segList, LAlist, LBList, label2DataDictionary, r1MapLabelToStructureIDDictionary,r2MapLabelToStructureIDDictionary, r1facetoHoleMappingUsingMapLabels, r2facetoHoleMappingUsingMapLabels ), ... ]

The maps are labeled with the following conventions:

  • interior face cycles have an even label
  • interior of hole cycles have an odd label
  • exterior label is -1
  • Labels for sturctural regions from cir1 have positive labels (except for an exterior of -1), labels for sturctural regions from cir2 have negative labels,

Each seg will have a single above label (LA) and a single below labele (LB). The label2DataDictionary maps that LA or LB to the list of regin labels indicating the interiors of all cycles that lie above (LA) or below (LB) the line segment. This labels were made according to the previos bullet point. r1MapLabelToStructureIDDictionary maps those labels to the actual ID of the structure in the source structural region of CIR1. likewise for r2MapLabelToStructureIDDictionary.

pyspatiotemporalgeom.componentMovingRegion.computeTimeInstantsOfTopologicalChange(cir1, cir2)[source]

Find all time instants when a topological change occurs betweeen two input component interval regions.

Input:

cir1, cir2
Two component interval regions

Returns:

A sorted list of floats where each float is a time instant where the two input component interval regions experience a change in topology relative to each other. For example, they were disjoint, and suddenly they meet. These instants are discovered based on the intersections of motion triangles
pyspatiotemporalgeom.componentMovingRegion.intersection(cir1, cir2)[source]

computes the intersection of two component interval regions

Warning

Intersection assumes that cir1 and cir2 are temporally aligned. That is, they have the same start and end times.

If this is not the case, you must align them using def computeTimeInstantsOfTopologicalChange() and then create the aligned interval regions.

Input:

cir1:
a component interval region
cir2:
a component interval region

Returns:

A list of component interval regions sorted by time (earliest to latest)

pyspatiotemporalgeom.componentMovingRegion.relevantCyclesForIntersection(LA, sr1MapLabelF2HDict, LB, sr2MapLabelF2HDict)[source]

This function is called by def intersection( cir1, cir2 ).

Given a list of labels that lie above and a list of labels that lie below the same segment in a map, this function returns a set containing tuples of labels where each tuple indicates

  • a pair of map labels that corresond to Face IDS from the input structural regions used to build the map that intersect
  • OR, a pair of map labels and a hole label that corresponds to a hole ID in the input structural region

essentially, we are identifying overlapping faces, and holes that overlap overlapping faces

Input:

LA
the labels that lie above a segment from a map created with computeMapsAtTimeInstants()
sr1MapLabelF2HDict
A copy of the structural region’s F2H mapping, except map labels are used instead of IDs from the structural labels. computeMapsAtTimeInstants() provides this as a return value.
LB, sr2MapLabelF2HDict
correspond to LA and sr1MapLabelF2HDict, except the labels lie below the segment, and the dicitonanary applies to the second input structural region to computeMapsAtTimeInstants()

Returns:

A set of tuples where each tuple indicates a pair of face labels. The labels correspond to the intersection of two faces from the input structural regions to computeMapsAtTimeInstants(). Map lables are used as opposed to structure IDs in the structural regions.

A set of tuples where each tuple is a triple; a face label, a face label, and a hole label. This corresponds to a hole intersecting the intersection of two faces from the input structural regions passed to computeMapsAtTimeInstants(). Map labels are used, as opposed to structure IDs in the structural regions.