[DebianGIS-dev] r892 - in packages/jts/branches/upstream/current: . src src/com/vividsolutions/jts src/com/vividsolutions/jts/algorithm src/com/vividsolutions/jts/geom src/com/vividsolutions/jts/geom/impl src/com/vividsolutions/jts/geom/util src/com/vividsolutions/jts/geomgraph src/com/vividsolutions/jts/geomgraph/index src/com/vividsolutions/jts/index src/com/vividsolutions/jts/index/bintree src/com/vividsolutions/jts/index/chain src/com/vividsolutions/jts/index/quadtree src/com/vividsolutions/jts/index/strtree src/com/vividsolutions/jts/index/sweepline src/com/vividsolutions/jts/io src/com/vividsolutions/jts/linearref src/com/vividsolutions/jts/noding src/com/vividsolutions/jts/noding/snapround src/com/vividsolutions/jts/operation src/com/vividsolutions/jts/operation/buffer src/com/vividsolutions/jts/operation/distance src/com/vividsolutions/jts/operation/linemerge src/com/vividsolutions/jts/operation/overlay src/com/vividsolutions/jts/operation/polygonize src/com/vividsolutions/jts/operation/predicate src/com/vividsolutions/jts/operation/relate src/com/vividsolutions/jts/operation/valid src/com/vividsolutions/jts/planargraph src/com/vividsolutions/jts/planargraph/algorithm src/com/vividsolutions/jts/precision src/com/vividsolutions/jts/simplify src/com/vividsolutions/jts/util src/com/vividsolutions/jtsexample src/com/vividsolutions/jtsexample/geom src/com/vividsolutions/jtsexample/linearref src/com/vividsolutions/jtsexample/operation/distance src/com/vividsolutions/jtsexample/operation/linemerge src/com/vividsolutions/jtsexample/operation/polygonize src/com/vividsolutions/jtsexample/precision src/com/vividsolutions/jtsexample/technique src/jtsio src/jtsio/src src/jtsio/src/com src/jtsio/src/com/vividsolutions src/jtsio/src/com/vividsolutions/jts src/jtsio/src/com/vividsolutions/jts/io src/jtsio/src/com/vividsolutions/jts/io/gml2 test/vivid
frankie at alioth.debian.org
frankie at alioth.debian.org
Fri Jun 15 22:22:07 UTC 2007
Author: frankie
Date: 2007-06-15 22:22:06 +0000 (Fri, 15 Jun 2007)
New Revision: 892
Added:
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/JTSVersion.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequenceComparator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequences.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/ByteArrayInStream.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/ByteOrderDataInStream.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/ByteOrderValues.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/InStream.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/InputStreamInStream.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/OutStream.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/OutputStreamOutStream.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/WKBConstants.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/WKBReader.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/WKBWriter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/ExtractLineByLocation.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LengthIndexOfPoint.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LengthIndexedLine.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LengthLocationMap.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LinearGeometryBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LinearIterator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LinearLocation.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LocationIndexOfLine.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LocationIndexOfPoint.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/LocationIndexedLine.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/linearref/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/IntersectionAdder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/IntersectionFinderAdder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/MCIndexNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/Octant.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/OrientedCoordinateArray.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/ScaledNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SegmentPointComparator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SegmentStringDissolver.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SinglePassNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/HotPixel.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/MCIndexPointSnapper.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/MCIndexSnapRounder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/SimpleSnapRounder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/LineSequencer.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/Subgraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/algorithm/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/algorithm/ConnectedSubgraphFinder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/CollectionUtil.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/linearref/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/linearref/LinearRefExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique/PolygonUnionUsingBuffer.java
packages/jts/branches/upstream/current/src/jtsio/
packages/jts/branches/upstream/current/src/jtsio/src/
packages/jts/branches/upstream/current/src/jtsio/src/com/
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/gml2/
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/gml2/GMLConstants.java
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/gml2/GMLHandler.java
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/gml2/GMLReader.java
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/gml2/GMLWriter.java
packages/jts/branches/upstream/current/src/jtsio/src/com/vividsolutions/jts/io/gml2/GeometryStrategies.java
packages/jts/branches/upstream/current/src/jtsio/test/
Removed:
packages/jts/branches/upstream/current/doc/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/IndexVisitor.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/MCQuadtreeNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/SegmentSnapper.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/SimpleSegmentStringsSnapper.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/SnapRounder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique/UnionUsingBuffer.java
Modified:
packages/jts/branches/upstream/current/src/MANIFEST.MF
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointLine.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointPoint.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/LineIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MCPointInRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MinimumDiameter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustCGAlgorithms.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustLineIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NotRepresentableException.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointInRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointLocator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustCGAlgorithms.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustDeterminant.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustLineIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SIRtreePointInRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInAreaLocator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Coordinate.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateArrays.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateList.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequence.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequenceFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/DefaultCoordinateSequence.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/DefaultCoordinateSequenceFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Dimension.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Envelope.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Geometry.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/GeometryCollection.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/GeometryCollectionIterator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/GeometryComponentFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/GeometryFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/GeometryFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/IntersectionMatrix.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/LineSegment.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/LineString.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/LinearRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Location.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/MultiLineString.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/MultiPoint.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/MultiPolygon.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Point.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Polygon.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/PrecisionModel.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/TopologyException.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Triangle.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/impl/CoordinateArraySequence.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/impl/CoordinateArraySequenceFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/impl/PackedCoordinateSequence.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/GeometryEditor.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/GeometryTransformer.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/LinearComponentExtracter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/PointExtracter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/PolygonExtracter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/ShortCircuitedGeometryVisitor.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/Depth.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/DirectedEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/DirectedEdgeStar.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/Edge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeEnd.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeEndStar.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeIntersection.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeIntersectionList.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeList.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeNodingValidator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/EdgeRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/GeometryGraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/GraphComponent.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/Label.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/Node.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/NodeFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/NodeMap.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/PlanarGraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/Position.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/Quadrant.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/TopologyLocation.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/EdgeSetIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/MonotoneChain.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/MonotoneChainEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/MonotoneChainIndexer.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/SegmentIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/SimpleEdgeSetIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/SimpleMCSweepLineIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/SimpleSweepLineIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/SweepLineEvent.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index/SweepLineSegment.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/ArrayListVisitor.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/ItemVisitor.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/SpatialIndex.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree/Bintree.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree/Interval.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree/Key.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree/Node.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree/NodeBase.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree/Root.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/chain/MonotoneChain.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/chain/MonotoneChainBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/chain/MonotoneChainOverlapAction.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/chain/MonotoneChainSelectAction.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/DoubleBits.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/IntervalSize.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/Key.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/Node.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/NodeBase.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/Quadtree.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/Root.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/AbstractNode.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/AbstractSTRtree.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/Boundable.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/Interval.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/ItemBoundable.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/SIRtree.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/STRtree.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/sweepline/SweepLineEvent.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/sweepline/SweepLineIndex.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/sweepline/SweepLineInterval.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/sweepline/SweepLineOverlapAction.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/ParseException.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/WKTReader.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/WKTWriter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/IteratedNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/Noder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/NodingValidator.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SegmentIntersector.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SegmentNode.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SegmentNodeList.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SegmentString.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/SimpleNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/GeometryGraphOperation.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/IsSimpleOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/BufferBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/BufferOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/BufferSubgraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/OffsetCurveBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/OffsetCurveSetBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/RightmostEdgeFinder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer/SubgraphDepthLocater.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/distance/ConnectedElementLocationFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/distance/ConnectedElementPointFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/distance/DistanceOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/distance/GeometryLocation.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/EdgeString.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/LineMergeDirectedEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/LineMergeEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/LineMergeGraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/LineMerger.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/EdgeSetNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/LineBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/MaximalEdgeRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/MinimalEdgeRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/OverlayNodeFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/OverlayOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/PointBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay/PolygonBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize/EdgeRing.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize/PolygonizeDirectedEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize/PolygonizeEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize/PolygonizeGraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize/Polygonizer.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/predicate/RectangleContains.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/predicate/RectangleIntersects.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/predicate/SegmentIntersectionTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/EdgeEndBuilder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/EdgeEndBundle.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/EdgeEndBundleStar.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/RelateComputer.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/RelateNode.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/RelateNodeFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/RelateNodeGraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate/RelateOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/ConnectedInteriorTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/ConsistentAreaTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/IsValidOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/QuadtreeNestedRingTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/RepeatedPointTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/SimpleNestedRingTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/SweeplineNestedRingTester.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/TopologyValidationError.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/DirectedEdge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/DirectedEdgeStar.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/Edge.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/GraphComponent.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/Node.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/NodeMap.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/PlanarGraph.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/precision/CommonBits.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/precision/CommonBitsOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/precision/CommonBitsRemover.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/precision/EnhancedPrecisionOp.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/precision/SimpleGeometryPrecisionReducer.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/DouglasPeuckerLineSimplifier.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/DouglasPeuckerSimplifier.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/TaggedLineString.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/TaggedLineStringSimplifier.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/TopologyPreservingSimplifier.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/Assert.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/AssertionFailedException.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/CoordinateArrayFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/CoordinateCountFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/Debug.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/GeometricShapeFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/Stopwatch.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/UniqueCoordinateArrayFilter.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/BasicExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/ConstructionExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/ExtendedCoordinate.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/ExtendedCoordinateExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/ExtendedCoordinateSequence.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/ExtendedCoordinateSequenceFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/PrecisionModelExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/SimpleMethodsExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/distance/ClosestPointExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/linemerge/LineMergeExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/polygonize/PolygonizeExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/precision/EnhancedPrecisionOpExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique/LineStringSelfIntersections.java
packages/jts/branches/upstream/current/test/vivid/TestFunctionAA.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionAAPrec.xml
packages/jts/branches/upstream/current/test/vivid/TestRectanglePredicate.xml
packages/jts/branches/upstream/current/test/vivid/TestValid.xml
Log:
[svn-upgrade] Integrating new upstream version, jts (1.7)
Modified: packages/jts/branches/upstream/current/src/MANIFEST.MF
===================================================================
--- packages/jts/branches/upstream/current/src/MANIFEST.MF 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/MANIFEST.MF 2007-06-15 22:22:06 UTC (rev 892)
@@ -1,4 +1,4 @@
Manifest-version: 1.0
Implementation-Title: Java Topology Suite
-Implementation-Version: 1.6
+Implementation-Version: 1.7
Implementation-Vendor: Vivid Solutions
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/JTSVersion.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/JTSVersion.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/JTSVersion.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -0,0 +1,86 @@
+package com.vividsolutions.jts;
+
+/**
+ * JTS API version information.
+ * <p>
+ * Versions consist of a 3-part version number: <code>major.minor.patch</code>
+ * An optional release status string may be present in the string version of
+ * the version.
+ *
+ * @version 1.7
+ */
+public class JTSVersion {
+
+ /**
+ * The current version number of the JTS API.
+ */
+ public static final JTSVersion CURRENT_VERSION = new JTSVersion();
+
+ /**
+ * The major version number.
+ */
+ public static final int MAJOR = 1;
+
+ /**
+ * The minor version number.
+ */
+ public static final int MINOR = 7;
+
+ /**
+ * The patch version number.
+ */
+ public static final int PATCH = 0;
+
+ /**
+ * An optional string providing further release info (such as "alpha 1");
+ */
+ private static final String releaseInfo = "";
+
+ /**
+ * Prints the current JTS version to stdout.
+ *
+ * @param args the command-line arguments (none are required).
+ */
+ public static void main(String[] args)
+ {
+ System.out.println(CURRENT_VERSION);
+ }
+
+ private JTSVersion() {
+ }
+
+ /**
+ * Gets the major number of the release version.
+ *
+ * @return the major number of the release version.
+ */
+ public int getMajor() { return MAJOR; }
+
+ /**
+ * Gets the minor number of the release version.
+ *
+ * @return the minor number of the release version.
+ */
+ public int getMinor() { return MINOR; }
+
+ /**
+ * Gets the patch number of the release version.
+ *
+ * @return the patch number of the release version.
+ */
+ public int getPatch() { return PATCH; }
+
+ /**
+ * Gets the full version number, suitable for display.
+ *
+ * @return the full version number, suitable for display.
+ */
+ public String toString()
+ {
+ String ver = MAJOR + "." + MINOR + "." + PATCH;
+ if (releaseInfo != null && releaseInfo.length() > 0)
+ return ver + " " + releaseInfo;
+ return ver;
+ }
+
+}
\ No newline at end of file
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -39,7 +39,7 @@
* Specifies and implements various fundamental Computational Geometric algorithms.
* The algorithms supplied in this class are robust for double-precision floating point.
*
- * @version 1.6
+ * @version 1.7
*/
public class CGAlgorithms
{
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -45,7 +45,7 @@
* See <code>http://www.faqs.org/faqs/graphics/algorithms-faq/</code>
* for further details of the basic approach.
*
- * @version 1.6
+ * @version 1.7
*/
public class CentroidArea
{
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -41,7 +41,7 @@
* Compute the average of the midpoints
* of all line segments weighted by the segment length.
*
- * @version 1.6
+ * @version 1.7
*/
public class CentroidLine
{
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -40,7 +40,7 @@
* <h2>Algorithm</h2>
* Compute the average of all points.
*
- * @version 1.6
+ * @version 1.7
*/
public class CentroidPoint
{
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -1,36 +1,36 @@
/*
- * The JTS Topology Suite is a collection of Java classes that
- * implement the fundamental operations required to validate a given
- * geo-spatial data set to a known topological specification.
- *
- * Copyright (C) 2001 Vivid Solutions
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * For more information, contact:
- *
- * Vivid Solutions
- * Suite #1A
- * 2328 Government Street
- * Victoria BC V8T 5G5
- * Canada
- *
- * (250)385-6040
- * www.vividsolutions.com
+* The JTS Topology Suite is a collection of Java classes that
+* implement the fundamental operations required to validate a given
+* geo-spatial data set to a known topological specification.
+*
+* Copyright (C) 2001 Vivid Solutions
+*
+* This library is free software; you can redistribute it and/or
+* modify it under the terms of the GNU Lesser General Public
+* License as published by the Free Software Foundation; either
+* version 2.1 of the License, or (at your option) any later version.
+*
+* This library is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+* Lesser General Public License for more details.
+*
+* You should have received a copy of the GNU Lesser General Public
+* License along with this library; if not, write to the Free Software
+* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*
+* For more information, contact:
+*
+* Vivid Solutions
+* Suite #1A
+* 2328 Government Street
+* Victoria BC V8T 5G5
+* Canada
+*
+* (250)385-6040
+* www.vividsolutions.com
*/
package com.vividsolutions.jts.algorithm;
import com.vividsolutions.jts.geom.*;
@@ -43,29 +43,43 @@
* Computes the convex hull of a {@link Geometry}.
* The convex hull is the smallest convex Geometry that contains all the
* points in the input Geometry.
+ * <p>
* Uses the Graham Scan algorithm.
*
- *@version 1.6
+ *@version 1.7
*/
public class ConvexHull
{
- private PointLocator pointLocator = new PointLocator();
- //private CGAlgorithms cgAlgorithms = new RobustCGAlgorithms();
- private Geometry geometry;
- private GeometryFactory factory;
+ private GeometryFactory geomFactory;
+ private Coordinate[] inputPts;
/**
* Create a new convex hull construction for the input {@link Geometry}.
*/
public ConvexHull(Geometry geometry)
{
- this.geometry = geometry;
+ this(extractCoordinates(geometry), geometry.getFactory());
}
+ /**
+ * Create a new convex hull construction for the input {@link Coordinate} array.
+ */
+ public ConvexHull(Coordinate[] pts, GeometryFactory geomFactory)
+ {
+ inputPts = pts;
+ this.geomFactory = geomFactory;
+ }
+ private static Coordinate[] extractCoordinates(Geometry geom)
+ {
+ UniqueCoordinateArrayFilter filter = new UniqueCoordinateArrayFilter();
+ geom.apply(filter);
+ return filter.getCoordinates();
+ }
+
/**
* Returns a {@link Geometry} that represents the convex hull of the input
* geometry.
- * The geometry will contain the minimal number of points needed to
+ * The returned geometry contains the minimal number of points needed to
* represent the convex hull. In particular, no more than two consecutive
* points will be collinear.
*
@@ -75,40 +89,32 @@
* 0 points, an empty {@link GeometryCollection}.
*/
public Geometry getConvexHull() {
- factory = geometry.getFactory();
- UniqueCoordinateArrayFilter filter = new UniqueCoordinateArrayFilter();
- geometry.apply(filter);
- Coordinate[] pts = filter.getCoordinates();
-
- if (pts.length == 0) {
- return factory.createGeometryCollection(null);
+ if (inputPts.length == 0) {
+ return geomFactory.createGeometryCollection(null);
}
- if (pts.length == 1) {
- return factory.createPoint(pts[0]);
+ if (inputPts.length == 1) {
+ return geomFactory.createPoint(inputPts[0]);
}
- if (pts.length == 2) {
- return factory.createLineString(pts);
+ if (inputPts.length == 2) {
+ return geomFactory.createLineString(inputPts);
}
+ Coordinate[] reducedPts = inputPts;
+ // use heuristic to reduce points, if large
+ if (inputPts.length > 50) {
+ reducedPts = reduce(inputPts);
+ }
// sort points for Graham scan.
- Coordinate[] pspts;
- if (pts.length > 10) {
- //Probably should be somewhere between 50 and 100?
- Coordinate[] rpts = reduce(pts);
- pspts = preSort(rpts);
- }
- else {
- pspts = preSort(pts);
- }
+ Coordinate[] sortedPts = preSort(reducedPts);
// Use Graham scan to find convex hull.
- Stack cHS = grahamScan(pspts);
+ Stack cHS = grahamScan(sortedPts);
// Convert stack to an array.
Coordinate[] cH = toCoordinateArray(cHS);
- // Convert array to linear ring.
+ // Convert array to appropriate output geometry.
return lineOrPolygon(cH);
}
@@ -125,42 +131,54 @@
return coordinates;
}
- private Coordinate[] reduce(Coordinate[] pts) {
- BigQuad bigQuad = bigQuad(pts);
- // Build a linear ring defining a big poly.
- ArrayList bigPoly = new ArrayList();
- bigPoly.add(bigQuad.westmost);
- if (!bigPoly.contains(bigQuad.northmost)) {
- bigPoly.add(bigQuad.northmost);
+ /**
+ * Uses a heuristic to reduce the number of points scanned
+ * to compute the hull.
+ * The heuristic is to find a polygon guaranteed to
+ * be in (or on) the hull, and eliminate all points inside it.
+ * A quadrilateral defined by the extremal points
+ * in the four orthogonal directions
+ * can be used, but even more inclusive is
+ * to use an octilateral defined by the points in the 8 cardinal directions.
+ * <p>
+ * Note that even if the method used to determine the polygon vertices
+ * is not 100% robust, this does not affect the robustness of the convex hull.
+ *
+ * @param pts
+ * @return
+ */
+ private Coordinate[] reduce(Coordinate[] inputPts)
+ {
+ //Coordinate[] polyPts = computeQuad(inputPts);
+ Coordinate[] polyPts = computeOctRing(inputPts);
+ //Coordinate[] polyPts = null;
+
+ // unable to compute interior polygon for some reason
+ if (polyPts == null)
+ return inputPts;
+
+// LinearRing ring = geomFactory.createLinearRing(polyPts);
+// System.out.println(ring);
+
+ // add points defining polygon
+ TreeSet reducedSet = new TreeSet();
+ for (int i = 0; i < polyPts.length; i++) {
+ reducedSet.add(polyPts[i]);
}
- if (!bigPoly.contains(bigQuad.eastmost)) {
- bigPoly.add(bigQuad.eastmost);
- }
- if (!bigPoly.contains(bigQuad.southmost)) {
- bigPoly.add(bigQuad.southmost);
- }
- if (bigPoly.size() < 3) {
- return pts;
- }
- bigPoly.add(bigQuad.westmost);
- Coordinate[] bigPolyArray = new Coordinate[bigPoly.size()];
- LinearRing bQ = factory.createLinearRing((Coordinate[]) bigPoly.toArray(bigPolyArray));
-// LinearRing bQ = new LinearRing((Coordinate[]) bigPoly.toArray(bigPolyArray),
-// geometry.getPrecisionModel(), geometry.getSRID());
-
- // load an array with all points not in the big poly
- // and the defining points.
- TreeSet reducedSet = new TreeSet(bigPoly);
- for (int i = 0; i < pts.length; i++) {
- if (pointLocator.locate(pts[i], bQ) == Location.EXTERIOR) {
- reducedSet.add(pts[i]);
+ /**
+ * Add all unique points not in the interior poly.
+ * CGAlgorithms.isPointInRing is not defined for points actually on the ring,
+ * but this doesn't matter since the points of the interior polygon
+ * are forced to be in the reduced set.
+ */
+ for (int i = 0; i < inputPts.length; i++) {
+ if (! CGAlgorithms.isPointInRing(inputPts[i], polyPts)) {
+ reducedSet.add(inputPts[i]);
}
}
- Coordinate[] rP = (Coordinate[]) reducedSet.toArray(new Coordinate[0]);
-
- // Return this array as the reduced problem.
- return rP;
+ Coordinate[] reducedPts = CoordinateArrays.toCoordinateArray(reducedSet);
+ return reducedPts;
}
private Coordinate[] preSort(Coordinate[] pts) {
@@ -178,14 +196,14 @@
}
// sort the points radially around the focal point.
- radialSort(pts);
+ Arrays.sort(pts, 1, pts.length, new RadialComparator(pts[0]));
+
+ //radialSort(pts);
return pts;
}
private Stack grahamScan(Coordinate[] c) {
Coordinate p;
- Coordinate p1;
- Coordinate p2;
Stack ps = new Stack();
p = (Coordinate) ps.push(c[0]);
p = (Coordinate) ps.push(c[1]);
@@ -202,53 +220,6 @@
return ps;
}
- private void radialSort(Coordinate[] p) {
-
- // A selection sort routine, assumes the pivot point is
- // the first point (i.e., p[0]).
- Coordinate t;
- for (int i = 1; i < (p.length - 1); i++) {
- int min = i;
- for (int j = i + 1; j < p.length; j++) {
- if (polarCompare(p[0], p[j], p[min]) < 0) {
- min = j;
- }
- }
- t = p[i];
- p[i] = p[min];
- p[min] = t;
- }
- }
-
- private int polarCompare(Coordinate o, Coordinate p, Coordinate q) {
-
- // Given two points p and q compare them with respect to their radial
- // ordering about point o. -1, 0 or 1 depending on whether p is less than,
- // equal to or greater than q. First checks radial ordering then if both
- // points lie on the same line, check distance to o.
- double dxp = p.x - o.x;
- double dyp = p.y - o.y;
- double dxq = q.x - o.x;
- double dyq = q.y - o.y;
- double alph = Math.atan2(dxp, dyp);
- double beta = Math.atan2(dxq, dyq);
- if (alph < beta) {
- return -1;
- }
- if (alph > beta) {
- return 1;
- }
- double op = dxp * dxp + dyp * dyp;
- double oq = dxq * dxq + dyq * dyq;
- if (op < oq) {
- return -1;
- }
- if (op > oq) {
- return 1;
- }
- return 0;
- }
-
/**
*@return whether the three coordinates are collinear and c2 lies between
* c1 and c3 inclusive
@@ -276,6 +247,84 @@
return false;
}
+ private Coordinate[] computeOctRing(Coordinate[] inputPts) {
+ Coordinate[] octPts = computeOctPts(inputPts);
+ CoordinateList coordList = new CoordinateList();
+ coordList.add(octPts, false);
+
+ // points must all lie in a line
+ if (coordList.size() < 3) {
+ return null;
+ }
+ coordList.closeRing();
+ return coordList.toCoordinateArray();
+ }
+
+ private Coordinate[] computeOctPts(Coordinate[] inputPts)
+ {
+ Coordinate[] pts = new Coordinate[8];
+ for (int j = 0; j < pts.length; j++) {
+ pts[j] = inputPts[0];
+ }
+ for (int i = 1; i < inputPts.length; i++) {
+ if (inputPts[i].x < pts[0].x) {
+ pts[0] = inputPts[i];
+ }
+ if (inputPts[i].x - inputPts[i].y < pts[1].x - pts[1].y) {
+ pts[1] = inputPts[i];
+ }
+ if (inputPts[i].y > pts[2].y) {
+ pts[2] = inputPts[i];
+ }
+ if (inputPts[i].x + inputPts[i].y > pts[3].x + pts[3].y) {
+ pts[3] = inputPts[i];
+ }
+ if (inputPts[i].x > pts[4].x) {
+ pts[4] = inputPts[i];
+ }
+ if (inputPts[i].x - inputPts[i].y > pts[5].x - pts[5].y) {
+ pts[5] = inputPts[i];
+ }
+ if (inputPts[i].y < pts[6].y) {
+ pts[6] = inputPts[i];
+ }
+ if (inputPts[i].x + inputPts[i].y < pts[7].x + pts[7].y) {
+ pts[7] = inputPts[i];
+ }
+ }
+ return pts;
+
+ }
+
+/*
+ // MD - no longer used, but keep for reference purposes
+ private Coordinate[] computeQuad(Coordinate[] inputPts) {
+ BigQuad bigQuad = bigQuad(inputPts);
+
+ // Build a linear ring defining a big poly.
+ ArrayList bigPoly = new ArrayList();
+ bigPoly.add(bigQuad.westmost);
+ if (! bigPoly.contains(bigQuad.northmost)) {
+ bigPoly.add(bigQuad.northmost);
+ }
+ if (! bigPoly.contains(bigQuad.eastmost)) {
+ bigPoly.add(bigQuad.eastmost);
+ }
+ if (! bigPoly.contains(bigQuad.southmost)) {
+ bigPoly.add(bigQuad.southmost);
+ }
+ // points must all lie in a line
+ if (bigPoly.size() < 3) {
+ return null;
+ }
+ // closing point
+ bigPoly.add(bigQuad.westmost);
+
+ Coordinate[] bigPolyArray = CoordinateArrays.toCoordinateArray(bigPoly);
+
+ return bigPolyArray;
+ }
+
private BigQuad bigQuad(Coordinate[] pts) {
BigQuad bigQuad = new BigQuad();
bigQuad.northmost = pts[0];
@@ -299,6 +348,14 @@
return bigQuad;
}
+ private static class BigQuad {
+ public Coordinate northmost;
+ public Coordinate southmost;
+ public Coordinate westmost;
+ public Coordinate eastmost;
+ }
+ */
+
/**
*@param vertices the vertices of a linear ring, which may or may not be
* flattened (i.e. vertices collinear)
@@ -310,12 +367,12 @@
coordinates = cleanRing(coordinates);
if (coordinates.length == 3) {
- return factory.createLineString(new Coordinate[]{coordinates[0], coordinates[1]});
+ return geomFactory.createLineString(new Coordinate[]{coordinates[0], coordinates[1]});
// return new LineString(new Coordinate[]{coordinates[0], coordinates[1]},
// geometry.getPrecisionModel(), geometry.getSRID());
}
- LinearRing linearRing = factory.createLinearRing(coordinates);
- return factory.createPolygon(linearRing, null);
+ LinearRing linearRing = geomFactory.createLinearRing(coordinates);
+ return geomFactory.createPolygon(linearRing, null);
}
/**
@@ -346,11 +403,85 @@
return (Coordinate[]) cleanedRing.toArray(cleanedRingCoordinates);
}
- private static class BigQuad {
- public Coordinate northmost;
- public Coordinate southmost;
- public Coordinate westmost;
- public Coordinate eastmost;
+
+ /**
+ * Compares {@link Coordinate}s for their angle and distance
+ * relative to an origin.
+ *
+ * @author Martin Davis
+ * @version 1.7
+ */
+ private static class RadialComparator
+ implements Comparator
+ {
+ private Coordinate origin;
+
+ public RadialComparator(Coordinate origin)
+ {
+ this.origin = origin;
+ }
+ public int compare(Object o1, Object o2)
+ {
+ Coordinate p1 = (Coordinate) o1;
+ Coordinate p2 = (Coordinate) o2;
+ return polarCompare(origin, p1, p2);
+ }
+
+ /**
+ * Given two points p and q compare them with respect to their radial
+ * ordering about point o. First checks radial ordering.
+ * If points are collinear, the comparison is based
+ * on their distance to the origin.
+ * <p>
+ * p < q iff
+ * <ul>
+ * <li>ang(o-p) < ang(o-q) (e.g. o-p-q is CCW)
+ * <li>or ang(o-p) == ang(o-q) && dist(o,p) < dist(o,q)
+ * </ul>
+ *
+ * @param o the origin
+ * @param p a point
+ * @param q another point
+ * @return -1, 0 or 1 depending on whether p is less than,
+ * equal to or greater than q
+ */
+ private static int polarCompare(Coordinate o, Coordinate p, Coordinate q)
+ {
+ double dxp = p.x - o.x;
+ double dyp = p.y - o.y;
+ double dxq = q.x - o.x;
+ double dyq = q.y - o.y;
+
+/*
+ // MD - non-robust
+ int result = 0;
+ double alph = Math.atan2(dxp, dyp);
+ double beta = Math.atan2(dxq, dyq);
+ if (alph < beta) {
+ result = -1;
+ }
+ if (alph > beta) {
+ result = 1;
+ }
+ if (result != 0) return result;
+ //*/
+
+ int orient = CGAlgorithms.computeOrientation(o, p, q);
+
+ if (orient == CGAlgorithms.COUNTERCLOCKWISE) return 1;
+ if (orient == CGAlgorithms.CLOCKWISE) return -1;
+
+ // points are collinear - check distance
+ double op = dxp * dxp + dyp * dyp;
+ double oq = dxq * dxq + dyq * dyq;
+ if (op < oq) {
+ return -1;
+ }
+ if (op > oq) {
+ return 1;
+ }
+ return 0;
+ }
+
}
-
-}
+}
\ No newline at end of file
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -1,67 +1,64 @@
-
-
-
/*
- * The JTS Topology Suite is a collection of Java classes that
- * implement the fundamental operations required to validate a given
- * geo-spatial data set to a known topological specification.
- *
- * Copyright (C) 2001 Vivid Solutions
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * For more information, contact:
- *
- * Vivid Solutions
- * Suite #1A
- * 2328 Government Street
- * Victoria BC V8T 5G5
- * Canada
- *
- * (250)385-6040
- * www.vividsolutions.com
+* The JTS Topology Suite is a collection of Java classes that
+* implement the fundamental operations required to validate a given
+* geo-spatial data set to a known topological specification.
+*
+* Copyright (C) 2001 Vivid Solutions
+*
+* This library is free software; you can redistribute it and/or
+* modify it under the terms of the GNU Lesser General Public
+* License as published by the Free Software Foundation; either
+* version 2.1 of the License, or (at your option) any later version.
+*
+* This library is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+* Lesser General Public License for more details.
+*
+* You should have received a copy of the GNU Lesser General Public
+* License along with this library; if not, write to the Free Software
+* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*
+* For more information, contact:
+*
+* Vivid Solutions
+* Suite #1A
+* 2328 Government Street
+* Victoria BC V8T 5G5
+* Canada
+*
+* (250)385-6040
+* www.vividsolutions.com
*/
package com.vividsolutions.jts.algorithm;
-/**
- * @version 1.6
- */
import com.vividsolutions.jts.geom.*;
/**
- * Represents a homogeneous coordinate for 2-D coordinates.
+ * Represents a homogeneous coordinate in a 2-D coordinate space.
+ * In JTS {@link HCoordinate}s are used as a clean way
+ * of computing intersections between line segments.
*
- * @version 1.6
+ * @author David Skea
+ * @version 1.7
*/
public class HCoordinate
{
-/**
- * Computes the (approximate) intersection point between two line segments
- * using homogeneous coordinates.
- * <p>
- * Note that this algorithm is
- * not numerically stable; i.e. it can produce intersection points which
- * lie outside the envelope of the line segments themselves. In order
- * to increase the precision of the calculation input points should be normalized
- * before passing them to this routine.
- */
+ /**
+ * Computes the (approximate) intersection point between two line segments
+ * using homogeneous coordinates.
+ * <p>
+ * Note that this algorithm is
+ * not numerically stable; i.e. it can produce intersection points which
+ * lie outside the envelope of the line segments themselves. In order
+ * to increase the precision of the calculation input points should be normalized
+ * before passing them to this routine.
+ */
public static Coordinate intersection(
Coordinate p1, Coordinate p2,
Coordinate q1, Coordinate q2)
- throws NotRepresentableException
+ throws NotRepresentableException
{
HCoordinate l1 = new HCoordinate(new HCoordinate(p1), new HCoordinate(p2));
HCoordinate l2 = new HCoordinate(new HCoordinate(q1), new HCoordinate(q2));
@@ -71,52 +68,58 @@
}
- public double x,y,w;
+ public double x,y,w;
- public HCoordinate() {
- x = 0.0;
- y = 0.0;
- w = 1.0;
- }
+ public HCoordinate() {
+ x = 0.0;
+ y = 0.0;
+ w = 1.0;
+ }
- public HCoordinate(double _x, double _y, double _w) {
- x = _x;
- y = _y;
- w = _w;
- }
+ public HCoordinate(double _x, double _y, double _w) {
+ x = _x;
+ y = _y;
+ w = _w;
+ }
- public HCoordinate(Coordinate p) {
- x = p.x;
- y = p.y;
- w = 1.0;
- }
+ public HCoordinate(double _x, double _y) {
+ x = _x;
+ y = _y;
+ w = 1.0;
+ }
- public HCoordinate(HCoordinate p1, HCoordinate p2) {
- x = p1.y*p2.w - p2.y*p1.w;
- y = p2.x*p1.w - p1.x*p2.w;
- w = p1.x*p2.y - p2.x*p1.y;
- }
+ public HCoordinate(Coordinate p) {
+ x = p.x;
+ y = p.y;
+ w = 1.0;
+ }
- public double getX() throws NotRepresentableException {
- double a = x/w;
- if ((Double.isNaN(a)) || (Double.isInfinite(a))) {
- throw new NotRepresentableException();
- }
- return a;
+ public HCoordinate(HCoordinate p1, HCoordinate p2) {
+ x = p1.y * p2.w - p2.y * p1.w;
+ y = p2.x * p1.w - p1.x * p2.w;
+ w = p1.x * p2.y - p2.x * p1.y;
+ }
+
+ public double getX() throws NotRepresentableException {
+ double a = x/w;
+ if ((Double.isNaN(a)) || (Double.isInfinite(a))) {
+ throw new NotRepresentableException();
}
+ return a;
+ }
- public double getY() throws NotRepresentableException {
- double a = y/w;
- if ((Double.isNaN(a)) || (Double.isInfinite(a))) {
- throw new NotRepresentableException();
- }
- return a;
+ public double getY() throws NotRepresentableException {
+ double a = y/w;
+ if ((Double.isNaN(a)) || (Double.isInfinite(a))) {
+ throw new NotRepresentableException();
}
+ return a;
+ }
- public Coordinate getCoordinate() throws NotRepresentableException {
- Coordinate p = new Coordinate();
- p.x = getX();
- p.y = getY();
- return p;
- }
-}
+ public Coordinate getCoordinate() throws NotRepresentableException {
+ Coordinate p = new Coordinate();
+ p.x = getX();
+ p.y = getY();
+ return p;
+ }
+}
\ No newline at end of file
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -52,7 +52,7 @@
* which does not lie in the interior.
* </b>
*
- * @version 1.6
+ * @version 1.7
*/
public class InteriorPointArea {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointLine.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointLine.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointLine.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -45,7 +45,7 @@
* closest to the centroid.
* </ul>
*
- * @version 1.6
+ * @version 1.7
*/
public class InteriorPointLine {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointPoint.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointPoint.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointPoint.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -40,7 +40,7 @@
* <h2>Algorithm</h2>
* Find a point which is closest to the centroid of the geometry.
*
- * @version 1.6
+ * @version 1.7
*/
public class InteriorPointPoint {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/LineIntersector.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/LineIntersector.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/LineIntersector.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -36,10 +36,11 @@
package com.vividsolutions.jts.algorithm;
/**
- * @version 1.6
+ * @version 1.7
*/
import com.vividsolutions.jts.geom.*;
import com.vividsolutions.jts.util.*;
+import com.vividsolutions.jts.io.WKTWriter;
/**
* A LineIntersector is an algorithm that can both test whether
@@ -50,7 +51,7 @@
* that the input coordinates have been made precise by scaling them to
* an integer grid.)
*
- * @version 1.6
+ * @version 1.7
*/
public abstract class LineIntersector {
@@ -208,23 +209,32 @@
Coordinate p1, Coordinate p2,
Coordinate q1, Coordinate q2);
+/*
public String toString() {
String str = inputLines[0][0] + "-"
+ inputLines[0][1] + " "
+ inputLines[1][0] + "-"
- + inputLines[1][1] + " : ";
- if (isEndPoint()) {
- str += " endpoint";
- }
- if (isProper) {
- str += " proper";
- }
- if (isCollinear()) {
- str += " collinear";
- }
+ + inputLines[1][1] + " : "
+ + getTopologySummary();
return str;
}
+*/
+ public String toString() {
+ return WKTWriter.toLineString(inputLines[0][0], inputLines[0][1]) + " - "
+ + WKTWriter.toLineString(inputLines[1][0], inputLines[1][1])
+ + getTopologySummary();
+ }
+
+ private String getTopologySummary()
+ {
+ StringBuffer catBuf = new StringBuffer();
+ if (isEndPoint()) catBuf.append(" endpoint");
+ if (isProper) catBuf.append(" proper");
+ if (isCollinear()) catBuf.append(" collinear");
+ return catBuf.toString();
+ }
+
protected boolean isEndPoint() {
return hasIntersection() && !isProper;
}
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MCPointInRing.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MCPointInRing.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MCPointInRing.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -36,7 +36,6 @@
import java.util.*;
import com.vividsolutions.jts.geom.*;
import com.vividsolutions.jts.index.chain.*;
-import com.vividsolutions.jts.index.strtree.*;
import com.vividsolutions.jts.index.bintree.*;
import com.vividsolutions.jts.index.bintree.Interval;
@@ -45,7 +44,7 @@
* using {@link MonotoneChain}s and a {@link BinTree} index to
* increase performance.
*
- * @version 1.6
+ * @version 1.7
*/
public class MCPointInRing implements PointInRing {
@@ -76,7 +75,7 @@
private void buildIndex()
{
- Envelope env = ring.getEnvelopeInternal();
+ //Envelope env = ring.getEnvelopeInternal();
tree = new Bintree();
Coordinate[] pts = CoordinateArrays.removeRepeatedPoints(ring.getCoordinates());
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MinimumDiameter.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MinimumDiameter.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/MinimumDiameter.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -51,7 +51,7 @@
*
* @see ConvexHull
*
- * @version 1.6
+ * @version 1.7
*/
public class MinimumDiameter
{
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustCGAlgorithms.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustCGAlgorithms.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustCGAlgorithms.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -40,7 +40,7 @@
* <b>FOR TESTING PURPOSES ONLY!</b>.
* The non-robustness is due to rounding error in floating point computation.
*
- * @version 1.6
+ * @version 1.7
*/
public class NonRobustCGAlgorithms
extends CGAlgorithms
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustLineIntersector.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustLineIntersector.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NonRobustLineIntersector.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -36,7 +36,7 @@
import com.vividsolutions.jts.algorithm.LineIntersector;
/**
- *@version 1.6
+ *@version 1.7
*/
import com.vividsolutions.jts.geom.*;
@@ -45,7 +45,7 @@
/**
* A non-robust version of {@LineIntersector}.
*
- * @version 1.6
+ * @version 1.7
*/
public class NonRobustLineIntersector
extends LineIntersector
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NotRepresentableException.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NotRepresentableException.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/NotRepresentableException.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -39,7 +39,7 @@
* Indicates that a {@link HCoordinate} has been computed which is
* not representable on the Cartesian plane.
*
- * @version 1.6
+ * @version 1.7
* @see HCoordinate
*/
public class NotRepresentableException extends Exception {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointInRing.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointInRing.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointInRing.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -39,7 +39,7 @@
* An interface for classes which test whether a {@link Coordinate} lies inside
* a ring.
*
- * @version 1.6
+ * @version 1.7
*/
public interface PointInRing {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointLocator.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointLocator.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/PointLocator.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -41,15 +41,16 @@
/**
* Computes the topological relationship ({@link Location})
- * of a single point to a Geometry.
- * The algorithm obeys the SFS boundaryDetermination rule to correctly determine
+ * of a single point to a {@link Geometry}.
+ * The algorithm obeys the SFS Boundary Determination Rule to determine
* whether the point lies on the boundary or not.
- * Note that instances of this class are not reentrant.
- * @version 1.6
+ * <p>
+ * Instances of this class are not reentrant.
+ *
+ * @version 1.7
*/
-public class PointLocator {
-
-
+public class PointLocator
+{
private boolean isIn; // true if the point lies in or on any Geometry element
private int numBoundaries; // the number of sub-elements whose boundaries the point lies in
@@ -74,7 +75,7 @@
* It handles both single-element
* and multi-element Geometries.
* The algorithm for multi-part Geometries
- * takes into account the boundaryDetermination rule.
+ * takes into account the SFS Boundary Determination Rule.
*
* @return the {@link Location} of the point relative to the input Geometry
*/
@@ -82,12 +83,12 @@
{
if (geom.isEmpty()) return Location.EXTERIOR;
- if (geom instanceof LineString) {
- return locate(p, (LineString) geom);
- }
if (geom instanceof LinearRing) {
return locate(p, (LinearRing) geom);
}
+ if (geom instanceof LineString) {
+ return locate(p, (LineString) geom);
+ }
else if (geom instanceof Polygon) {
return locate(p, (Polygon) geom);
}
@@ -102,12 +103,12 @@
private void computeLocation(Coordinate p, Geometry geom)
{
- if (geom instanceof LineString) {
- updateLocationInfo(locate(p, (LineString) geom));
- }
if (geom instanceof LinearRing) {
updateLocationInfo(locate(p, (LinearRing) geom));
}
+ if (geom instanceof LineString) {
+ updateLocationInfo(locate(p, (LineString) geom));
+ }
else if (geom instanceof Polygon) {
updateLocationInfo(locate(p, (Polygon) geom));
}
@@ -183,6 +184,4 @@
}
return Location.INTERIOR;
}
-
-
}
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustCGAlgorithms.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustCGAlgorithms.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustCGAlgorithms.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -40,7 +40,7 @@
* Stub version of RobustCGAlgorithms for backwards compatibility.
* Will be deprecated in next release - use CGAlgorithms instead.
*
- * @version 1.6
+ * @version 1.7
*
*/
public class RobustCGAlgorithms extends CGAlgorithms {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustDeterminant.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustDeterminant.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustDeterminant.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -35,7 +35,7 @@
package com.vividsolutions.jts.algorithm;
/**
- * @version 1.6
+ * @version 1.7
*/
/**
@@ -59,7 +59,7 @@
**************************************************************************
* </pre>
*
- * @version 1.6
+ * @version 1.7
*/
public class RobustDeterminant {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustLineIntersector.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustLineIntersector.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/RobustLineIntersector.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -35,7 +35,7 @@
package com.vividsolutions.jts.algorithm;
/**
- *@version 1.6
+ *@version 1.7
*/
import com.vividsolutions.jts.geom.*;
@@ -44,7 +44,7 @@
/**
* A robust version of {@LineIntersector}.
*
- * @version 1.6
+ * @version 1.7
* @see RobustDeterminant
*/
public class RobustLineIntersector
@@ -200,7 +200,7 @@
Coordinate n3 = new Coordinate(q1);
Coordinate n4 = new Coordinate(q2);
Coordinate normPt = new Coordinate();
- normalize(n1, n2, n3, n4, normPt);
+ normalizeToEnvCentre(n1, n2, n3, n4, normPt);
Coordinate intPt = null;
try {
@@ -213,21 +213,53 @@
intPt.x += normPt.x;
intPt.y += normPt.y;
+ /**
+ *
+ * MD - May 4 2005 - This is still a problem. Here is a failure case:
+ *
+ * LINESTRING (2089426.5233462777 1180182.3877339689, 2085646.6891757075 1195618.7333999649)
+ * LINESTRING (1889281.8148903656 1997547.0560044837, 2259977.3672235999 483675.17050843034)
+ * int point = (2097408.2633752143,1144595.8008114607)
+ */
+ if (! isInSegmentEnvelopes(intPt)) {
+ System.out.println("Intersection outside segment envelopes: " + intPt);
+ }
+ /*
+ // disabled until a better solution is found
+ if (! isInSegmentEnvelopes(intPt)) {
+ System.out.println("first value outside segment envelopes: " + intPt);
+
+ IteratedBisectionIntersector ibi = new IteratedBisectionIntersector(p1, p2, q1, q2);
+ intPt = ibi.getIntersection();
+ }
+ if (! isInSegmentEnvelopes(intPt)) {
+ System.out.println("ERROR - outside segment envelopes: " + intPt);
+
+ IteratedBisectionIntersector ibi = new IteratedBisectionIntersector(p1, p2, q1, q2);
+ Coordinate testPt = ibi.getIntersection();
+ }
+ */
+
if (precisionModel != null) {
precisionModel.makePrecise(intPt);
}
- /**
- * MD - after fairly extensive testing
- * it appears that the computed intPt always lies in the segment envelopes
- */
- //if (! isInSegmentEnvelopes(intPt))
- // System.out.println("outside segment envelopes: " + intPt);
-
return intPt;
}
- private void normalize(
+ /**
+ * Normalize the supplied coordinates so that
+ * their minimum ordinate values lie at the origin.
+ * NOTE: this normalization technique appears to cause
+ * large errors in the position of the intersection point for some cases.
+ *
+ * @param n1
+ * @param n2
+ * @param n3
+ * @param n4
+ * @param normPt
+ */
+ private void normalizeToMinimum(
Coordinate n1,
Coordinate n2,
Coordinate n3,
@@ -242,6 +274,61 @@
n4.x -= normPt.x; n4.y -= normPt.y;
}
+ /**
+ * Normalize the supplied coordinates to
+ * so that the midpoint of their intersection envelope
+ * lies at the origin.
+ *
+ * @param n00
+ * @param n01
+ * @param n10
+ * @param n11
+ * @param normPt
+ */
+ private void normalizeToEnvCentre(
+ Coordinate n00,
+ Coordinate n01,
+ Coordinate n10,
+ Coordinate n11,
+ Coordinate normPt)
+ {
+ double minX0 = n00.x < n01.x ? n00.x : n01.x;
+ double minY0 = n00.y < n01.y ? n00.y : n01.y;
+ double maxX0 = n00.x > n01.x ? n00.x : n01.x;
+ double maxY0 = n00.y > n01.y ? n00.y : n01.y;
+
+ double minX1 = n10.x < n11.x ? n10.x : n11.x;
+ double minY1 = n10.y < n11.y ? n10.y : n11.y;
+ double maxX1 = n10.x > n11.x ? n10.x : n11.x;
+ double maxY1 = n10.y > n11.y ? n10.y : n11.y;
+
+ double intMinX = minX0 > minX1 ? minX0 : minX1;
+ double intMaxX = maxX0 < maxX1 ? maxX0 : maxX1;
+ double intMinY = minY0 > minY1 ? minY0 : minY1;
+ double intMaxY = maxY0 < maxY1 ? maxY0 : maxY1;
+
+ double intMidX = (intMinX + intMaxX) / 2.0;
+ double intMidY = (intMinY + intMaxY) / 2.0;
+ normPt.x = intMidX;
+ normPt.y = intMidY;
+
+ /*
+ // equilavalent code using more modular but slower method
+ Envelope env0 = new Envelope(n00, n01);
+ Envelope env1 = new Envelope(n10, n11);
+ Envelope intEnv = env0.intersection(env1);
+ Coordinate intMidPt = intEnv.centre();
+
+ normPt.x = intMidPt.x;
+ normPt.y = intMidPt.y;
+ */
+
+ n00.x -= normPt.x; n00.y -= normPt.y;
+ n01.x -= normPt.x; n01.y -= normPt.y;
+ n10.x -= normPt.x; n10.y -= normPt.y;
+ n11.x -= normPt.x; n11.y -= normPt.y;
+ }
+
private double smallestInAbsValue(double x1, double x2, double x3, double x4)
{
double x = x1;
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SIRtreePointInRing.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SIRtreePointInRing.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SIRtreePointInRing.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -42,7 +42,7 @@
* using a {@link SIRtree} index to
* increase performance.
*
- * @version 1.6
+ * @version 1.7
*/
public class SIRtreePointInRing implements PointInRing {
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInAreaLocator.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInAreaLocator.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInAreaLocator.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -44,7 +44,7 @@
* The algorithm used is only guaranteed to return correct results
* for points which are <b>not</b> on the boundary of the Geometry.
*
- * @version 1.6
+ * @version 1.7
*/
public class SimplePointInAreaLocator
{
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInRing.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInRing.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/SimplePointInRing.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -39,7 +39,7 @@
* Tests whether a {@link Coordinate} lies inside
* a ring, using a linear-time algorithm.
*
- * @version 1.6
+ * @version 1.7
*/
public class SimplePointInRing
implements PointInRing
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/package.html
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/package.html 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/package.html 2007-06-15 22:22:06 UTC (rev 892)
@@ -8,37 +8,33 @@
<body bgcolor="white">
Contains classes and interfaces implementing fundamental computational geometry algorithms.
-<P>
-The Java Topology Suite (JTS) is a Java API that implements a core set of spatial data operations using an explicit precision model and robust geometric algorithms. JTS is intended to be used in the development of applications that support the validation, cleaning, integration and querying of spatial datasets.
-<P>
-JTS attempts to implement the OpenGIS Simple Features Specification (SFS) as accurately as possible. In some cases the SFS is unclear or omits a specification; in this case JTS attempts to choose a reasonable and consistent alternative. Differences from and elaborations of the SFS are documented in this specification.
<H3>Robustness</H3>
-Geometrical algorithms involve a combination of combinatorial and numerical computation. As with
-all numerical computation using finite-precision numbers, the algorithms chosen are susceptible to
-problems of robustness. A robustness problem occurs when a numerical calculation produces an
-incorrect answer for some inputs due to round-off errors. Robustness problems are especially
+Geometrical algorithms involve a combination of combinatorial and numerical computation. As with
+all numerical computation using finite-precision numbers, the algorithms chosen are susceptible to
+problems of robustness. A robustness problem occurs when a numerical calculation produces an
+incorrect answer for some inputs due to round-off errors. Robustness problems are especially
serious in geometric computation, since they can result in errors during topology building.
<P>
-There are many approaches to dealing with the problem of robustness in geometrical computation.
-Not surprisingly, most robust algorithms are substantially more complex and less performant than
-the non-robust versions. Fortunately, JTS is sensitive to robustness problems in only a few key
-functions (such as line intersection and the point-in-polygon test). There are efficient robust
+There are many approaches to dealing with the problem of robustness in geometrical computation.
+Not surprisingly, most robust algorithms are substantially more complex and less performant than
+the non-robust versions. Fortunately, JTS is sensitive to robustness problems in only a few key
+functions (such as line intersection and the point-in-polygon test). There are efficient robust
algorithms available for these functions, and these algorithms are implemented in JTS.
<H3>Computational Performance</H3>
-Runtime performance is an important consideration for a production-quality implementation of
-geometric algorithms. The most computationally intensive algorithm used in JTS is intersection
-detection. JTS methods need to determine both all intersection between the line segments in a
-single Geometry (self-intersection) and all intersections between the line segments of two different
-Geometries.
+Runtime performance is an important consideration for a production-quality implementation of
+geometric algorithms. The most computationally intensive algorithm used in JTS is intersection
+detection. JTS methods need to determine both all intersection between the line segments in a
+single Geometry (self-intersection) and all intersections between the line segments of two different
+Geometries.
<P>
-The obvious naive algorithm for intersection detection (comparing every segment with every other)
-has unacceptably slow performance. There is a large literature of faster algorithms for intersection
-detection. Unfortunately, many of them involve substantial code complexity. JTS tries to balance code
-simplicity with performance gains. It uses some simple techniques to produce substantial performance
+The obvious naive algorithm for intersection detection (comparing every segment with every other)
+has unacceptably slow performance. There is a large literature of faster algorithms for intersection
+detection. Unfortunately, many of them involve substantial code complexity. JTS tries to balance code
+simplicity with performance gains. It uses some simple techniques to produce substantial performance
gains for common types of input data.
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Coordinate.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Coordinate.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/Coordinate.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -1,39 +1,39 @@
/*
- * The JTS Topology Suite is a collection of Java classes that
- * implement the fundamental operations required to validate a given
- * geo-spatial data set to a known topological specification.
- *
- * Copyright (C) 2001 Vivid Solutions
- *
- * This library is free software; you can redistribute it and/or
- * modify it under the terms of the GNU Lesser General Public
- * License as published by the Free Software Foundation; either
- * version 2.1 of the License, or (at your option) any later version.
- *
- * This library is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * Lesser General Public License for more details.
- *
- * You should have received a copy of the GNU Lesser General Public
- * License along with this library; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
- *
- * For more information, contact:
- *
- * Vivid Solutions
- * Suite #1A
- * 2328 Government Street
- * Victoria BC V8T 5G5
- * Canada
- *
- * (250)385-6040
- * www.vividsolutions.com
+* The JTS Topology Suite is a collection of Java classes that
+* implement the fundamental operations required to validate a given
+* geo-spatial data set to a known topological specification.
+*
+* Copyright (C) 2001 Vivid Solutions
+*
+* This library is free software; you can redistribute it and/or
+* modify it under the terms of the GNU Lesser General Public
+* License as published by the Free Software Foundation; either
+* version 2.1 of the License, or (at your option) any later version.
+*
+* This library is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+* Lesser General Public License for more details.
+*
+* You should have received a copy of the GNU Lesser General Public
+* License along with this library; if not, write to the Free Software
+* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+*
+* For more information, contact:
+*
+* Vivid Solutions
+* Suite #1A
+* 2328 Government Street
+* Victoria BC V8T 5G5
+* Canada
+*
+* (250)385-6040
+* www.vividsolutions.com
*/
package com.vividsolutions.jts.geom;
import java.io.Serializable;
-
+import java.util.Comparator;
import com.vividsolutions.jts.util.Assert;
@@ -52,221 +52,281 @@
* z-ordinate of <code>NaN</code>. The standard comparison functions will ignore
* the z-ordinate.
*
- *@version 1.6
+ *@version 1.7
*/
public class Coordinate implements Comparable, Cloneable, Serializable {
- private static final long serialVersionUID = 6683108902428366910L;
- /**
- * The x-coordinate.
- */
- public double x;
- /**
- * The y-coordinate.
- */
- public double y;
- /**
- * The z-coordinate.
- */
- public double z;
+ private static final long serialVersionUID = 6683108902428366910L;
+ /**
+ * The x-coordinate.
+ */
+ public double x;
+ /**
+ * The y-coordinate.
+ */
+ public double y;
+ /**
+ * The z-coordinate.
+ */
+ public double z;
- /**
- * Constructs a <code>Coordinate</code> at (x,y,z).
- *
- *@param x the x-value
- *@param y the y-value
- *@param z the z-value
- */
- public Coordinate(double x, double y, double z) {
- this.x = x;
- this.y = y;
- this.z = z;
- }
+ /**
+ * Constructs a <code>Coordinate</code> at (x,y,z).
+ *
+ *@param x the x-value
+ *@param y the y-value
+ *@param z the z-value
+ */
+ public Coordinate(double x, double y, double z) {
+ this.x = x;
+ this.y = y;
+ this.z = z;
+ }
- /**
- * Constructs a <code>Coordinate</code> at (0,0,NaN).
- */
- public Coordinate() {
- this(0.0, 0.0);
+ /**
+ * Constructs a <code>Coordinate</code> at (0,0,NaN).
+ */
+ public Coordinate() {
+ this(0.0, 0.0);
+ }
+
+ /**
+ * Constructs a <code>Coordinate</code> having the same (x,y,z) values as
+ * <code>other</code>.
+ *
+ *@param c the <code>Coordinate</code> to copy.
+ */
+ public Coordinate(Coordinate c) {
+ this(c.x, c.y, c.z);
+ }
+
+ /**
+ * Constructs a <code>Coordinate</code> at (x,y,NaN).
+ *
+ *@param x the x-value
+ *@param y the y-value
+ */
+ public Coordinate(double x, double y) {
+ this(x, y, Double.NaN);
+ }
+
+
+
+ /**
+ * Sets this <code>Coordinate</code>s (x,y,z) values to that of <code>other</code>
+ * .
+ *
+ *@param other the <code>Coordinate</code> to copy
+ */
+ public void setCoordinate(Coordinate other) {
+ x = other.x;
+ y = other.y;
+ z = other.z;
+ }
+
+ /**
+ * Returns whether the planar projections of the two <code>Coordinate</code>s
+ * are equal.
+ *
+ *@param other a <code>Coordinate</code> with which to do the 2D comparison.
+ *@return <code>true</code> if the x- and y-coordinates are equal; the
+ * z-coordinates do not have to be equal.
+ */
+ public boolean equals2D(Coordinate other) {
+ if (x != other.x) {
+ return false;
}
- /**
- * Constructs a <code>Coordinate</code> having the same (x,y,z) values as
- * <code>other</code>.
- *
- *@param c the <code>Coordinate</code> to copy.
- */
- public Coordinate(Coordinate c) {
- this(c.x, c.y, c.z);
+ if (y != other.y) {
+ return false;
}
- /**
- * Constructs a <code>Coordinate</code> at (x,y,NaN).
- *
- *@param x the x-value
- *@param y the y-value
- */
- public Coordinate(double x, double y) {
- this(x, y, Double.NaN);
+ return true;
+ }
+
+ /**
+ * Returns <code>true</code> if <code>other</code> has the same values for
+ * the x and y ordinates.
+ * Since Coordinates are 2.5D, this routine ignores the z value when making the comparison.
+ *
+ *@param other a <code>Coordinate</code> with which to do the comparison.
+ *@return <code>true</code> if <code>other</code> is a <code>Coordinate</code>
+ * with the same values for the x and y ordinates.
+ */
+ public boolean equals(Object other) {
+ if (!(other instanceof Coordinate)) {
+ return false;
}
+ return equals2D((Coordinate) other);
+ }
+ /**
+ * Compares this {@link Coordinate} with the specified {@link Coordinate} for order.
+ * This method ignores the z value when making the comparison.
+ * Returns:
+ * <UL>
+ * <LI> -1 : this.x < other.x || ((this.x == other.x) && (this.y <
+ * other.y))
+ * <LI> 0 : this.x == other.x && this.y = other.y
+ * <LI> 1 : this.x > other.x || ((this.x == other.x) && (this.y > other.y))
+ *
+ * </UL>
+ * Note: This method assumes that ordinate values
+ * are valid numbers. NaN values are not handled correctly.
+ *
+ *@param o the <code>Coordinate</code> with which this <code>Coordinate</code>
+ * is being compared
+ *@return -1, zero, or 1 as this <code>Coordinate</code>
+ * is less than, equal to, or greater than the specified <code>Coordinate</code>
+ */
+ public int compareTo(Object o) {
+ Coordinate other = (Coordinate) o;
+ if (x < other.x) return -1;
+ if (x > other.x) return 1;
+ if (y < other.y) return -1;
+ if (y > other.y) return 1;
+ return 0;
+ }
- /**
- * Sets this <code>Coordinate</code>s (x,y,z) values to that of <code>other</code>
- * .
- *
- *@param other the <code>Coordinate</code> to copy
- */
- public void setCoordinate(Coordinate other) {
- x = other.x;
- y = other.y;
- z = other.z;
- }
+ /**
+ * Returns <code>true</code> if <code>other</code> has the same values for x,
+ * y and z.
+ *
+ *@param other a <code>Coordinate</code> with which to do the 3D comparison.
+ *@return <code>true</code> if <code>other</code> is a <code>Coordinate</code>
+ * with the same values for x, y and z.
+ */
+ public boolean equals3D(Coordinate other) {
+ return (x == other.x) && (y == other.y) &&
+ ((z == other.z) ||
+ (Double.isNaN(z) && Double.isNaN(other.z)));
+ }
- /**
- * Returns whether the planar projections of the two <code>Coordinate</code>s
- * are equal.
- *
- *@param other a <code>Coordinate</code> with which to do the 2D comparison.
- *@return <code>true</code> if the x- and y-coordinates are equal; the
- * z-coordinates do not have to be equal.
- */
- public boolean equals2D(Coordinate other) {
- if (x != other.x) {
- return false;
- }
+ /**
+ * Returns a <code>String</code> of the form <I>(x,y,z)</I> .
+ *
+ *@return a <code>String</code> of the form <I>(x,y,z)</I>
+ */
+ public String toString() {
+ return "(" + x + ", " + y + ", " + z + ")";
+ }
- if (y != other.y) {
- return false;
- }
+ public Object clone() {
+ try {
+ Coordinate coord = (Coordinate) super.clone();
- return true;
- }
+ return coord; // return the clone
+ } catch (CloneNotSupportedException e) {
+ Assert.shouldNeverReachHere(
+ "this shouldn't happen because this class is Cloneable");
- /**
- * Returns <code>true</code> if <code>other</code> has the same values for
- * the x and y ordinates.
- * Since Coordinates are 2.5D, this routine ignores the z value when making the comparison.
- *
- *@param other a <code>Coordinate</code> with which to do the comparison.
- *@return <code>true</code> if <code>other</code> is a <code>Coordinate</code>
- * with the same values for the x and y ordinates.
- */
- public boolean equals(Object other) {
- if (!(other instanceof Coordinate)) {
- return false;
- }
- return equals2D((Coordinate) other);
+ return null;
}
+ }
+ public double distance(Coordinate p) {
+ double dx = x - p.x;
+ double dy = y - p.y;
+
+ return Math.sqrt(dx * dx + dy * dy);
+ }
+
+ public int hashCode() {
+ //Algorithm from Effective Java by Joshua Bloch [Jon Aquino]
+ int result = 17;
+ result = 37 * result + hashCode(x);
+ result = 37 * result + hashCode(y);
+ return result;
+ }
+
+ /**
+ * Returns a hash code for a double value, using the algorithm from
+ * Joshua Bloch's book <i>Effective Java"</i>
+ */
+ public static int hashCode(double x) {
+ long f = Double.doubleToLongBits(x);
+ return (int)(f^(f>>>32));
+ }
+
+
+ /**
+ * Compares two {@link Coordinate}s, allowing for either a 2-dimensional
+ * or 3-dimensional comparison, and handling NaN values correctly.
+ */
+ public static class DimensionalComparator
+ implements Comparator
+ {
/**
- * Compares this object with the specified object for order.
- * Since Coordinates are 2.5D, this routine ignores the z value when making the comparison.
- * Returns
- * <UL>
- * <LI> -1 : this.x < other.x || ((this.x == other.x) && (this.y <
- * other.y))
- * <LI> 0 : this.x == other.x && this.y = other.y
- * <LI> 1 : this.x > other.x || ((this.x == other.x) && (this.y > other.y))
+ * Compare two <code>double</code>s, allowing for NaN values.
+ * NaN is treated as being less than any valid number.
*
- * </UL>
- *
- *
- *@param o the <code>Coordinate</code> with which this <code>Coordinate</code>
- * is being compared
- *@return a negative integer, zero, or a positive integer as this <code>Coordinate</code>
- * is less than, equal to, or greater than the specified <code>Coordinate</code>
+ * @param a a <code>double</code>
+ * @param b a <code>double</code>
+ * @return -1, 0, or 1 depending on whether a is less than, equal to or greater than b
*/
- public int compareTo(Object o) {
- Coordinate other = (Coordinate) o;
+ public static int compare(double a, double b)
+ {
+ if (a < b) return -1;
+ if (a > b) return 1;
- if (x < other.x) {
- return -1;
- }
+ if (Double.isNaN(a)) {
+ if (Double.isNaN(b)) return 0;
+ return -1;
+ }
- if (x > other.x) {
- return 1;
- }
+ if (Double.isNaN(b)) return 1;
+ return 0;
+ }
- if (y < other.y) {
- return -1;
- }
+ private int dimensionsToTest = 2;
- if (y > other.y) {
- return 1;
- }
-
- return 0;
+ /**
+ * Creates a comparator for 2 dimensional coordinates.
+ */
+ public DimensionalComparator()
+ {
+ this(2);
}
/**
- * Returns <code>true</code> if <code>other</code> has the same values for x,
- * y and z.
+ * Creates a comparator for 2 or 3 dimensional coordinates, depending
+ * on the value provided.
*
- *@param other a <code>Coordinate</code> with which to do the 3D comparison.
- *@return <code>true</code> if <code>other</code> is a <code>Coordinate</code>
- * with the same values for x, y and z.
+ * @param dimensionLimit the number of dimensions to test
*/
- public boolean equals3D(Coordinate other) {
- return (x == other.x) && (y == other.y) &&
- ((z == other.z) ||
- (Double.isNaN(z) && Double.isNaN(other.z)));
+ public DimensionalComparator(int dimensionsToTest)
+ {
+ if (dimensionsToTest != 2 && dimensionsToTest != 3)
+ throw new IllegalArgumentException("only 2 or 3 dimensions may be specified");
+ this.dimensionsToTest = dimensionsToTest;
}
/**
- * Returns a <code>String</code> of the form <I>(x,y,z)</I> .
+ * Compares two {@link Coordinate}s along to the number of
+ * dimensions specified.
*
- *@return a <code>String</code> of the form <I>(x,y,z)</I>
+ * @param o1 a {@link Coordinate}
+ * @param o2 a {link Coordinate}
+ * @return -1, 0, or 1 depending on whether o1 is less than,
+ * equal to, or greater than 02
+ *
*/
- public String toString() {
- return "(" + x + ", " + y + ", " + z + ")";
- }
+ public int compare(Object o1, Object o2)
+ {
+ Coordinate c1 = (Coordinate) o1;
+ Coordinate c2 = (Coordinate) o2;
- public Object clone() {
- try {
- Coordinate coord = (Coordinate) super.clone();
+ int compX = compare(c1.x, c2.x);
+ if (compX != 0) return compX;
- return coord; // return the clone
- } catch (CloneNotSupportedException e) {
- Assert.shouldNeverReachHere(
- "this shouldn't happen because this class is Cloneable");
+ int compY = compare(c1.y, c2.y);
+ if (compY != 0) return compY;
- return null;
- }
- }
+ if (dimensionsToTest <= 2) return 0;
- /**
- * "Fixes" this Coordinate to the PrecisionModel grid.
- */
-
- /*
- public void makePrecise(PrecisionModel precisionModel)
- {
- x = precisionModel.makePrecise(x);
- y = precisionModel.makePrecise(y);
- }
- */
- public double distance(Coordinate p) {
- double dx = x - p.x;
- double dy = y - p.y;
-
- return Math.sqrt(dx * dx + dy * dy);
+ int compZ = compare(c1.z, c2.z);
+ return compZ;
}
+ }
- public int hashCode() {
- //Algorithm from Effective Java by Joshua Bloch [Jon Aquino]
- int result = 17;
- result = 37 * result + hashCode(x);
- result = 37 * result + hashCode(y);
- return result;
- }
-
- /**
- * Returns a hash code for a double value, using the algorithm from
- * Joshua Bloch's book <i>Effective Java"</i>
- */
- public static int hashCode(double x) {
- long f = Double.doubleToLongBits(x);
- return (int)(f^(f>>>32));
- }
-}
+}
\ No newline at end of file
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateArrays.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateArrays.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateArrays.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -34,18 +34,176 @@
*/
package com.vividsolutions.jts.geom;
-import java.util.List;
+import java.util.*;
/**
* Useful utility functions for handling Coordinate arrays
*
- * @version 1.6
+ * @version 1.7
*/
public class CoordinateArrays {
private final static Coordinate[] coordArrayType = new Coordinate[0];
/**
+ * Finds a point in a list of points which is not contained in another list of points
+ * @param testPts the {@link Coordinate}s to test
+ * @param pts an array of {@link Coordinate}s to test the input points against
+ * @return a {@link Coordinate} from <code>testPts</code> which is not in <code>pts</code>, '
+ * or <code>null</code>
+ */
+ public static Coordinate ptNotInList(Coordinate[] testPts, Coordinate[] pts)
+ {
+ for (int i = 0; i < testPts.length; i++) {
+ Coordinate testPt = testPts[i];
+ if (CoordinateArrays.indexOf(testPt, pts) >= 0)
+ return testPt;
+ }
+ return null;
+ }
+
+ /**
+ * Compares two {@link Coordinate} arrays
+ * in the forward direction of their coordinates,
+ * using lexicographic ordering.
+ *
+ * @param pts1
+ * @param pts2
+ * @return
+ */
+ public static int compare(Coordinate[] pts1, Coordinate[] pts2) {
+ int i = 0;
+ while (i < pts1.length && i < pts2.length) {
+ int compare = pts1[i].compareTo(pts2[i]);
+ if (compare != 0)
+ return compare;
+ i++;
+ }
+ // handle situation when arrays are of different length
+ if (i < pts2.length) return -1;
+ if (i < pts1.length) return 1;
+
+ return 0;
+ }
+
+ /**
+ * A {@link Comparator} for {@link Coordinate} arrays
+ * in the forward direction of their coordinates,
+ * using lexicographic ordering.
+ */
+ public static class ForwardComparator
+ implements Comparator
+ {
+ public int compare(Object o1, Object o2) {
+ Coordinate[] pts1 = (Coordinate[]) o1;
+ Coordinate[] pts2 = (Coordinate[]) o2;
+
+ return CoordinateArrays.compare(pts1, pts2);
+ }
+ }
+
+
+ /**
+ * Determines which orientation of the {@link Coordinate} array
+ * is (overall) increasing.
+ * In other words, determines which end of the array is "smaller"
+ * (using the standard ordering on {@link Coordinate}).
+ * Returns an integer indicating the increasing direction.
+ * If the sequence is a palindrome, it is defined to be
+ * oriented in a positive direction.
+ *
+ * @param pts the array of Coordinates to test
+ * @return <code>1</code> if the array is smaller at the start
+ * or is a palindrome,
+ * <code>-1</code> if smaller at the end
+ */
+ public static int increasingDirection(Coordinate[] pts) {
+ for (int i = 0; i < pts.length / 2; i++) {
+ int j = pts.length - 1 - i;
+ // skip equal points on both ends
+ int comp = pts[i].compareTo(pts[j]);
+ if (comp != 0)
+ return comp;
+ }
+ // array must be a palindrome - defined to be in positive direction
+ return 1;
+ }
+
+ /**
+ * Determines whether two {@link Coordinate} arrays of equal length
+ * are equal in opposite directions.
+ *
+ * @param pts1
+ * @param pts2
+ * @return <code>true</code> if the two arrays are equal in opposite directions.
+ */
+ private static boolean isEqualReversed(Coordinate[] pts1, Coordinate[] pts2)
+ {
+ for (int i = 0; i < pts1.length; i++) {
+ Coordinate p1 = pts1[i];
+ Coordinate p2 = pts2[pts1.length - i - 1];
+ if (p1.compareTo(p2) != 0)
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * A {@link Comparator} for {@link Coordinate} arrays
+ * modulo their directionality.
+ * E.g. if two coordinate arrays are identical but reversed
+ * they will compare as equal under this ordering.
+ * If the arrays are not equal, the ordering returned
+ * is the ordering in the forward direction.
+ *
+ */
+ public static class BidirectionalComparator
+ implements Comparator
+ {
+ public int compare(Object o1, Object o2) {
+ Coordinate[] pts1 = (Coordinate[]) o1;
+ Coordinate[] pts2 = (Coordinate[]) o2;
+
+ if (pts1.length < pts2.length) return -1;
+ if (pts1.length > pts2.length) return 1;
+
+ if (pts1.length == 0) return 0;
+
+ int forwardComp = CoordinateArrays.compare(pts1, pts2);
+ boolean isEqualRev = isEqualReversed(pts1, pts2);
+ if (isEqualRev)
+ return 0;
+ return forwardComp;
+ }
+
+ public int OLDcompare(Object o1, Object o2) {
+ Coordinate[] pts1 = (Coordinate[]) o1;
+ Coordinate[] pts2 = (Coordinate[]) o2;
+
+ if (pts1.length < pts2.length) return -1;
+ if (pts1.length > pts2.length) return 1;
+
+ if (pts1.length == 0) return 0;
+
+ int dir1 = increasingDirection(pts1);
+ int dir2 = increasingDirection(pts2);
+
+ int i1 = dir1 > 0 ? 0 : pts1.length - 1;
+ int i2 = dir2 > 0 ? 0 : pts1.length - 1;
+
+ for (int i = 0; i < pts1.length; i++) {
+ int comparePt = pts1[i1].compareTo(pts2[i2]);
+ if (comparePt != 0)
+ return comparePt;
+ i1 += dir1;
+ i2 += dir2;
+ }
+ return 0;
+ }
+
+ }
+
+ /**
* Creates a deep copy of the argument {@link Coordinate) array.
*
* @param coordinates an array of Coordinates
@@ -60,9 +218,9 @@
}
/**
- * Converts the given List of Coordinates into a Coordinate array.
+ * Converts the given Collection of Coordinates into a Coordinate array.
*/
- public static Coordinate[] toCoordinateArray(List coordList)
+ public static Coordinate[] toCoordinateArray(Collection coordList)
{
return (Coordinate[]) coordList.toArray(coordArrayType);
}
@@ -135,6 +293,29 @@
}
/**
+ * Returns true if the two arrays are identical, both null, or pointwise
+ * equal, using a user-defined {@link Comparator} for {@link Coordinate} s
+ *
+ * @param coord1 an array of Coordinates
+ * @param coord2 an array of Coordinates
+ * @param coordinateComparator a Comparator for Coordinates
+ */
+ public static boolean equals(
+ Coordinate[] coord1,
+ Coordinate[] coord2,
+ Comparator coordinateComparator)
+ {
+ if (coord1 == coord2) return true;
+ if (coord1 == null || coord2 == null) return false;
+ if (coord1.length != coord2.length) return false;
+ for (int i = 0; i < coord1.length; i++) {
+ if (coordinateComparator.compare(coord1[i], coord2[i]) != 0)
+ return false;
+ }
+ return true;
+ }
+
+ /**
* Returns the minimum coordinate, using the usual lexicographic comparison.
*
*@param coordinates the array to search
@@ -185,4 +366,25 @@
return -1;
}
+ /**
+ * Extracts a subsequence of the input {@link Coordinate} array
+ * from indices <code>start</code> to
+ * <code>end</code> (inclusive).
+ *
+ * @param pts the input array
+ * @param start the index of the start of the subsequence to extract
+ * @param end the index of the end of the subsequence to extract
+ * @return a subsequence of the input array
+ */
+ public static Coordinate[] extract(Coordinate[] pts, int start, int end)
+ {
+ int len = end - start + 1;
+ Coordinate[] extractPts = new Coordinate[len];
+ int iPts = 0;
+ for (int i = start; i <= end; i++) {
+ extractPts[iPts++] = pts[i];
+ }
+ return extractPts;
+ }
+
}
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateFilter.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateFilter.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateFilter.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -45,7 +45,7 @@
* used to implement such things as coordinate transformations, centroid and
* envelope computation, and many other functions.
*
- *@version 1.6
+ *@version 1.7
*/
public interface CoordinateFilter {
@@ -54,6 +54,6 @@
*
*@param coord a <code>Coordinate</code> to which the filter is applied.
*/
- public void filter(Coordinate coord);
+ void filter(Coordinate coord);
}
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateList.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateList.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateList.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -43,7 +43,7 @@
* be set to prevent repeated coordinates from occuring in the list.
*
*
- * @version 1.6
+ * @version 1.7
*/
public class CoordinateList
extends ArrayList
@@ -83,7 +83,7 @@
public Coordinate getCoordinate(int i) { return (Coordinate) get(i); }
-
+
/** Add an array of coordinates
* @param coord The coordinates
* @param allowRepeated if set to false, repeated coordinates are collapsed
@@ -169,23 +169,24 @@
}
/** Returns the Coordinates in this collection.
- *
+ *
* @return the coordinates
*/
public Coordinate[] toCoordinateArray()
{
return (Coordinate[]) toArray(coordArrayType);
}
-
+
/**
- * Returns a deep copy of this collection.
- * @return The copied object
+ * Returns a deep copy of this <tt>CoordinateList</tt> instance.
+ *
+ * @return a clone of this <tt>CoordinateList</tt> instance
*/
public Object clone() {
- CoordinateList result = (CoordinateList) super.clone();
- for (int i=0; i<result.size(); i++) {
- this.add(i, ((Coordinate)this.get(i)).clone());
+ CoordinateList clone = (CoordinateList) super.clone();
+ for (int i = 0; i < this.size(); i++) {
+ clone.add(i, ((Coordinate) this.get(i)).clone());
}
- return result;
+ return clone;
}
}
Modified: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequence.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequence.java 2007-06-15 21:30:39 UTC (rev 891)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequence.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -53,7 +53,7 @@
* @see DefaultCoordinateSequenceFactory
* @see TwoArrayCoordinateSequenceFactory
*
- * @version 1.6
+ * @version 1.7
*/
public interface CoordinateSequence
extends Cloneable
@@ -61,12 +61,20 @@
/**
* Standard ordinate index values
*/
- public static final int X = 0;
- public static final int Y = 1;
- public static final int Z = 2;
- public static final int M = 3;
+ int X = 0;
+ int Y = 1;
+ int Z = 2;
+ int M = 3;
/**
+ * Returns the dimension (number of ordinates in each coordinate)
+ * for this sequence.
+ *
+ * @return the dimension of the sequence.
+ */
+ int getDimension();
+
+ /**
* Returns (possibly a copy of) the i'th coordinate in this sequence.
* Whether or not the Coordinate returned is the actual underlying
* Coordinate or merely a copy depends on the implementation.
@@ -79,7 +87,7 @@
* @param i the index of the coordinate to retrieve
* @return the i'th coordinate in the sequence
*/
- public Coordinate getCoordinate(int i);
+ Coordinate getCoordinate(int i);
/**
* Returns a copy of the i'th coordinate in this sequence.
@@ -90,7 +98,7 @@
* @param i the index of the coordinate to retrieve
* @return a copy of the i'th coordinate in the sequence
*/
- public Coordinate getCoordinateCopy(int i);
+ Coordinate getCoordinateCopy(int i);
/**
* Copies the i'th coordinate in the sequence to the supplied
@@ -99,7 +107,7 @@
* @param index the index of the coordinate to copy
* @param coord a {@link Coordinate} to receive the value
*/
- public void getCoordinate(int index, Coordinate coord);
+ void getCoordinate(int index, Coordinate coord);
/**
* Returns ordinate X (0) of the specified coordinate.
@@ -107,7 +115,7 @@
* @param index
* @return the value of the X ordinate in the index'th coordinate
*/
- public double getX(int index);
+ double getX(int index);
/**
* Returns ordinate Y (1) of the specified coordinate.
@@ -115,7 +123,7 @@
* @param index
* @return the value of the Y ordinate in the index'th coordinate
*/
- public double getY(int index);
+ double getY(int index);
/**
* Returns the ordinate of a coordinate in this sequence.
@@ -126,13 +134,13 @@
* @param index the coordinate index in the sequence
* @param ordinateIndex the ordinate index in the coordinate (in range [0, dimension-1])
*/
- public double getOrdinate(int index, int ordinateIndex);
+ double getOrdinate(int index, int ordinateIndex);
/**
* Returns the number of coordinates in this sequence.
* @return the size of the sequence
*/
- public int size();
+ int size();
/**
* Sets the value for a given ordinate of a coordinate in this sequence.
@@ -141,7 +149,7 @@
* @param ordinateIndex the ordinate index in the coordinate (in range [0, dimension-1])
* @param value the new ordinate value
*/
- public void setOrdinate(int index, int ordinateIndex, double value);
+ void setOrdinate(int index, int ordinateIndex, double value);
/**
* Returns (possibly copies of) the Coordinates in this collection.
@@ -153,7 +161,7 @@
*
* @return a array of coordinates containing the point values in this sequence
*/
- public Coordinate[] toCoordinateArray();
+ Coordinate[] toCoordinateArray();
/**
* Expands the given {@link Envelope} to include the coordinates in the sequence.
@@ -162,7 +170,7 @@
* @param env the envelope to expand
* @return a ref to the expanded envelope
*/
- public Envelope expandEnvelope(Envelope env);
+ Envelope expandEnvelope(Envelope env);
/**
* Returns a deep copy of this collection.
@@ -170,5 +178,5 @@
*
* @return a copy of the coordinate sequence containing copies of all points
*/
- public Object clone();
-}
+ Object clone();
+}
\ No newline at end of file
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequenceComparator.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequenceComparator.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/CoordinateSequenceComparator.java 2007-06-15 22:22:06 UTC (rev 892)
@@ -0,0 +1,130 @@
+package com.vividsolutions.jts.geom;
+
+import java.util.Comparator;
+
+/**
+ * Compares two {@link CoordinateSequence}s.
+ * For sequences of the same dimension, the ordering is lexicographic.
+ * Otherwise, lower dimensions are sorted before higher.
+ * The dimensions compared can be limited; if this is done
+ * ordinate dimensions above the limit will not be compared.
+ * <p>
+ * If different behaviour is required for comparing size, dimension, or
+ * coordinate values, any or all methods can be overridden.
+ *
+ */
+public class CoordinateSequenceComparator
+ implements Comparator
+{
+ /**
+ * Compare two <code>double</code>s, allowing for NaN values.
+ * NaN is treated as being less than any valid number.
+ *
+ * @param a a <code>double</code>
+ * @param b a <code>double</code>
+ * @return -1, 0, or 1 depending on whether a is less than, equal to or greater than b
+ */
+ public static int compare(double a, double b)
+ {
+ if (a < b) return -1;
+ if (a > b) return 1;
+
+ if (Double.isNaN(a)) {
+ if (Double.isNaN(b)) return 0;
+ return -1;
+ }
+
+ if (Double.isNaN(b)) return 1;
+ return 0;
+ }
+
+ /**
+ * The number of dimensions to test
+ */
+ protected int dimensionLimit;
+
+ /**
+ * Creates a comparator which will test all dimensions.
+ */
+ public CoordinateSequenceComparator()
+ {
+ dimensionLimit = Integer.MAX_VALUE;
+ }
+
+ /**
+ * Creates a comparator which will test only the specified number of dimensions.
+ *
+ * @param dimensionLimit the number of dimensions to test
+ */
+ public CoordinateSequenceComparator(int dimensionLimit)
+ {
+ this.dimensionLimit = dimensionLimit;
+ }
+
+ /**
+ * Compares two {@link CoordinateSequence}s for relative order.
+ *
+ * @param o1 a {@link CoordinateSequence}
+ * @param o2 a {@link CoordinateSequence}
+ * @return -1, 0, or 1 depending on whether o1 is less than, equal to, or greater than o2
+ */
+ public int compare(Object o1, Object o2)
+ {
+ CoordinateSequence s1 = (CoordinateSequence) o1;
+ CoordinateSequence s2 = (CoordinateSequence) o2;
+
+ int size1 = s1.size();
+ int size2 = s2.size();
+
+ int dim1 = s1.getD