Algorithm
+-
+
- Dimension 2 - the centroid ic computed
+ as a weighted sum of the centroids
+ of a decomposition of the area into (possibly overlapping) triangles.
+ Holes and multipolygons are handled correctly.
+ See
http://www.faqs.org/faqs/graphics/algorithms-faq/ + for further details of the basic approach.
+ - Dimension 1 - Computes the average of the midpoints + of all line segments weighted by the segment length. + Zero-length lines are treated as points. + +
- Dimension 0 - Compute the average coordinate over all points. + Repeated points are all included in the average + +
-
+
- 1 if q is counter-clockwise (left) from p1-p2 +
- -1 if q is clockwise (right) from p1-p2 +
- 0 if q is collinear with p1-p2
-
+
- -1 if the determinant is negative, +
- 1 if the determinant is positive, +
- 0 if the determinant is 0. +
-
+
- The orientation index if it can be computed safely +
- > 1 if the orientation index cannot be computed safely > +
-
+
- The list of points is assumed to have the first and last points equal. +
- This will handle coordinate lists which contain repeated points. +
-
+
- The list of points is assumed to have the first and last points equal. +
- This will handle coordinate lists which contain repeated points. +
-
+
- positive
- negative
- zero
-
+
- positive
- negative
- zero
Algorithm:
+-
+
- Find a Y value which is close to the centre of + the geometry's vertical extent but is different + to any of it's Y ordinates. +
- Create a horizontal bisector line using the Y value + and the geometry's horizontal extent +
- Find the intersection between the geometry + and the horizontal bisector line. + The intersection is a collection of lines and points. +
- Pick the midpoint of the largest intersection geometry +
KNOWN BUGS
+-
+
- If a fixed precision model is used, + in some cases this method may return a point + which does not lie in the interior.
-
+
- the segments do not intersect
+ - the segments intersect in a single point
+ - the segments are collinear and they intersect in a line segment
+
-
+
- As a centre point and a radius +
- By the set of points defining the circle. + + Depending on the number of points in the input + and their relative positions, this + will be specified by anywhere from 0 to 3 points. +
- 0 or 1 points indicate an empty or trivial input point arrangment. +
- 2 or 3 points define a circle which contains + all the input points. +
-
+
-
+
- the diameter line of the Minimum Bounding Circle +
- an empty line if the input is empty +
- a Point if the input is a point +
-
+
s do not enclose any area - points inside the ring are still in the EXTERIOR of the ring.
+
-
+
- touch the ray +
- lie in in any ring which may contain the point +
-
+
- -1 if the determinant is negative, +
- 1 if the determinant is positive, +
- 0 if the determinant is null. +
-
+
- 1 if q is counter-clockwise (left) from p1-p2 +
- -1 if q is clockwise (right) from p1-p2 +
- 0 if q is collinear with p1-p2
Binary Predicates:
+ Because it is not clear at this time what semantics for spatial + analysis methods involvingOverlay Methods:
+ The spatial analysis methods will + return the most specific class possible to represent the result. If the + result is homogeneous, aGeometry Equality
+ There are two ways of comparing geometries for equality: + structural equality and topological equality. +Structural Equality
+ Structural Equality is provided by the +Topological Equality
+ Topological Equality is provided by the +this, if the geometry is not a collection.
+ -
+
- The DE-9IM intersection matrix for the two geometries matches
FF*FF**** .
+ !g.intersects(this) == true
(Disjoint is the inverse ofIntersects )
+
-
+
- The geometries have at least one point in common, + but their interiors do not intersect +
- The DE-9IM Intersection Matrix for the two geometries matches
+ at least one of the following patterns
+
-
+
FT******* ,
+ F**T***** or
+ F***T**** .
+
+
-
+
- The two geometries have at least one point in common +
- The DE-9IM Intersection Matrix for the two geometries matches
+[T********] or
+[*T*******] or
+[***T*****] or
+[****T****]
+ -
!g.disjoint(this)
+ (Intersects is the inverse ofDisjoint )
+
-
+
- The geometries have some but not all interior points in common. +
- The DE-9IM Intersection Matrix for the two geometries matches
+ one of the following patterns:
+
-
+
- Code
[T*T******] [T*****T**] [0********]
Description for P/L, P/A, and L/A situations +for L/P, A/P, and A/L situations) +for L/L situations +
+
false.
+ within predicate has the following equivalent definitions:
+ -
+
- + Every point of this geometry is a point of the other geometry, + and the interiors of the two geometries have at least one point in common. + +
- The DE-9IM Intersection Matrix for the two geometries matches
[T*F**F***]
+ g.contains(this) == true
(Within is the converse of)
+
-
+
- The geometries have at least one point each not shared by the other (or equivalently neither covers the other), + they have the same dimension, + and the intersection of the interiors of the two geometries has + the same dimension as the geometries themselves. +
- The DE-9IM Intersection Matrix for the two geometries matches
+
[T*T***T**] (for two points or two surfaces) + or[1*T***T**] (for two curves)
+
-
+
- Every point of the other geometry is a point of this geometry. +
- The DE-9IM Intersection Matrix for the two geometries matches at least
+ one of the following patterns:
+
-
+
[T*****FF*] or
+ [*T****FF*] or
+ [***T**FF*] or
+ [****T*FF*]
+
+ g.CoveredBy(this) == true
+ (covers is the converse of)
+
-
+
- Every point of this geometry is a point of the other geometry. + +
- The DE-9IM Intersection Matrix for the two geometries matches
+ at least one of the following patterns:
+
-
+
[T*F**F***]
+ [*TF**F***]
+ [**FT*F***]
+ [**F*TF***]
+ g.Covers(this) == true
+ (CoveredBy is the converse of) +
+
-
+
- 0 (dimension 0) +
- 1 (dimension 1) +
- 2 (dimension 2) +
- T ( matches 0, 1 or 2) +
- F ( matches FALSE) +
- * ( matches any value) +
equals predicate has the following equivalent definitions:
+ -
+
- The two geometries have at least one point in common, + and no point of either geometry lies in the exterior of the other geometry. +
- The DE-9IM Intersection Matrix for the two geometries matches
+ the pattern T*F**FFF*
+
+ T*F + **F + FF* +
+
Geometrys are topologically equal-
+
- (default) a semi-circle
+ - a straight line perpendicular to the end segment
+ - a half-square
+
-
+
- (default) a semi-circle
+ - a straight line perpendicular to the end segment
+ - a half-square
+
-
+
- (default) a semi-circle
+ - a straight line perpendicular to the end segment
+ - a half-square
+
-
+
- (default) a semi-circle
+ - a straight line perpendicular to the end segment
+ - a half-square
+
-
+
- Unioning a set of
s has the effect of fully noding and dissolving the linework.
+ - Unioning a set of
s always returns a geometry + (unlike ), which may return geometries of lower dimension if a topology + collapse occurred).
+
-
+
- they have the same class, +
- they have the same values of Coordinates, + within the given tolerance distance, in their internal + Coordinate lists, in exactly the same order. +
-
+
- they have the same class, +
- they have the same values of Coordinates in their internal + Coordinate lists, in exactly the same order. +
-
+
- Point (lowest), +
- MultiPoint, +
- LineString, +
- LinearRing, +
- MultiLineString, +
- Polygon, +
- MultiPolygon, +
- GeometryCollection (highest). +
-
+
- Point (lowest), +
- MultiPoint, +
- LineString, +
- LinearRing, +
- MultiLineString, +
- Polygon, +
- MultiPolygon, +
- GeometryCollection (highest). +
-
+
- Point (lowest), +
- MultiPoint, +
- LineString, +
- LinearRing, +
- MultiLineString, +
- Polygon, +
- MultiPolygon, +
- GeometryCollection (highest). +
o, as
+ defined in "Normal Form For Geometry" in the JTS Technical
+ Specifications
+ -
+
- Valid polygonal geometries are simple, since their rings
+ must not self-intersect.
IsSimple + tests for this condition and reportsfalseif it is not met. + (This is a looser test than checking for validity).
+ - Linear rings have the same semantics. +
- Linear geometries are simple iff they do not self-intersect at points + other than boundary points. +
- Zero-dimensional geometries (points) are simple iff they have no + repeated points. +
- Empty
Geometrys are always simple.
+
Geometry is simple-
+
- empty, returns an empty
Point
+ - a point, returns a
Point
+ - a line parallel to an axis, a two-vertex
LineString ,
+ - otherwise, returns a
+
Polygon whose vertices are (minx, miny), (maxx, miny), (maxx, + maxy), (minx, maxy), (minx, miny).
+
-
+
- null returns an empty
- a point returns a non-empty
- a line returns a two-point
- a rectangle returns a
whose points are (minx, maxy), (minx, maxy), (maxx, maxy), (maxx, miny).
+
+ If
+ If
+ If
The
+ If
+ If an
+ If an
+ If an
+ The distance is: +
-
+
- positive if the point lies above the plane (relative to the plane normal) +
- zero if the point is on the plane +
- negative if the point lies below the plane (relative to the plane normal) +
+ Note that some clients (such as
-
+
- the only intersection between any two linestrings occurs at their endpoints. +
+ |x.lo| <= 0.5*ulp(x.hi) ++ and ulp(y) means "unit in the last place of y". + The basic arithmetic operations are implemented using + convenient properties of IEEE-754 floating-point arithmetic. +
References
+-
+
- Priest, D., Algorithms for Arbitrary Precision Floating Point Arithmetic, + in P. Kornerup and D. Matula, Eds., Proc. 10th Symposium on Computer Arithmetic, + IEEE Computer Society Press, Los Alamitos, Calif., 1991. +
- Yozo Hida, Xiaoye S. Li and David H. Bailey, + Quad-Double Arithmetic: Algorithms, Implementation, and Application, + manuscript, Oct 2000; Lawrence Berkeley National Laboratory Report BNL-46996. +
- David Bailey, High Precision Software Directory; + http://crd.lbl.gov/~dhbailey/mpdist/index.html +
-
+
- if this value is > 0, returns 1 +
- if this value is < 0, returns -1 +
- if this value is = 0, returns 0 +
- if this value is NaN, returns 0 +
-
+
- If this value is NaN, returns NaN. +
-
+
- If this value is NaN, returns NaN. +
-
+
- if this value is NaN, it is returned. +
+ or
+ [+|-] {digit} [ . {digit} ] [ ( e | E ) [+|-] {digit}+
+
+ -
+
- If the argument is NaN or less than zero, then the result is NaN. +
- If the argument is positive infinity, then the result is positive infinity. +
- If the argument is positive zero or negative zero, then the result is negative infinity. +
or
+ sum = frac * this + (1 - frac) * v ++
-
+
- +
- NormalizePositive(0.0) = 0.0 +
- NormalizePositive(-PI) =
- NormalizePositive(-2PI) = 0.0 +
- NormalizePositive(-3PI) =
- NormalizePositive(-4PI) = 0 +
- NormalizePositive(PI) =
- NormalizePositive(2PI) = 0.0 +
- NormalizePositive(3PI) =
- NormalizePositive(4PI) = 0.0 +
-
+
- The angles are assumed to be normalized to the range [-Pi, Pi]. +
- The result will be in the range [0, Pi]. +
doubles, allowing for NaN values.
+ NaN is treated as being less than any valid number.
+ double
+ A double
+ LineString
+ -
+
- 1 if
p is to the left of this segment
+ - -1 if
p is to the right of this segment
+ - 0 if
p is collinear with this segment
+
0.0 returns the start point of the segment;
+ A fraction of 1.0 returns the end point of the segment.
+ If the fraction is < 0.0 or > 1.0 the point returned
+ will lie before the start or beyond the end of the segment.
+ 0.0 offsets from the start point of the segment;
+ A fraction of 1.0 offsets from the end point of the segment.
+ The computed point is offset to the left of the line if the offset distance is
+ positive, to the right if negative.
+ true if this object has valid values
+
+ -
+
- The coordinate which defines it if any) is a valid coordinate
+ (i.e. does not have an
NaN X- or Y-ordinate
+
-
+
- the coordinates which define it are valid coordinates +
- the linear rings for the shell and holes are valid + (i.e. are closed and do not self-intersect) +
- holes touch the shell or another hole at at most one point + (which implies that the rings of the shell and holes must not cross) +
- the interior of the polygon is connected, + or equivalently no sequence of touching holes + makes the interior of the polygon disconnected + (i.e. effectively split the polygon into two pieces). +
-
+
- jtsPt.x = round( (inputPt.x * scale ) / scale +
- jtsPt.y = round( (inputPt.y * scale ) / scale +
+ Used when short-circuit tests are not conclusive. +
+ Uses short-circuit tests and indexing to improve performance. +
-
+
- reflection (through a line) +
- rotation (around the origin) +
- scaling (relative to the origin) +
- shearing (in both the X and Y directions) +
- translation +
+ A coordinate P = (x, y) can be transformed to a new coordinate P' = (x', y') + by representing it as a 3x1 matrix and using matrix multiplication to compute: ++ T = | m00 m01 m02 | + | m10 m11 m12 | + | 0 0 1 | +
++ | x' | = T x | x | + | y' | | y | + | 1 | | 1 | +
Transformation Composition
+++ A.compose(B) = TB x TA +
Transformation Inversion
+++ | 1 0 0 | + | 0 1 0 | + | 0 0 1 | +
++ * 1 + * inverse(A) = --- x adjoint(A) + * det + * + * + * = 1 | m11 -m01 m01*m12-m02*m11 | + * --- x | -m10 m00 -m00*m12+m10*m02 | + * det | 0 0 m00*m11-m10*m01 | + * + * + * + * = | m11/det -m01/det m01*m12-m02*m11/det | + * | -m10/det m00/det -m00*m12+m10*m02/det | + * | 0 0 1 | + * + *
++ d = sqrt(x2 + y2) + sin = x / d; + cos = x / d; + Tref = Trot(sin, cos) x Tscale(1, -1) x Trot(-sin, cos) +
theta
+ has the value:
+ ++ | cos(theta) -sin(theta) 0 | + | sin(theta) cos(theta) 0 | + | 0 0 1 | +
++ | cosTheta -sinTheta 0 | + | sinTheta cosTheta 0 | + | 0 0 1 | +
++ | cosTheta -sinTheta x-x*cos+y*sin | + | sinTheta cosTheta y-x*sin-y*cos | + | 0 0 1 | +
++ | cosTheta -sinTheta x-x*cos+y*sin | + | sinTheta cosTheta y-x*sin-y*cos | + | 0 0 1 | +
++ | xScale 0 dx | + | 1 yScale dy | + | 0 0 1 | +
+ Note that a shear of (1, 1) is not + equal to shear(1, 0) composed with shear(0, 1). + Instead, shear(1, 1) corresponds to a mapping onto the + line x = y. ++ | 1 xShear 0 | + | yShear 1 0 | + | 0 0 1 | +
++ | 1 0 dx | + | 1 0 dy | + | 0 0 1 | +
++ A.compose(B) = TB x TA +
++ A.composeBefore(B) = TA x TB +
dest coordinateCoordinateSequence
+ the index of the coordinate to transform
+
+ AffineTransformation[[m00, m01, m02], [m10, m11, m12]]
+
+ + m00, m01, m02, m10, m11, m12 ++
++ | m00 m01 m02 | + | m10 m11 m12 | = m00 * m11 - m01 * m10 + | 0 0 1 | +
-
+
- An affine transformation +
null if the control vectors do not determine a well-defined transformation.
+
-
+
- a translation from the start point of the source baseline to the start point of the destination baseline, +
- a rotation through the angle between the baselines about the destination start point, +
- and a scaling equal to the ratio of the baseline lengths. +
-
+
- + The values of the coordinates may be changed. + The editor does not check whether changing coordinate values makes the result Geometry invalid + +
- + The coordinate lists may be changed (e.g. by adding, deleting or modifying coordinates). + The modifed coordinate lists must be consistent with their original parent component + (e.g. a LinearRing must always have at least 4 coordinates, and the first and last + coordinate must be equal). + +
- + Components of the original point may be deleted + (e.g. holes may be removed from a Polygon, or LineStrings removed from a MultiLineString). + Deletions will be propagated up the component tree appropriately. +
Polygon cannot be collapsed into a LineString).
+ If changing the structure is required, use a -
+
- The resulting Geometry is not checked for validity.
+ If validity needs to be enforced, the new Geometry's
+
method should be called.
+ - By default the UserData of the input geometry is not copied to the result. +
null if the geometry is to be deleted.
+ T elements from a single + In order to avoid overhead the algorithm runs in-place + on A - if A should not be modified the client must supply a copy. +
-
+
- A vector containing the solution (if any) +
null if the system has no or no unique solution
+
-
+
- On
- Left
- Right
-
+
- the segments within a monotone chain never intersect each other +
- the envelope of any contiguous subset of the segments in a monotone chain + is equal to the envelope of the endpoints of the subset. +
-
+
- Envelope select
- Overlap
-
+
- the best matching node +
- null if no match was found +
-
+
- The data for the point +
- The created node +
+ or -1 if no subquad wholly contains the envelope
+
+ Any type of object can also be indexed, as long as it has an extent that can be + represented by an
-
+
- empty +
- an interior node containing child
s
+ - a leaf node containing data items (
s).
+
- 0x80000000 flag if geometry's z-ordinate values are written +
- 0x40000000 flag if geometry's m-ordinate values are written +
- 0x20000000 flag if geometry's SRID value is written
+ The referenced geometry is not maintained within this location, + but must be provided for operations which require it. + Various methods are provided to manipulate the location value + and query the geometry it references. +
index
+ + Note that some clients (such as
+ Note that some clients (such as
+ Note that some clients (such as
+ or
+ 0 the two objects are equal;
+ 1 this one is greater. +
+ 0 this SegmentNode is at the argument location;
+ 1 this SegmentNode is located after the argument location. +
+ 0 if the two nodes are equal, or
+ 1 if node1 occurs first. +
+ or
-
+
- the usual round end caps
+ - end caps are truncated flat at the line ends
+ - end caps are squared off at the buffer distance beyond the line ends
+
-
+
- the usual round join
+ - corners are "sharp" (up to a distance limit})
+ - corners are beveled (clipped off)
+
-
+
- Quadrant segments (accuracy of approximation for circular arcs) +
- End Cap style +
- Join style +
- Mitre limit +
- whether the buffer is single-sided +
-
+
QuadrantSegments >>= 1QuadrantSegments = 0QuadrantSegments < 0
-
+
- a positive distance indicates the left-hand side +
- a negative distance indicates the right-hand side +
+ or
+ or
-
+
- -1 : if DS1.seg is left of or below DS2.seg (DS1 < DS2). +
- 1 : if DS1.seg is right of or above DS2.seg (DS1 > DS2). +
- 0 : if the segments are identical +
-
+
- The logic does not obey the
contract. + This is acceptable for the intended usage, but may cause problems if used with some + utilities in the .Net standard library (e.g. .
+
+ or
+ or
+ or
+ or
-
+
- + Performance is improved due to the effects of the R-tree index + and the pruning due to the Branch-and-Bound approach +
- + The spatial index on the target geometry can be cached + to allow reuse in an incremental query situation. +
-
+
- + A Geometry is simple if and only if the only self-intersections are at boundary points. + +
-
+
- Valid
geometries are simple by definition, so + IsSimple trivially returns true.
+ (Note: this means that IsSimple cannot be used to test + for (invalid) self-intersections in Polygons. + In order to check if a Polygonal geometry has self-intersections, + use).
+ geometries are simple if and only if they do not self-intersect at interior points + (i.e. points other than boundary points). + This is equivalent to saying that no two linear components satisfy the SFS + predicate.
+ - Zero-dimensional (
) geometries are simple if and only if they have no + repeated points.
+ - Empty
s are always simple by definition.
+
LineStrings touch
+ only at their endpoints, use IsSimpleOp with {@link BoundaryNodeRule#ENDPOINT_BOUNDARY_RULE}.
+ For example, this can be used to validate that a set of lines form a topologically valid
+ linear network.
+ + or
-
+
- result has the dimension of the lowest input dimension
+ - result has the dimension of the highest input dimension
+ - result has the dimension of the left-hand input
+ - result has the dimension of the highest input dimension + (since symDifference is the union of the differences).
+
or +
or +
+ or -1 if no segment snaps to the snap point.
+ or
+ or
+ or
+ The class supports specifying a custom
-
+
- Unioning a set of
s has the effect of merging the areas (i.e. the same effect as iteratively unioning all individual polygons together).
+ - Unioning a set of
s has the effect of fully noding + and dissolving the input linework. + In this context "fully noded" means that there will be + an endpoint or node in the result + for every endpoint or line segment crossing in the input. + "Dissolved" means that any duplicate (e.g. coincident) line segments or portions + of line segments will be reduced to a single line segment in the output. + This is consistent with the semantics of the + operation. + If merged linework is required, the class can be used.
+ - Unioning a set of
s has the effect of merging all identical points (producing a set with no duplicates).
+ or
-
+
- No two distinct vertices of G are closer than r. +
- No vertex of G is closer than r to an edge of G of which the vertex is not an endpoint +
References
+-
+
- [Mi88] Milenkovic, V. J., + Verifiable implementations of geometric algorithms + using finite precision arithmetic. + in Artificial Intelligence, 377-401. 1988 +
- [TV06] Thompson, Rod and van Oosterom, Peter, + Interchange of Spatial Data-Inhibiting Factors, + Agile 2006, Visegrad, Hungary. 2006 +
+ or
+ or
+ or
-
+
- valid topology is not required +
- fixing topology is a relative expensive operation +
- in some pathological cases the topology fixing operation may either fail or run for too long +
+ Points closer than this tolerance to a simplified segment may + be removed. +
-
+
- The result has the same number of shells and holes as the input, + with the same topological structure +
- The result rings touch at no more than the number of touching points in the input + (although they may touch at fewer points). + The key implication of this statement is that if the + input is topologically valid, so is the simplified output. +
KNOWN BUGS
+-
+
- May create invalid topology if there are components which are small + relative to the tolerance value. + In particular, if a small hole is very near an edge, + it is possible for the edge to be moved by a relatively large tolerance value + and end up with the hole outside the result shell (or inside another hole). + Similarly, it is possible for a small polygon component to end up inside + a nearby larger polygon. + A workaround is to test for this situation in post-processing and remove + any invalid holes or polygons. +
-
+
- The projection of the encroaching point on the segment +
- A point on the segment which will produce two segments which will not be further encroached +
- The point on the segment which is the same distance from an endpoint as the encroaching + point +
+ or null if no such triangle exists +
+ or
+ or -1 if the edge is not an edge of this triangle +
+ or -1 if the vertex is not in the triangle +
null
+ + LINESTRING (1507029.9878 518325.7547, 1507022.1120341457 518332.8225183258, + 1507029.9833 518325.7458, 1507029.9896965567 518325.744909031) ++
null if there is none0.0 returns the end point of the
+ segment; a fraction of 1.0 returns the start point of the segment.
+ -
+
-
+
an envelope supplied by +.
+ -
+
an envelope determined by the input sites. +
+
+ StreamTokenizer tokenizer = new StreamTokenizer();
+ tokenizer.GrabWhitespace = true;
+ tokenizer.Verbosity = VerbosityLevel.Debug; // just for debugging
+ tokenizer.TextReader = File.OpenText(fileName);
+ Token token;
+ while (tokenizer.NextToken(out token)) log.Info("Token = '{0}'", token);
+
+
+ StreamTokenizer tokenizer = new StreamTokenizer("some string");
+ ArrayList tokens = new ArrayList();
+ if (!tokenizer.Tokenize(tokens))
+ {
+ // error handling
+ }
+ foreach (Token t in tokens) Console.WriteLine("t = {0}", t);
+
+
+ for all geometries a, b: DHD(a, b) <= HD(a, b)
+
+ The approximation can be made as close as needed by densifying the input geometries.
+ In the limit, this value will approach the true Hausdorff distance:
+
+ DHD(A, B, densifyFactor) -> HD(A, B) as densifyFactor -> 0.0
+
+ The default approximation is exact or close enough for a large subset of useful cases.
+ -
+
- + computing distance between Linestrings that are roughly parallel to each other, + and roughly equal in length. This occurs in matching linear networks. + +
- Testing similarity of geometries. +
+ A = LINESTRING (0 0, 100 0, 10 100, 10 100)
+ B = LINESTRING (0 100, 0 10, 80 10)
+
+ DHD(A, B) = 22.360679774997898
+ HD(A, B) ~= 47.8
+
+