[DebianGIS-dev] r877 - in packages: . jts jts/branches jts/branches/upstream jts/branches/upstream/current jts/branches/upstream/current/bin jts/branches/upstream/current/doc jts/branches/upstream/current/src jts/branches/upstream/current/src/com jts/branches/upstream/current/src/com/vividsolutions jts/branches/upstream/current/src/com/vividsolutions/jts jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm jts/branches/upstream/current/src/com/vividsolutions/jts/geom jts/branches/upstream/current/src/com/vividsolutions/jts/geom/impl jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/index jts/branches/upstream/current/src/com/vividsolutions/jts/index jts/branches/upstream/current/src/com/vividsolutions/jts/index/bintree jts/branches/upstream/current/src/com/vividsolutions/jts/index/chain jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree jts/branches/upstream/current/src/com/vividsolutions/jts/index/sweepline jts/branches/upstream/current/src/com/vividsolutions/jts/io jts/branches/upstream/current/src/com/vividsolutions/jts/noding jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround jts/branches/upstream/current/src/com/vividsolutions/jts/operation jts/branches/upstream/current/src/com/vividsolutions/jts/operation/buffer jts/branches/upstream/current/src/com/vividsolutions/jts/operation/distance jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge jts/branches/upstream/current/src/com/vividsolutions/jts/operation/overlay jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize jts/branches/upstream/current/src/com/vividsolutions/jts/operation/predicate jts/branches/upstream/current/src/com/vividsolutions/jts/operation/relate jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph jts/branches/upstream/current/src/com/vividsolutions/jts/polygonize jts/branches/upstream/current/src/com/vividsolutions/jts/precision jts/branches/upstream/current/src/com/vividsolutions/jts/simplify jts/branches/upstream/current/src/com/vividsolutions/jts/util jts/branches/upstream/current/src/com/vividsolutions/jtsexample jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/distance jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/linemerge jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/polygonize jts/branches/upstream/current/src/com/vividsolutions/jtsexample/precision jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique jts/branches/upstream/current/test jts/branches/upstream/current/test/robust jts/branches/upstream/current/test/validate jts/branches/upstream/current/test/vivid
frankie at alioth.debian.org
frankie at alioth.debian.org
Fri Jun 15 19:35:00 UTC 2007
Author: frankie
Date: 2007-06-15 19:34:59 +0000 (Fri, 15 Jun 2007)
New Revision: 877
Added:
packages/jts/
packages/jts/branches/
packages/jts/branches/upstream/
packages/jts/branches/upstream/current/
packages/jts/branches/upstream/current/bin/
packages/jts/branches/upstream/current/bin/jts.css
packages/jts/branches/upstream/current/bin/test.bat
packages/jts/branches/upstream/current/bin/test_robust.bat
packages/jts/branches/upstream/current/bin/test_vivid.bat
packages/jts/branches/upstream/current/bin/testbuilder.bat
packages/jts/branches/upstream/current/bin/testrunner.bat
packages/jts/branches/upstream/current/bin/testrunner.properties
packages/jts/branches/upstream/current/doc/
packages/jts/branches/upstream/current/doc/JTS Developer Guide.pdf
packages/jts/branches/upstream/current/doc/JTS Technical Specs.pdf
packages/jts/branches/upstream/current/doc/JTS TestBuilder & TestRunner User Guide.pdf
packages/jts/branches/upstream/current/doc/JTS Version History.html
packages/jts/branches/upstream/current/src/
packages/jts/branches/upstream/current/src/Doxyfile
packages/jts/branches/upstream/current/src/MANIFEST.MF
packages/jts/branches/upstream/current/src/com/
packages/jts/branches/upstream/current/src/com/vividsolutions/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/
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/
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/
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/impl/PackedCoordinateSequenceFactory.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geom/util/
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/geom/util/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/
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/
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/geomgraph/index/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/geomgraph/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/ArrayListVisitor.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/IndexVisitor.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/
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/bintree/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/chain/
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/chain/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/quadtree/
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/quadtree/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/strtree/
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/strtree/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/index/sweepline/
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/index/sweepline/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/io/
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/io/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/IteratedNoder.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/MCQuadtreeNoder.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/noding/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/noding/snapround/
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/jts/noding/snapround/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/
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/
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/buffer/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/distance/
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/distance/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/linemerge/
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/
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/overlay/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/polygonize/
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/
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/
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/relate/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/operation/valid/
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/operation/valid/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/planargraph/
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/planargraph/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/polygonize/
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/polygonize/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/precision/
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/precision/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/
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/LineSegmentIndex.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/TaggedLineSegment.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/TaggedLinesSimplifier.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/simplify/TopologyPreservingSimplifier.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jts/util/
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/jts/util/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/geom/
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/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/distance/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/distance/ClosestPointExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/linemerge/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/linemerge/LineMergeExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/polygonize/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/operation/polygonize/PolygonizeExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/package.html
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/precision/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/precision/EnhancedPrecisionOpExample.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique/
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique/LineStringSelfIntersections.java
packages/jts/branches/upstream/current/src/com/vividsolutions/jtsexample/technique/UnionUsingBuffer.java
packages/jts/branches/upstream/current/src/jump-workbench-properties.xml
packages/jts/branches/upstream/current/test/
packages/jts/branches/upstream/current/test/robust/
packages/jts/branches/upstream/current/test/robust/TestRobustOverlayFixed.xml
packages/jts/branches/upstream/current/test/robust/TestRobustOverlayFloat.xml
packages/jts/branches/upstream/current/test/robust/TestRobustRelate.xml
packages/jts/branches/upstream/current/test/validate/
packages/jts/branches/upstream/current/test/validate/TestRelateAA-big.xml
packages/jts/branches/upstream/current/test/validate/TestRelateAA.xml
packages/jts/branches/upstream/current/test/validate/TestRelateAC.xml
packages/jts/branches/upstream/current/test/validate/TestRelateLA.xml
packages/jts/branches/upstream/current/test/validate/TestRelateLC.xml
packages/jts/branches/upstream/current/test/validate/TestRelateLL.xml
packages/jts/branches/upstream/current/test/validate/TestRelatePA.xml
packages/jts/branches/upstream/current/test/validate/TestRelatePL.xml
packages/jts/branches/upstream/current/test/validate/TestRelatePP.xml
packages/jts/branches/upstream/current/test/vivid/
packages/jts/branches/upstream/current/test/vivid/TestBoundary.xml
packages/jts/branches/upstream/current/test/vivid/TestCentroid.xml
packages/jts/branches/upstream/current/test/vivid/TestConvexHull-big.xml
packages/jts/branches/upstream/current/test/vivid/TestConvexHull.xml
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/TestFunctionLA.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionLAPrec.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionLL.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionLLPrec.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionPA.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionPL.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionPLPrec.xml
packages/jts/branches/upstream/current/test/vivid/TestFunctionPP.xml
packages/jts/branches/upstream/current/test/vivid/TestInteriorPoint.xml
packages/jts/branches/upstream/current/test/vivid/TestRectanglePredicate.xml
packages/jts/branches/upstream/current/test/vivid/TestRelateAA.xml
packages/jts/branches/upstream/current/test/vivid/TestRelateAC.xml
packages/jts/branches/upstream/current/test/vivid/TestRelateLA.xml
packages/jts/branches/upstream/current/test/vivid/TestRelateLC.xml
packages/jts/branches/upstream/current/test/vivid/TestRelateLL.xml
packages/jts/branches/upstream/current/test/vivid/TestRelatePA.xml
packages/jts/branches/upstream/current/test/vivid/TestRelatePL.xml
packages/jts/branches/upstream/current/test/vivid/TestRelatePP.xml
packages/jts/branches/upstream/current/test/vivid/TestSimple.xml
packages/jts/branches/upstream/current/test/vivid/TestValid.xml
packages/jts/branches/upstream/current/test/vivid/TestValid2-big.xml
packages/jts/branches/upstream/current/test/vivid/TestValid2.xml
packages/jts/branches/upstream/current/test/vivid/TestWithinDistance.xml
packages/jts/tags/
Log:
[svn-inject] Installing original source of jts
Added: packages/jts/branches/upstream/current/bin/jts.css
===================================================================
--- packages/jts/branches/upstream/current/bin/jts.css (rev 0)
+++ packages/jts/branches/upstream/current/bin/jts.css 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,139 @@
+BODY
+{
+ BACKGROUND-COLOR: lightblue;
+ FONT-FAMILY: Verdana, Arial;
+ FONT-SIZE: 10pt;
+ FONT-WEIGHT: normal
+}
+H2
+{
+ BACKGROUND-COLOR: darkblue;
+ COLOR: white;
+ FONT-FAMILY: Verdana, Arial;
+ FONT-SIZE: 12pt;
+ FONT-WEIGHT: bolder;
+ MARGIN-BOTTOM: 2pt;
+ PADDING-LEFT: 5px
+}
+H3
+{
+ BACKGROUND-COLOR: lightskyblue;
+ FONT-WEIGHT: normal;
+ MARGIN-BOTTOM: 2pt
+}
+H4
+{
+ BACKGROUND-COLOR: limegreen;
+ FONT-WEIGHT: normal
+}
+H5
+{
+ BACKGROUND-COLOR: burlywood;
+ FONT-WEIGHT: normal
+}
+H6
+{
+ FONT-SIZE: 12pt
+}
+TH
+{
+ BACKGROUND-COLOR: burlywood
+}
+.initialLetter
+{
+ COLOR: lightblue
+}
+.foo
+{
+ COLOR: goldenrod
+}
+.wktA
+{
+ COLOR: blue;
+ FONT-SIZE: 8pt
+}
+.wktB
+{
+ COLOR: red;
+ FONT-SIZE: 8pt
+}
+.methodTitle
+{
+ BACKGROUND-COLOR: steelblue;
+ COLOR: yellow
+}
+.wktR
+{
+ FONT-SIZE: 8pt
+}
+.precisionModel
+{
+ FONT-SIZE: 8pt
+}
+.resultTrue
+{
+ COLOR: green
+}
+.resultFalse
+{
+ COLOR: red
+}
+.MenuBody
+{
+ BACKGROUND-COLOR: midnightblue
+}
+.MenuItem
+{
+ COLOR: white
+}
+.MenuTitle
+{
+ COLOR: #3366ff;
+ FONT-SIZE: 14pt;
+ TEXT-ALIGN: center
+}
+TD
+{
+ FONT-SIZE: 10pt
+}
+.orgName
+{
+ FONT-SIZE: 8pt;
+ FONT-STYLE: italic;
+ FONT-WEIGHT: lighter
+}
+.creditName
+{
+ FONT-WEIGHT: bolder;
+ PADDING-LEFT: 10px
+}
+.creditTitle
+{
+ BACKGROUND-COLOR: steelblue;
+ COLOR: yellow;
+ FONT-WEIGHT: bolder;
+ PADDING-LEFT: 10px;
+ PADDING-RIGHT: 10px
+}
+H1
+{
+ BORDER-BOTTOM: darkblue thin solid;
+ BORDER-TOP: medium none;
+ FONT-STYLE: italic;
+ MARGIN-BOTTOM: 2px;
+ PADDING-BOTTOM: 4px
+}
+.testTitle
+{
+ FONT-SIZE: 16pt;
+ FONT-WEIGHT: bolder
+}
+.caption
+{
+ FONT-SIZE: 8pt;
+ FONT-STYLE: italic
+}
+.bigCaption
+{
+ FONT-WEIGHT: bolder
+}
Added: packages/jts/branches/upstream/current/bin/test.bat
===================================================================
--- packages/jts/branches/upstream/current/bin/test.bat (rev 0)
+++ packages/jts/branches/upstream/current/bin/test.bat 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,25 @@
+ at echo off
+rem A batch file to run the XML test files written by Geographic Data BC.
+
+set CLASSPATH=
+for %%i in (..\lib\*.*) do (
+ set jarfile=%%i
+
+ rem If we append to a variable inside the for, only the last entry will
+ rem be kept. So append to the variable outside the for.
+ rem See http://www.experts-exchange.com/Operating_Systems/MSDOS/Q_20561701.html.
+ rem [Jon Aquino]
+
+ call :setclass
+)
+
+java com.vividsolutions.jtstest.testrunner.TopologyTestApp -Files ..\test\validate
+pause
+
+goto :eof
+
+:setclass
+set CLASSPATH=%jarfile%;%CLASSPATH%
+set jarfile=
+
+:eof
\ No newline at end of file
Added: packages/jts/branches/upstream/current/bin/test_robust.bat
===================================================================
--- packages/jts/branches/upstream/current/bin/test_robust.bat (rev 0)
+++ packages/jts/branches/upstream/current/bin/test_robust.bat 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,25 @@
+ at echo off
+rem A batch file to run the XML test files written by Geographic Data BC.
+
+set CLASSPATH=
+for %%i in (..\lib\*.*) do (
+ set jarfile=%%i
+
+ rem If we append to a variable inside the for, only the last entry will
+ rem be kept. So append to the variable outside the for.
+ rem See http://www.experts-exchange.com/Operating_Systems/MSDOS/Q_20561701.html.
+ rem [Jon Aquino]
+
+ call :setclass
+)
+
+java com.vividsolutions.jtstest.testrunner.TopologyTestApp -Files ..\test\robust
+pause
+
+goto :eof
+
+:setclass
+set CLASSPATH=%jarfile%;%CLASSPATH%
+set jarfile=
+
+:eof
\ No newline at end of file
Added: packages/jts/branches/upstream/current/bin/test_vivid.bat
===================================================================
--- packages/jts/branches/upstream/current/bin/test_vivid.bat (rev 0)
+++ packages/jts/branches/upstream/current/bin/test_vivid.bat 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,25 @@
+ at echo off
+rem A batch file to run the XML test files written by Geographic Data BC.
+
+set CLASSPATH=
+for %%i in (..\lib\*.*) do (
+ set jarfile=%%i
+
+ rem If we append to a variable inside the for, only the last entry will
+ rem be kept. So append to the variable outside the for.
+ rem See http://www.experts-exchange.com/Operating_Systems/MSDOS/Q_20561701.html.
+ rem [Jon Aquino]
+
+ call :setclass
+)
+
+java com.vividsolutions.jtstest.testrunner.TopologyTestApp -Files ..\test\vivid
+pause
+
+goto :eof
+
+:setclass
+set CLASSPATH=%jarfile%;%CLASSPATH%
+set jarfile=
+
+:eof
\ No newline at end of file
Added: packages/jts/branches/upstream/current/bin/testbuilder.bat
===================================================================
--- packages/jts/branches/upstream/current/bin/testbuilder.bat (rev 0)
+++ packages/jts/branches/upstream/current/bin/testbuilder.bat 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,24 @@
+ at echo off
+rem A batch file to run the JTS Test Builder
+
+set CLASSPATH=
+for %%i in (..\lib\*.*) do (
+ set jarfile=%%i
+
+ rem If we append to a variable inside the for, only the last entry will
+ rem be kept. So append to the variable outside the for.
+ rem See http://www.experts-exchange.com/Operating_Systems/MSDOS/Q_20561701.html.
+ rem [Jon Aquino]
+
+ call :setclass
+)
+
+start javaw com.vividsolutions.jtstest.testbuilder.JTSTestBuilder
+
+goto :eof
+
+:setclass
+set CLASSPATH=%jarfile%;%CLASSPATH%
+set jarfile=
+
+:eof
\ No newline at end of file
Added: packages/jts/branches/upstream/current/bin/testrunner.bat
===================================================================
--- packages/jts/branches/upstream/current/bin/testrunner.bat (rev 0)
+++ packages/jts/branches/upstream/current/bin/testrunner.bat 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,24 @@
+ at echo off
+rem A batch file to run the JTS test runner.
+
+set CLASSPATH=
+for %%i in (..\lib\*.*) do (
+ set jarfile=%%i
+
+ rem If we append to a variable inside the for, only the last entry will
+ rem be kept. So append to the variable outside the for.
+ rem See http://www.experts-exchange.com/Operating_Systems/MSDOS/Q_20561701.html.
+ rem [Jon Aquino]
+
+ call :setclass
+)
+
+start javaw com.vividsolutions.jtstest.testrunner.TopologyTestApp -Properties testrunner.properties -GUI
+
+goto :eof
+
+:setclass
+set CLASSPATH=%jarfile%;%CLASSPATH%
+set jarfile=
+
+:eof
\ No newline at end of file
Added: packages/jts/branches/upstream/current/bin/testrunner.properties
===================================================================
--- packages/jts/branches/upstream/current/bin/testrunner.properties (rev 0)
+++ packages/jts/branches/upstream/current/bin/testrunner.properties 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,3 @@
+#Properties file for class com.vividsolutions.jtstest.testrunner.TopologyTestApp
+#Fri May 24 10:18:11 PDT 2002
+TestFiles=
Added: packages/jts/branches/upstream/current/doc/JTS Developer Guide.pdf
===================================================================
(Binary files differ)
Property changes on: packages/jts/branches/upstream/current/doc/JTS Developer Guide.pdf
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: packages/jts/branches/upstream/current/doc/JTS Technical Specs.pdf
===================================================================
(Binary files differ)
Property changes on: packages/jts/branches/upstream/current/doc/JTS Technical Specs.pdf
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: packages/jts/branches/upstream/current/doc/JTS TestBuilder & TestRunner User Guide.pdf
===================================================================
(Binary files differ)
Property changes on: packages/jts/branches/upstream/current/doc/JTS TestBuilder & TestRunner User Guide.pdf
___________________________________________________________________
Name: svn:mime-type
+ application/octet-stream
Added: packages/jts/branches/upstream/current/doc/JTS Version History.html
===================================================================
--- packages/jts/branches/upstream/current/doc/JTS Version History.html (rev 0)
+++ packages/jts/branches/upstream/current/doc/JTS Version History.html 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,301 @@
+<html>
+
+<head>
+<title>JTS Version History</title>
+</head>
+
+<body bgcolor='lightblue'>
+<h1 style='text-align:center;'>
+JTS TOPOLOGY SUITE
+<br>
+Version History
+</h1>
+
+
+This document lists the change history of release versions of the JTS Topology Suite
+
+<hr>
+<h2>Version 1.6</h2>
+
+Release Date: February 3, 2005
+
+<h3>API Changes</h3>
+<ul>
+<li>Changed to using <code>CoordinateArraySequence</code> instead of <code>DefaultCoordinateSequence</code>
+(to provide a more descriptive name).
+</ul>
+
+<h3>Semantics Changes</h3>
+<ul>
+<li>PrecisionModel#makePrecise changed to use Symmetric Arithmetic Rounding rather than Banker's Rounding
+</ul>
+
+<h3>Functionality Improvements</h3>
+<ul>
+<li>Added ability to enable <code>Debug</code> methods by setting a system property
+<li>Added <code>getNumGeometries</code> and <code>getGeometryN</code> methods to Geometry class, to make API more uniform
+<li>Improved API for <code>CoordinateSequence</code> allows more options for improving memory usage and handling custom coordinate storage methods
+<li>Added <code>PackedCoordinateSequence</code> to provide reduced memory footprint for geometry objects if desired
+<li>Added optimized spatial predicates for rectangles
+<li>Added Debug#isDebugging method
+</ul>
+
+<h3>Bug Fixes</h3>
+<ul>
+<li>Fixed bug in <code>Geometry#within()</code> short circuiting
+<li>Fixed bug causing <code>Geometry#isValid</code> to throw IllegalArgumentException for certain kinds of holes with invalid rings
+<li>Fixed bug causing redundant linestrings to be returned in the result of overlaying polygons containing holes touching their shell.
+<li><code>Polygon#getBoundary</code> now returns a <code>LinearRing</code> if the polygon does not have holes
+</ul>
+
+<h3>Architecture Changes</h3>
+<ul>
+<li>Removed a proliferation of references to the default <code>CoordinateSequenceFactory</code>
+</ul>
+
+<h2>Contributors</h2>
+<ul>
+<li>Andrea Aime
+</ul>
+
+<h2>Version 1.5</h2>
+Release Date: September 22, 2004
+<p>
+This version is upwards compatible with Version 1.4
+
+<h3>API Changes</h3>
+<ul>
+<li>None
+</ul>
+
+<h3>Semantics Changes</h3>
+<ul>
+<li>None
+</ul>
+
+<h3>Functionality Improvements</h3>
+<ul>
+<li>CGAlgorithms#isCCW now handles coordinate lists with repeated points. Also throws an IllegalArgumentException if the input ring does not have 3 distinct points
+<li>isValid now checks for invalid coordinates (e.g. ones with Nan or infinite numbers)
+<li>added copyDeep() method to CoordinateArrays
+<li>added geometry simplification operations DouglasPeuckerSimplifier and TopologyPreservingSimplifier
+<li>added methods to Quadtree and STRtree to remove items and query using the Visitor pattern
+</ul>
+
+<h3>Performance Improvements</h3>
+<ul>
+<li>Added short-circuit tests in geometry named predicates based on envelope tests
+</ul>
+<h3>Bug Fixes</h3>
+<ul>
+<li>Fixed bugs in Geometry serialization
+<li>Fixed bug in ValidOp which reported some MultiPolygons with shells nested inside a hole as invalid
+<li>Fixed bug in buffer which caused buffers of some polygons with small & large holes to not contain any holes
+<li>Fixed bug in Polygonizer which caused exception if no lines were supplied
+</ul>
+<h3>Architecture Changes</h3>
+<ul>
+<li>Basic CG algorithm methods made static in the in CGAlgorithms class
+<li>Various utility methods made public in CoordinateArrays class
+</ul>
+<h3>Documentation</h3>
+<ul>
+<li>More examples provided in com.vividsolutions.jtsexamples package
+</ul>
+
+<h2>Version 1.4</h2>
+
+Release Date: November 4, 2003
+<h3>Semantics Changes</h3>
+<ul>
+<li>none
+</ul>
+<h3>Functionality Improvements</h3>
+<ul>
+<li>Added "LINEARRING" tag to WKT syntax
+<li>Added GeometryEditor class to allow easy copy/modify of Geometrys
+<li>Added GeometricShapeFactory class to easily create standard geometric shapes
+<li>Geometries can now carry arbitrary user-defined data objects (via Geometry#get/setUserData(Object) method)
+<li>Added CoordinateSequence and CoordinateSequenceFactory interfaces, and default implementations (BasicCoordinateSequence, BasicCoordinateSequenceFactory)
+<li>Added Geometry#getFactory
+<li>Added new PrecisionModel type of FLOATING_SINGLE, for rounding to single precision floating point
+<li>Added DistanceOp#getClosestPoints method, which returns the closest points between two Geometries
+<li>Added com.vividsolutions.jts.noding package containing classes to perform fast indexed noding of linestrings
+<li>Added com.vividsolutions.jts.operation.polygonize package containing classes to perform polygonization
+<li>Added com.vividsolutions.jts.operation.linemerge package containing classes to perform line merging
+<li>Added SimpleGeometryPrecisionReducer to allow reducing precision of coordinates of a Geometry
+<li>Added LineSegment#closestPoints method to compute the closest points between two line segments
+<li>Added MinimumDiameter class to compute minimum diameters of Geometries
+<li>Added geom.Triangle class to contain algorithms for Triangles
+<li>BufferOp now allows end cap styles to be specified. Three types are supported: round, butt and square.
+</ul>
+<h3>Performance Improvements</h3>
+<ul>
+<li>EdgeList now provides a findEqualEdge method which is substantially faster than findEdgeIndex, for large lists
+<li>Buffering is now faster and much more robust
+<li>Overlap operations are now more robust
+</ul>
+<h3>Bug Fixes</h3>
+<ul>
+<li>Envelope#init(Envelope) now handles null Envelopes correctly
+<li>CoordinateList#add() now correctly ignores the z-value of Coordinates in determining equality
+<li>Geometry#isValid now correctly handles checking validity of LinearRings
+<li>Fixed infinite loop bug causing Out Of Memory errors during polygon intersection
+<li>Geometry#clone now correctly clones the Geometry's Envelope
+<li>LineIntersector#computeEdgeDistance now correctly computes a non-zero edge distance in certain situations when a fixed precision model was being used and the line segment was a single unit in length
+<li>Fixed incorrect calculation of depths in DirectedEdgeStar#computeDepths
+<li>Fixed BufferSubgraph#addReachable to use explicit stack to avoid stack overflow problems
+<li>Fixed various bugs causing some kinds of buffers to be computed incorrectly
+</ul>
+<h3>API Changes</h3>
+<ul>
+<li>WKTReader/Writer: changed protected members to private
+<li>PrecisionModel type is now an object rather than an int
+<li>ConvexHull API changed to remove requirement to pass in CGAlgorithms object
+</ul>
+<h3>Code Architecture Changes</h3>
+<ul>
+<li>geom.util package added for utility classes which parse and modify geometries
+</ul>
+<h3>Documentation</h3>
+<ul>
+<li>More examples provided in com.vividsolutions.jtsexamples package
+<li>Added JTS Developers Guide
+</ul>
+
+<h2>Version 1.3</h2>
+Release Date: April 4, 2003
+<h3>Semantics Changes</h3>
+<ul>
+<li>all Geometry methods are now reentrant (thread-safe)
+<li>Fixed-precision coordinates are now stored in a rounded but non-scaled form. This makes them compatible with non-precise (Floating) coordinates, and simplifies working with precise coordinates directly. Mixed precision models are now supported in Geometry methods; method results are in the more precise of the input precision models.
+<li>Offsets are no longer supported in the Fixed precision model. This is necessary to allow storing fixed precision coordinates in a non-scaled form. This does not reduce the total precision available, since coordinates are stored in a floating-point format.
+<li>SRID and Precision Model are no longer checked for equality during Geometry operations. This removes a limitation which provided little semantic benefit.
+</ul>
+
+<h3>Functionality Improvements</h3>
+<ul>
+<li>added Geometry.isWithinDistance(Geometry g, double distance) method, to provide optimized proximity queries
+<li>added Geometry.buffer(double distance, int quadrantSegments) method, allowing control over accuracy of buffer approximation
+<li>added Geometry.getCentroid() method
+<li>added Geometry.getInteriorPoint() method, which uses heuristic methods to return a point in the interior of a Geometry
+<li>GeometryFactory.toGeometryArray now returns null if the argument is null
+</ul>
+<h3>Performance Improvements</h3>
+<ul>
+<li>Removed unnecessary string construction in EdgeEndStar.propagateSideLabels()
+<li>Eliminated unnecessary computation of self-intersections in rings during relate and spatial functions. This provides a large increase in speed when working with large rings and polygons. (Note that IsValid still checks for these self-intersections, which are illegal in LinearRings)
+<li>Add short-circuit code to RobustLineIntersector to detect non-intersections more efficiently
+</ul>
+<h3>Bug Fixes</h3>
+<ul>
+<li>Fixed ClassCastException occurring in GeometryCollection.getLength()
+<li>Fixed bug in Edge Intersection insertion (replaced Coordinate#equals with equals2D to ensure that intersection creation is not sensitive to Z-value).
+<li>Fixed handling LineStrings with too few points in GeometryGraph.addLineString
+<li>Fixed: was not checking that MultiPolygons don't contain components with too few points.
+<li>Fixed Envelope.distance() to return correct distance for all envelopes.
+<li>Fixed a few Geometry methods to make them re-entrant.
+<li>Fixed CoordinateList.closeRing() to ensure endpoints are not duplicated
+<li>Fixed CGAlgorithms.signedArea() to use a simpler algorithm which is more robust and faster.
+<li>Fixed bug preventing validating Rings containing an initial repeated point.
+</ul>
+<h3>API Changes</h3>
+<ul>
+<li>Added default constructor to WKTReader. It uses the default GeometryFactory
+<li>Add two static intersects() methods to Envelope, to allow computing intersections with envelopes defined by points only.
+<li>Dropped BinaryPower; its functionality is provided by DoubleBits in a more robust fashion.
+<li>Removed a couple of redundant private static methods from Geometry; they have been replaced by methods in CoordinateArrays
+<li>The Geometry class is now marked as Serializable
+</ul>
+
+<h2>Version 1.2</h2>
+Release Date: 7 October 2002
+<h3>Semantics Changes</h3>
+<ul>
+<li>JTS now allows Geometrys to have repeated points. All operations will continue to perform as before. This removes a significant incompatibility with the OGC spatial data model.
+<li>TopologyExceptions may now be thrown by spatial overlay methods. This helps to distinguish between code bugs and known robustness problems. It also provides a machine-readable coordinate for the error location.
+</ul>
+<h3>Functionality Improvements</h3>
+<ul>
+<li>RobustLineIntersector now uses "normalized" coordinates to maximize the accuracy of intersection computation.
+<li>Upgraded Quadtree with more robust implementation
+<li>Replaced IntervalTree with a more robust implementation of BinTree
+<li>Added STRTree 2-D spatial index, which exhibits better performance than QuadTrees in many situations.
+<li>Added EnhancePrecisionOp, which uses precisioning enhancing techniques to reduce the number of failure cases due to robustness problems.
+</ul>
+<h3>Bug Fixes</h3>
+<ul>
+<li>fixed ConvexHull to use TreeSet instead of HashSet for coordinates
+<li>Fixed isValid for GeometryCollections containing Polygons, which were sometimes erroneously returning a validity failure for correct Geometrys.
+<li>Fixed bug in LineSegment.distancePointLine() which would return the incorrect distance for a LineSegment with two identical points
+<li>Improved error handling in CGAlgorithms.isCCW()
+<li>IsValid now checks for too few points in a geometry component (e.g. due to repeated points in a ring)
+</ul>
+<h3>API Changes</h3>
+<ul>
+<li>added Stopwatch class
+<li>added Geometry.getArea() and Geometry.getLength() methods
+<li>added CGAlgorithms.signedArea() method
+<li>added methods to LineSegment - closestPoint(), getLength()
+<li>added CoordinateArrrays and CoordinateLists utility classes
+<li>Added TopologyValidationError.getErrorType() method
+<li>Added Envelope#intersects; deprecated Envelope#overlaps.
+<li>Added Geometry#geometryChanged() method to allow signaling when Geometry coordinates have been mutated by a client class
+<li>Added STRTree class implementing a Sort-Tile-Recursive spatial index (a variant of a packed R-tree)
+<li>Deleted IntervalTree 1-D spatial index (replaced by BinTree)
+<li>Add BinTree 1-D spatial index
+</ul>
+
+<h2>Version 1.1.1</h2>
+Release Date: 9 April 2002
+<h3>Bug Fixes</h3>
+<ul>
+<li>fixed decimal-point symbol localization bug in WKTWriter
+<li>fixed bug in Envelope.int(Envelope env)
+<li>fixed filename case of SFSMultiLineString.java and IntervalTree.java
+</ul>
+<h3>API Changes</h3>
+<ul>
+<li>deleted TopologyException class
+<li>renamed CGAlgorithms.isPointInPolygon to isPointInRing (a more accurate description of what the method computes)
+</ul>
+<h3>API Additions</h3>
+<ul>
+<li>added Geometry.getCoordinate() method
+<li>added Geometry.distance() method
+<li>added GeometryComponentFilter interface and Geometry.apply(GeometryComponentFilter) method
+</ul>
+
+<h2>Version 1.1</h2>
+Release Date: 28 March 2002
+<h3>New Features</h3>
+<ul>
+<li>added Geometry.isSimple() and Geometry.isValid() methods
+<li>improved design of topological data structures
+<li>added Geometry.setSRID() method
+<li>improved functionality of the Envelope class
+<li>added ability to write to an arbitrary java.io.Writer object to WKTWriter
+<li>added Validate and Mark Location functionality to TestBuilder
+</ul>
+
+<h2>Version 1.0</h2>
+Release Date: 1 February 2002
+<ul>
+<li>Removed some non-compatibilities with Java 1.1
+<li>Fixed bug in constructing buffer outline around inside of angles
+<li>In TestBuilder vertices are now displayed with fixed size in view units
+<li>Improved code for WKTWriter.writeFormatted()
+<li>Fixed bug in constructor for LinearRing
+<li>Improved implementation of sweepline intersection algorithm to avoid use of dynamic set.
+<li>Fixed bug in ConvexHull.cleanRing()
+<li>Refactored RobustLineIntersector and NonRobustLineIntersector
+</ul>
+
+<h2>Version 0.0</h2>
+Release Date: 30 May 2001
+
+<p>
+<i>Baseline version</i>
+
+</body>
+</html>
Added: packages/jts/branches/upstream/current/src/Doxyfile
===================================================================
--- packages/jts/branches/upstream/current/src/Doxyfile (rev 0)
+++ packages/jts/branches/upstream/current/src/Doxyfile 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,200 @@
+# Doxyfile 1.3-rc1
+
+#---------------------------------------------------------------------------
+# General configuration options
+#---------------------------------------------------------------------------
+PROJECT_NAME = JTS
+PROJECT_NUMBER =
+OUTPUT_DIRECTORY = c:\public\doxygen\jts
+OUTPUT_LANGUAGE = English
+EXTRACT_ALL = YES
+EXTRACT_PRIVATE = YES
+EXTRACT_STATIC = YES
+EXTRACT_LOCAL_CLASSES = YES
+HIDE_UNDOC_MEMBERS = NO
+HIDE_UNDOC_CLASSES = NO
+HIDE_FRIEND_COMPOUNDS = NO
+HIDE_IN_BODY_DOCS = NO
+BRIEF_MEMBER_DESC = YES
+REPEAT_BRIEF = YES
+ALWAYS_DETAILED_SEC = NO
+INLINE_INHERITED_MEMB = NO
+FULL_PATH_NAMES = YES
+STRIP_FROM_PATH =
+INTERNAL_DOCS = NO
+CASE_SENSE_NAMES = YES
+SHORT_NAMES = NO
+HIDE_SCOPE_NAMES = NO
+VERBATIM_HEADERS = YES
+SHOW_INCLUDE_FILES = YES
+JAVADOC_AUTOBRIEF = NO
+MULTILINE_CPP_IS_BRIEF = NO
+DETAILS_AT_TOP = NO
+INHERIT_DOCS = YES
+INLINE_INFO = YES
+SORT_MEMBER_DOCS = YES
+DISTRIBUTE_GROUP_DOC = NO
+TAB_SIZE = 8
+GENERATE_TODOLIST = YES
+GENERATE_TESTLIST = YES
+GENERATE_BUGLIST = YES
+GENERATE_DEPRECATEDLIST= YES
+ALIASES =
+ENABLED_SECTIONS =
+MAX_INITIALIZER_LINES = 30
+OPTIMIZE_OUTPUT_FOR_C = NO
+OPTIMIZE_OUTPUT_JAVA = YES
+SHOW_USED_FILES = YES
+#---------------------------------------------------------------------------
+# configuration options related to warning and progress messages
+#---------------------------------------------------------------------------
+QUIET = NO
+WARNINGS = YES
+WARN_IF_UNDOCUMENTED = YES
+WARN_FORMAT = "$file:$line: $text"
+WARN_LOGFILE =
+#---------------------------------------------------------------------------
+# configuration options related to the input files
+#---------------------------------------------------------------------------
+INPUT = U:/jaquino/CVS/jts/src/
+FILE_PATTERNS =
+RECURSIVE = YES
+EXCLUDE =
+EXCLUDE_SYMLINKS = NO
+EXCLUDE_PATTERNS =
+EXAMPLE_PATH =
+EXAMPLE_PATTERNS =
+EXAMPLE_RECURSIVE = NO
+IMAGE_PATH =
+INPUT_FILTER =
+FILTER_SOURCE_FILES = NO
+#---------------------------------------------------------------------------
+# configuration options related to source browsing
+#---------------------------------------------------------------------------
+SOURCE_BROWSER = YES
+INLINE_SOURCES = YES
+STRIP_CODE_COMMENTS = YES
+REFERENCED_BY_RELATION = YES
+REFERENCES_RELATION = YES
+#---------------------------------------------------------------------------
+# configuration options related to the alphabetical class index
+#---------------------------------------------------------------------------
+ALPHABETICAL_INDEX = YES
+COLS_IN_ALPHA_INDEX = 5
+IGNORE_PREFIX =
+#---------------------------------------------------------------------------
+# configuration options related to the HTML output
+#---------------------------------------------------------------------------
+GENERATE_HTML = YES
+HTML_OUTPUT = html
+HTML_FILE_EXTENSION = .html
+HTML_HEADER =
+HTML_FOOTER =
+HTML_STYLESHEET =
+HTML_ALIGN_MEMBERS = YES
+GENERATE_HTMLHELP = NO
+CHM_FILE =
+HHC_LOCATION =
+GENERATE_CHI = NO
+BINARY_TOC = NO
+TOC_EXPAND = NO
+DISABLE_INDEX = NO
+ENUM_VALUES_PER_LINE = 4
+GENERATE_TREEVIEW = NO
+TREEVIEW_WIDTH = 250
+#---------------------------------------------------------------------------
+# configuration options related to the LaTeX output
+#---------------------------------------------------------------------------
+GENERATE_LATEX = NO
+LATEX_OUTPUT = latex
+LATEX_CMD_NAME = latex
+MAKEINDEX_CMD_NAME = makeindex
+COMPACT_LATEX = NO
+PAPER_TYPE = a4wide
+EXTRA_PACKAGES =
+LATEX_HEADER =
+PDF_HYPERLINKS = NO
+USE_PDFLATEX = NO
+LATEX_BATCHMODE = NO
+#---------------------------------------------------------------------------
+# configuration options related to the RTF output
+#---------------------------------------------------------------------------
+GENERATE_RTF = NO
+RTF_OUTPUT = rtf
+COMPACT_RTF = NO
+RTF_HYPERLINKS = NO
+RTF_STYLESHEET_FILE =
+RTF_EXTENSIONS_FILE =
+#---------------------------------------------------------------------------
+# configuration options related to the man page output
+#---------------------------------------------------------------------------
+GENERATE_MAN = NO
+MAN_OUTPUT = man
+MAN_EXTENSION = .3
+MAN_LINKS = NO
+#---------------------------------------------------------------------------
+# configuration options related to the XML output
+#---------------------------------------------------------------------------
+GENERATE_XML = NO
+XML_SCHEMA =
+XML_DTD =
+#---------------------------------------------------------------------------
+# configuration options for the AutoGen Definitions output
+#---------------------------------------------------------------------------
+GENERATE_AUTOGEN_DEF = NO
+#---------------------------------------------------------------------------
+# configuration options related to the Perl module output
+#---------------------------------------------------------------------------
+GENERATE_PERLMOD = NO
+PERLMOD_LATEX = NO
+PERLMOD_PRETTY = YES
+PERLMOD_MAKEVAR_PREFIX =
+#---------------------------------------------------------------------------
+# Configuration options related to the preprocessor
+#---------------------------------------------------------------------------
+ENABLE_PREPROCESSING = YES
+MACRO_EXPANSION = NO
+EXPAND_ONLY_PREDEF = NO
+SEARCH_INCLUDES = YES
+INCLUDE_PATH =
+INCLUDE_FILE_PATTERNS =
+PREDEFINED =
+EXPAND_AS_DEFINED =
+SKIP_FUNCTION_MACROS = YES
+#---------------------------------------------------------------------------
+# Configuration::addtions related to external references
+#---------------------------------------------------------------------------
+TAGFILES =
+GENERATE_TAGFILE =
+ALLEXTERNALS = NO
+EXTERNAL_GROUPS = YES
+PERL_PATH = /usr/bin/perl
+#---------------------------------------------------------------------------
+# Configuration options related to the dot tool
+#---------------------------------------------------------------------------
+CLASS_DIAGRAMS = YES
+HIDE_UNDOC_RELATIONS = YES
+HAVE_DOT = YES
+CLASS_GRAPH = YES
+COLLABORATION_GRAPH = YES
+TEMPLATE_RELATIONS = YES
+INCLUDE_GRAPH = YES
+INCLUDED_BY_GRAPH = YES
+GRAPHICAL_HIERARCHY = YES
+DOT_IMAGE_FORMAT = png
+DOT_PATH = h:/utilities
+DOTFILE_DIRS =
+MAX_DOT_GRAPH_WIDTH = 1024
+MAX_DOT_GRAPH_HEIGHT = 1024
+GENERATE_LEGEND = YES
+DOT_CLEANUP = YES
+#---------------------------------------------------------------------------
+# Configuration::addtions related to the search engine
+#---------------------------------------------------------------------------
+SEARCHENGINE = NO
+CGI_NAME = search.cgi
+CGI_URL =
+DOC_URL =
+DOC_ABSPATH =
+BIN_ABSPATH = /usr/local/bin/
+EXT_DOC_PATHS =
Added: packages/jts/branches/upstream/current/src/MANIFEST.MF
===================================================================
--- packages/jts/branches/upstream/current/src/MANIFEST.MF (rev 0)
+++ packages/jts/branches/upstream/current/src/MANIFEST.MF 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,4 @@
+Manifest-version: 1.0
+Implementation-Title: Java Topology Suite
+Implementation-Version: 1.6
+Implementation-Vendor: Vivid Solutions
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CGAlgorithms.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,434 @@
+/*
+ * 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.Coordinate;
+import com.vividsolutions.jts.geom.CoordinateSequence;
+
+/**
+ * Specifies and implements various fundamental Computational Geometric algorithms.
+ * The algorithms supplied in this class are robust for double-precision floating point.
+ *
+ * @version 1.6
+ */
+public class CGAlgorithms
+{
+
+ /**
+ * A value that indicates an orientation of clockwise, or a right turn.
+ */
+ public static final int CLOCKWISE = -1;
+ public static final int RIGHT = CLOCKWISE;
+ /**
+ * A value that indicates an orientation of counterclockwise, or a left turn.
+ */
+ public static final int COUNTERCLOCKWISE = 1;
+ public static final int LEFT = COUNTERCLOCKWISE;
+ /**
+ * A value that indicates an orientation of collinear, or no turn (straight).
+ */
+ public static final int COLLINEAR = 0;
+ public static final int STRAIGHT = COLLINEAR;
+
+ /**
+ * Returns the index of the direction of the point <code>q</code>
+ * relative to a
+ * vector specified by <code>p1-p2</code>.
+ *
+ * @param p1 the origin point of the vector
+ * @param p2 the final point of the vector
+ * @param q the point to compute the direction to
+ *
+ * @return 1 if q is counter-clockwise (left) from p1-p2
+ * @return -1 if q is clockwise (right) from p1-p2
+ * @return 0 if q is collinear with p1-p2
+ */
+ public static int orientationIndex(Coordinate p1, Coordinate p2, Coordinate q) {
+ // travelling along p1->p2, turn counter clockwise to get to q return 1,
+ // travelling along p1->p2, turn clockwise to get to q return -1,
+ // p1, p2 and q are colinear return 0.
+ double dx1 = p2.x - p1.x;
+ double dy1 = p2.y - p1.y;
+ double dx2 = q.x - p2.x;
+ double dy2 = q.y - p2.y;
+ return RobustDeterminant.signOfDet2x2(dx1, dy1, dx2, dy2);
+ }
+
+ public CGAlgorithms() {
+ }
+
+ /**
+ * Test whether a point lies inside a ring.
+ * The ring may be oriented in either direction.
+ * If the point lies on the ring boundary the result of this method is unspecified.
+ * <p>
+ * This algorithm does not attempt to first check the point against the envelope
+ * of the ring.
+ *
+ * @param p point to check for ring inclusion
+ * @param ring assumed to have first point identical to last point
+ * @return <code>true</code> if p is inside ring
+ */
+ public static boolean isPointInRing(Coordinate p, Coordinate[] ring) {
+ /*
+ * For each segment l = (i-1, i), see if it crosses ray from test point in positive x direction.
+ */
+ int crossings = 0; // number of segment/ray crossings
+ for (int i = 1; i < ring.length; i++) {
+ int i1 = i - 1;
+ Coordinate p1 = ring[i];
+ Coordinate p2 = ring[i1];
+
+ if (((p1.y > p.y) && (p2.y <= p.y)) ||
+ ((p2.y > p.y) && (p1.y <= p.y))) {
+ double x1 = p1.x - p.x;
+ double y1 = p1.y - p.y;
+ double x2 = p2.x - p.x;
+ double y2 = p2.y - p.y;
+ /*
+ * segment straddles x axis, so compute intersection with x-axis.
+ */
+ double xInt = RobustDeterminant.signOfDet2x2(x1, y1, x2, y2) / (y2 - y1);
+ //xsave = xInt;
+ /*
+ * crosses ray if strictly positive intersection.
+ */
+ if (xInt > 0.0) {
+ crossings++;
+ }
+ }
+ }
+ /*
+ * p is inside if number of crossings is odd.
+ */
+ if ((crossings % 2) == 1) {
+ return true;
+ }
+ else {
+ return false;
+ }
+ }
+
+ /**
+ * Test whether a point lies on the line segments defined by a
+ * list of coordinates.
+ *
+ * @return true true if
+ * the point is a vertex of the line or lies in the interior of a line
+ * segment in the linestring
+ */
+ public static boolean isOnLine(Coordinate p, Coordinate[] pt) {
+ LineIntersector lineIntersector = new RobustLineIntersector();
+ for (int i = 1; i < pt.length; i++) {
+ Coordinate p0 = pt[i - 1];
+ Coordinate p1 = pt[i];
+ lineIntersector.computeIntersection(p, p0, p1);
+ if (lineIntersector.hasIntersection()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ /**
+ * Computes whether a ring defined by an array of {@link Coordinate} is
+ * oriented counter-clockwise.
+ * <ul>
+ * <li>The list of points is assumed to have the first and last points equal.
+ * <li>This will handle coordinate lists which contain repeated points.
+ * <li>If the ring is invalid, the answer returned may not be correct.
+ * </ul>
+ *
+ * @param ring an array of coordinates forming a ring
+ * @return <code>true</code> if the ring is oriented counter-clockwise.
+ */
+ public static boolean isCCW(Coordinate[] ring) {
+ // # of points without closing endpoint
+ int nPts = ring.length - 1;
+
+ // find highest point
+ Coordinate hip = ring[0];
+ int hii = 0;
+ for (int i = 1; i <= nPts; i++) {
+ Coordinate p = ring[i];
+ if (p.y > hip.y) {
+ hip = p;
+ hii = i;
+ }
+ }
+
+ // find distinct point before highest point
+ int iPrev = hii;
+ do {
+ iPrev = iPrev - 1;
+ if (iPrev < 0) iPrev = nPts;
+ } while (ring[iPrev].equals(hip) && iPrev != hii);
+
+ // find distinct point after highest point
+ int iNext = hii;
+ do {
+ iNext = (iNext + 1) % nPts;
+ } while (ring[iNext].equals(hip) && iNext != hii);
+
+ Coordinate prev = ring[iPrev];
+ Coordinate next = ring[iNext];
+
+ /**
+ * This check catches cases where the ring contains an A-B-A configuration of points.
+ * This can happen if the ring does not contain 3 distinct points
+ * (including the case where the input array has fewer than 4 elements),
+ * or it contains coincident line segments.
+ */
+ if (prev.equals(hip) || next.equals(hip) || prev.equals(next))
+ return false;
+ // MD - don't bother throwing exception, since this isn't a complete check for ring validity
+// throw new IllegalArgumentException("Invalid ring (contains repeated line segments)");
+
+ int disc = computeOrientation(prev, hip, next);
+
+ /**
+ * If disc is exactly 0, lines are collinear. There are two possible cases:
+ * (1) the lines lie along the x axis in opposite directions
+ * (2) the lines lie on top of one another
+ *
+ * (1) is handled by checking if next is left of prev ==> CCW
+ * (2) will never happen if the ring is valid, so don't check for it
+ * (Might want to assert this)
+ */
+ boolean isCCW = false;
+ if (disc == 0) {
+ // poly is CCW if prev x is right of next x
+ isCCW = (prev.x > next.x);
+ }
+ else {
+ // if area is positive, points are ordered CCW
+ isCCW = (disc > 0);
+ }
+ return isCCW;
+ }
+
+ /**
+ * Computes the orientation of a point q to the directed line segment p1-p2.
+ * The orientation of a point relative to a directed line segment indicates
+ * which way you turn to get to q after travelling from p1 to p2.
+ *
+ * @return 1 if q is counter-clockwise from p1-p2
+ * @return -1 if q is clockwise from p1-p2
+ * @return 0 if q is collinear with p1-p2
+ */
+ public static int computeOrientation(Coordinate p1, Coordinate p2, Coordinate q) {
+ return orientationIndex(p1, p2, q);
+ }
+
+
+ /**
+ * Computes the distance from a point p to a line segment AB
+ *
+ * Note: NON-ROBUST!
+ *
+ * @param p the point to compute the distance for
+ * @param A one point of the line
+ * @param B another point of the line (must be different to A)
+ * @return the distance from p to line segment AB
+ */
+ public static double distancePointLine(Coordinate p, Coordinate A, Coordinate B)
+ {
+ // if start==end, then use pt distance
+ if ( A.equals(B) ) return p.distance(A);
+
+ // otherwise use comp.graphics.algorithms Frequently Asked Questions method
+ /*(1) AC dot AB
+ r = ---------
+ ||AB||^2
+ r has the following meaning:
+ r=0 P = A
+ r=1 P = B
+ r<0 P is on the backward extension of AB
+ r>1 P is on the forward extension of AB
+ 0<r<1 P is interior to AB
+ */
+
+ double r = ( (p.x - A.x) * (B.x - A.x) + (p.y - A.y) * (B.y - A.y) )
+ /
+ ( (B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y) );
+
+ if (r <= 0.0) return p.distance(A);
+ if (r >= 1.0) return p.distance(B);
+
+
+ /*(2)
+ (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
+ s = -----------------------------
+ L^2
+
+ Then the distance from C to P = |s|*L.
+ */
+
+ double s = ((A.y - p.y) *(B.x - A.x) - (A.x - p.x)*(B.y - A.y) )
+ /
+ ((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y) );
+
+ return
+ Math.abs(s) *
+ Math.sqrt(((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y)));
+ }
+ /**
+ * Computes the perpendicular distance from a point p
+ * to the (infinite) line containing the points AB
+ *
+ * @param p the point to compute the distance for
+ * @param A one point of the line
+ * @param B another point of the line (must be different to A)
+ * @return the distance from p to line AB
+ */
+ public static double distancePointLinePerpendicular(Coordinate p, Coordinate A, Coordinate B)
+ {
+ // use comp.graphics.algorithms Frequently Asked Questions method
+ /*(2)
+ (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
+ s = -----------------------------
+ L^2
+
+ Then the distance from C to P = |s|*L.
+ */
+
+ double s = ((A.y - p.y) *(B.x - A.x) - (A.x - p.x)*(B.y - A.y) )
+ /
+ ((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y) );
+
+ return
+ Math.abs(s) *
+ Math.sqrt(((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y)));
+ }
+
+ /**
+ * Computes the distance from a line segment AB to a line segment CD
+ *
+ * Note: NON-ROBUST!
+ *
+ * @param A a point of one line
+ * @param B the second point of (must be different to A)
+ * @param C one point of the line
+ * @param D another point of the line (must be different to A)
+ */
+ public static double distanceLineLine(Coordinate A, Coordinate B, Coordinate C, Coordinate D)
+ {
+ // check for zero-length segments
+ if ( A.equals(B) ) return distancePointLine(A,C,D);
+ if ( C.equals(D) ) return distancePointLine(D,A,B);
+
+ // AB and CD are line segments
+ /* from comp.graphics.algo
+
+ Solving the above for r and s yields
+ (Ay-Cy)(Dx-Cx)-(Ax-Cx)(Dy-Cy)
+ r = ----------------------------- (eqn 1)
+ (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
+
+ (Ay-Cy)(Bx-Ax)-(Ax-Cx)(By-Ay)
+ s = ----------------------------- (eqn 2)
+ (Bx-Ax)(Dy-Cy)-(By-Ay)(Dx-Cx)
+ Let P be the position vector of the intersection point, then
+ P=A+r(B-A) or
+ Px=Ax+r(Bx-Ax)
+ Py=Ay+r(By-Ay)
+ By examining the values of r & s, you can also determine some other
+limiting conditions:
+ If 0<=r<=1 & 0<=s<=1, intersection exists
+ r<0 or r>1 or s<0 or s>1 line segments do not intersect
+ If the denominator in eqn 1 is zero, AB & CD are parallel
+ If the numerator in eqn 1 is also zero, AB & CD are collinear.
+
+ */
+ double r_top = (A.y-C.y)*(D.x-C.x) - (A.x-C.x)*(D.y-C.y) ;
+ double r_bot = (B.x-A.x)*(D.y-C.y) - (B.y-A.y)*(D.x-C.x) ;
+
+ double s_top = (A.y-C.y)*(B.x-A.x) - (A.x-C.x)*(B.y-A.y);
+ double s_bot = (B.x-A.x)*(D.y-C.y) - (B.y-A.y)*(D.x-C.x);
+
+ if ( (r_bot==0) || (s_bot == 0) ) {
+ return
+ Math.min(distancePointLine(A,C,D),
+ Math.min(distancePointLine(B,C,D),
+ Math.min(distancePointLine(C,A,B),
+ distancePointLine(D,A,B) ) ) );
+
+ }
+ double s = s_top/s_bot;
+ double r= r_top/r_bot;
+
+ if ((r < 0) || ( r > 1) || (s < 0) || (s > 1) ) {
+ //no intersection
+ return
+ Math.min(distancePointLine(A,C,D),
+ Math.min(distancePointLine(B,C,D),
+ Math.min(distancePointLine(C,A,B),
+ distancePointLine(D,A,B) ) ) );
+ }
+ return 0.0; //intersection exists
+ }
+
+ /**
+ * Returns the signed area for a ring. The area is positive if
+ * the ring is oriented CW.
+ */
+ public static double signedArea(Coordinate[] ring)
+ {
+ if (ring.length < 3) return 0.0;
+ double sum = 0.0;
+ for (int i = 0; i < ring.length - 1; i++) {
+ double bx = ring[i].x;
+ double by = ring[i].y;
+ double cx = ring[i + 1].x;
+ double cy = ring[i + 1].y;
+ sum += (bx + cx) * (cy - by);
+ }
+ return -sum / 2.0;
+ }
+
+ /**
+ * Computes the length of a linestring specified by a sequence of points.
+ *
+ * @param pts the points specifying the linestring
+ * @return the length of the linestring
+ */
+ public static double length(CoordinateSequence pts) {
+ if (pts.size() < 1) return 0.0;
+ double sum = 0.0;
+ for (int i = 1; i < pts.size(); i++) {
+ sum += pts.getCoordinate(i).distance(pts.getCoordinate(i - 1));
+ }
+ return sum;
+ }
+
+}
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidArea.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,165 @@
+
+/*
+ * 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.*;
+
+/**
+ * Computes the centroid of an area geometry.
+ * <h2>Algorithm</h2>
+ * Based on the usual algorithm for calculating
+ * the centroid as a weighted sum of the centroids
+ * of a decomposition of the area into (possibly overlapping) triangles.
+ * The algorithm has been extended to handle holes and multi-polygons.
+ * See <code>http://www.faqs.org/faqs/graphics/algorithms-faq/</code>
+ * for further details of the basic approach.
+ *
+ * @version 1.6
+ */
+public class CentroidArea
+{
+
+ private Coordinate basePt = null;// the point all triangles are based at
+ private Coordinate triangleCent3 = new Coordinate();// temporary variable to hold centroid of triangle
+ private double areasum2 = 0; /* Partial area sum */
+ private Coordinate cg3 = new Coordinate(); // partial centroid sum
+
+ public CentroidArea()
+ {
+ basePt = null;
+ }
+
+ /**
+ * Adds the area defined by a Geometry to the centroid total.
+ * If the geometry has no area it does not contribute to the centroid.
+ *
+ * @param geom the geometry to add
+ */
+ public void add(Geometry geom)
+ {
+ if (geom instanceof Polygon) {
+ Polygon poly = (Polygon) geom;
+ setBasePoint(poly.getExteriorRing().getCoordinateN(0));
+ add(poly);
+ }
+ else if (geom instanceof GeometryCollection) {
+ GeometryCollection gc = (GeometryCollection) geom;
+ for (int i = 0; i < gc.getNumGeometries(); i++) {
+ add(gc.getGeometryN(i));
+ }
+ }
+ }
+
+ /**
+ * Adds the area defined by an array of
+ * coordinates. The array must be a ring;
+ * i.e. end with the same coordinate as it starts with.
+ * @param ring an array of {@link Coordinate}s
+ */
+ public void add(Coordinate[] ring)
+ {
+ setBasePoint(ring[0]);
+ addShell(ring);
+ }
+
+ public Coordinate getCentroid()
+ {
+ Coordinate cent = new Coordinate();
+ cent.x = cg3.x / 3 / areasum2;
+ cent.y = cg3.y / 3 / areasum2;
+ return cent;
+ }
+
+ private void setBasePoint(Coordinate basePt)
+ {
+ if (this.basePt == null)
+ this.basePt = basePt;
+ }
+ private void add(Polygon poly)
+ {
+ addShell(poly.getExteriorRing().getCoordinates());
+ for (int i = 0; i < poly.getNumInteriorRing(); i++) {
+ addHole(poly.getInteriorRingN(i).getCoordinates());
+ }
+ }
+
+ private void addShell(Coordinate[] pts)
+ {
+
+ boolean isPositiveArea = ! CGAlgorithms.isCCW(pts);
+ for (int i = 0; i < pts.length - 1; i++) {
+ addTriangle(basePt, pts[i], pts[i+1], isPositiveArea);
+ }
+ }
+ private void addHole(Coordinate[] pts)
+ {
+ boolean isPositiveArea = CGAlgorithms.isCCW(pts);
+ for (int i = 0; i < pts.length - 1; i++) {
+ addTriangle(basePt, pts[i], pts[i+1], isPositiveArea);
+ }
+ }
+ private void addTriangle(Coordinate p0, Coordinate p1, Coordinate p2, boolean isPositiveArea)
+ {
+ double sign = (isPositiveArea) ? 1.0 : -1.0;
+ centroid3( p0, p1, p2, triangleCent3 );
+ double area2 = area2( p0, p1, p2 );
+ cg3.x += sign * area2 * triangleCent3.x;
+ cg3.y += sign * area2 * triangleCent3.y;
+ areasum2 += sign * area2;
+ }
+ /**
+ * Returns three times the centroid of the triangle p1-p2-p3.
+ * The factor of 3 is
+ * left in to permit division to be avoided until later.
+ */
+ private static void centroid3( Coordinate p1, Coordinate p2, Coordinate p3, Coordinate c )
+ {
+ c.x = p1.x + p2.x + p3.x;
+ c.y = p1.y + p2.y + p3.y;
+ return;
+ }
+
+ /**
+ * Returns twice the signed area of the triangle p1-p2-p3,
+ * positive if a,b,c are oriented ccw, and negative if cw.
+ */
+ private static double area2( Coordinate p1, Coordinate p2, Coordinate p3 )
+ {
+ return
+ (p2.x - p1.x) * (p3.y - p1.y) -
+ (p3.x - p1.x) * (p2.y - p1.y);
+ }
+
+
+}
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidLine.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,98 @@
+
+/*
+ * 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.*;
+
+/**
+ * Computes the centroid of a linear geometry.
+ * <h2>Algorithm</h2>
+ * Compute the average of the midpoints
+ * of all line segments weighted by the segment length.
+ *
+ * @version 1.6
+ */
+public class CentroidLine
+{
+ private Coordinate centSum = new Coordinate();
+ private double totalLength = 0.0;
+
+ public CentroidLine()
+ {
+ }
+
+ /**
+ * Adds the linestring(s) defined by a Geometry to the centroid total.
+ * If the geometry is not linear it does not contribute to the centroid
+ * @param geom the geometry to add
+ */
+ public void add(Geometry geom)
+ {
+ if (geom instanceof LineString) {
+ add(geom.getCoordinates());
+ }
+ else if (geom instanceof GeometryCollection) {
+ GeometryCollection gc = (GeometryCollection) geom;
+ for (int i = 0; i < gc.getNumGeometries(); i++) {
+ add(gc.getGeometryN(i));
+ }
+ }
+ }
+
+ public Coordinate getCentroid()
+ {
+ Coordinate cent = new Coordinate();
+ cent.x = centSum.x / totalLength;
+ cent.y = centSum.y / totalLength;
+ return cent;
+ }
+
+ /**
+ * Adds the length defined by an array of coordinates.
+ * @param pts an array of {@link Coordinate}s
+ */
+ public void add(Coordinate[] pts)
+ {
+ for (int i = 0; i < pts.length - 1; i++) {
+ double segmentLen = pts[i].distance(pts[i + 1]);
+ totalLength += segmentLen;
+
+ double midx = (pts[i].x + pts[i + 1].x) / 2;
+ centSum.x += segmentLen * midx;
+ double midy = (pts[i].y + pts[i + 1].y) / 2;
+ centSum.y += segmentLen * midy;
+ }
+ }
+
+}
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/CentroidPoint.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,91 @@
+
+/*
+ * 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.*;
+
+/**
+ * Computes the centroid of a point geometry.
+ * <h2>Algorithm</h2>
+ * Compute the average of all points.
+ *
+ * @version 1.6
+ */
+public class CentroidPoint
+{
+ private int ptCount = 0;
+ private Coordinate centSum = new Coordinate();
+
+ public CentroidPoint()
+ {
+ }
+
+ /**
+ * Adds the point(s) defined by a Geometry to the centroid total.
+ * If the geometry is not of dimension 0 it does not contribute to the centroid.
+ * @param geom the geometry to add
+ */
+ public void add(Geometry geom)
+ {
+ if (geom instanceof Point) {
+ add(geom.getCoordinate());
+ }
+ else if (geom instanceof GeometryCollection) {
+ GeometryCollection gc = (GeometryCollection) geom;
+ for (int i = 0; i < gc.getNumGeometries(); i++) {
+ add(gc.getGeometryN(i));
+ }
+ }
+ }
+
+ /**
+ * Adds the length defined by an array of coordinates.
+ * @param pts an array of {@link Coordinate}s
+ */
+ public void add(Coordinate pt)
+ {
+ ptCount += 1;
+ centSum.x += pt.x;
+ centSum.y += pt.y;
+ }
+
+ public Coordinate getCentroid()
+ {
+ Coordinate cent = new Coordinate();
+ cent.x = centSum.x / ptCount;
+ cent.y = centSum.y / ptCount;
+ return cent;
+ }
+
+}
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/ConvexHull.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,356 @@
+
+
+/*
+ * 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.*;
+import com.vividsolutions.jts.util.Assert;
+
+import java.util.*;
+import com.vividsolutions.jts.util.UniqueCoordinateArrayFilter;
+
+/**
+ * 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.
+ * Uses the Graham Scan algorithm.
+ *
+ *@version 1.6
+ */
+public class ConvexHull
+{
+ private PointLocator pointLocator = new PointLocator();
+ //private CGAlgorithms cgAlgorithms = new RobustCGAlgorithms();
+ private Geometry geometry;
+ private GeometryFactory factory;
+
+ /**
+ * Create a new convex hull construction for the input {@link Geometry}.
+ */
+ public ConvexHull(Geometry geometry)
+ {
+ this.geometry = geometry;
+ }
+
+ /**
+ * Returns a {@link Geometry} that represents the convex hull of the input
+ * geometry.
+ * The geometry will contain the minimal number of points needed to
+ * represent the convex hull. In particular, no more than two consecutive
+ * points will be collinear.
+ *
+ * @return if the convex hull contains 3 or more points, a {@link Polygon};
+ * 2 points, a {@link LineString};
+ * 1 point, a {@link Point};
+ * 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 (pts.length == 1) {
+ return factory.createPoint(pts[0]);
+ }
+ if (pts.length == 2) {
+ return factory.createLineString(pts);
+ }
+
+ // 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);
+ }
+
+ // Use Graham scan to find convex hull.
+ Stack cHS = grahamScan(pspts);
+
+ // Convert stack to an array.
+ Coordinate[] cH = toCoordinateArray(cHS);
+
+ // Convert array to linear ring.
+ return lineOrPolygon(cH);
+ }
+
+ /**
+ * An alternative to Stack.toArray, which is not present in earlier versions
+ * of Java.
+ */
+ protected Coordinate[] toCoordinateArray(Stack stack) {
+ Coordinate[] coordinates = new Coordinate[stack.size()];
+ for (int i = 0; i < stack.size(); i++) {
+ Coordinate coordinate = (Coordinate) stack.get(i);
+ coordinates[i] = coordinate;
+ }
+ 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);
+ }
+ 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]);
+ }
+ }
+ Coordinate[] rP = (Coordinate[]) reducedSet.toArray(new Coordinate[0]);
+
+ // Return this array as the reduced problem.
+ return rP;
+ }
+
+ private Coordinate[] preSort(Coordinate[] pts) {
+ Coordinate t;
+
+ // find the lowest point in the set. If two or more points have
+ // the same minimum y coordinate choose the one with the minimu x.
+ // This focal point is put in array location pts[0].
+ for (int i = 1; i < pts.length; i++) {
+ if ((pts[i].y < pts[0].y) || ((pts[i].y == pts[0].y) && (pts[i].x < pts[0].x))) {
+ t = pts[0];
+ pts[0] = pts[i];
+ pts[i] = t;
+ }
+ }
+
+ // sort the points radially around the focal point.
+ 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]);
+ p = (Coordinate) ps.push(c[2]);
+ for (int i = 3; i < c.length; i++) {
+ p = (Coordinate) ps.pop();
+ while (CGAlgorithms.computeOrientation((Coordinate) ps.peek(), p, c[i]) > 0) {
+ p = (Coordinate) ps.pop();
+ }
+ p = (Coordinate) ps.push(p);
+ p = (Coordinate) ps.push(c[i]);
+ }
+ p = (Coordinate) ps.push(c[0]);
+ 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
+ */
+ private boolean isBetween(Coordinate c1, Coordinate c2, Coordinate c3) {
+ if (CGAlgorithms.computeOrientation(c1, c2, c3) != 0) {
+ return false;
+ }
+ if (c1.x != c3.x) {
+ if (c1.x <= c2.x && c2.x <= c3.x) {
+ return true;
+ }
+ if (c3.x <= c2.x && c2.x <= c1.x) {
+ return true;
+ }
+ }
+ if (c1.y != c3.y) {
+ if (c1.y <= c2.y && c2.y <= c3.y) {
+ return true;
+ }
+ if (c3.y <= c2.y && c2.y <= c1.y) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private BigQuad bigQuad(Coordinate[] pts) {
+ BigQuad bigQuad = new BigQuad();
+ bigQuad.northmost = pts[0];
+ bigQuad.southmost = pts[0];
+ bigQuad.westmost = pts[0];
+ bigQuad.eastmost = pts[0];
+ for (int i = 1; i < pts.length; i++) {
+ if (pts[i].x < bigQuad.westmost.x) {
+ bigQuad.westmost = pts[i];
+ }
+ if (pts[i].x > bigQuad.eastmost.x) {
+ bigQuad.eastmost = pts[i];
+ }
+ if (pts[i].y < bigQuad.southmost.y) {
+ bigQuad.southmost = pts[i];
+ }
+ if (pts[i].y > bigQuad.northmost.y) {
+ bigQuad.northmost = pts[i];
+ }
+ }
+ return bigQuad;
+ }
+
+ /**
+ *@param vertices the vertices of a linear ring, which may or may not be
+ * flattened (i.e. vertices collinear)
+ *@return a 2-vertex <code>LineString</code> if the vertices are
+ * collinear; otherwise, a <code>Polygon</code> with unnecessary
+ * (collinear) vertices removed
+ */
+ private Geometry lineOrPolygon(Coordinate[] coordinates) {
+
+ coordinates = cleanRing(coordinates);
+ if (coordinates.length == 3) {
+ return factory.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);
+ }
+
+ /**
+ *@param vertices the vertices of a linear ring, which may or may not be
+ * flattened (i.e. vertices collinear)
+ *@return the coordinates with unnecessary (collinear) vertices
+ * removed
+ */
+ private Coordinate[] cleanRing(Coordinate[] original) {
+ Assert.equals(original[0], original[original.length - 1]);
+ ArrayList cleanedRing = new ArrayList();
+ Coordinate previousDistinctCoordinate = null;
+ for (int i = 0; i <= original.length - 2; i++) {
+ Coordinate currentCoordinate = original[i];
+ Coordinate nextCoordinate = original[i+1];
+ if (currentCoordinate.equals(nextCoordinate)) {
+ continue;
+ }
+ if (previousDistinctCoordinate != null
+ && isBetween(previousDistinctCoordinate, currentCoordinate, nextCoordinate)) {
+ continue;
+ }
+ cleanedRing.add(currentCoordinate);
+ previousDistinctCoordinate = currentCoordinate;
+ }
+ cleanedRing.add(original[original.length - 1]);
+ Coordinate[] cleanedRingCoordinates = new Coordinate[cleanedRing.size()];
+ return (Coordinate[]) cleanedRing.toArray(cleanedRingCoordinates);
+ }
+
+ private static class BigQuad {
+ public Coordinate northmost;
+ public Coordinate southmost;
+ public Coordinate westmost;
+ public Coordinate eastmost;
+ }
+
+}
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/HCoordinate.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,122 @@
+
+
+
+/*
+ * 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.
+ *
+ * @version 1.6
+ */
+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.
+ */
+ public static Coordinate intersection(
+ Coordinate p1, Coordinate p2,
+ Coordinate q1, Coordinate q2)
+ throws NotRepresentableException
+ {
+ HCoordinate l1 = new HCoordinate(new HCoordinate(p1), new HCoordinate(p2));
+ HCoordinate l2 = new HCoordinate(new HCoordinate(q1), new HCoordinate(q2));
+ HCoordinate intHCoord = new HCoordinate(l1, l2);
+ Coordinate intPt = intHCoord.getCoordinate();
+ return intPt;
+ }
+
+
+ public double x,y,w;
+
+ 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(Coordinate p) {
+ x = p.x;
+ y = p.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 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 Coordinate getCoordinate() throws NotRepresentableException {
+ Coordinate p = new Coordinate();
+ p.x = getX();
+ p.y = getY();
+ return p;
+ }
+}
Added: packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java
===================================================================
--- packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java (rev 0)
+++ packages/jts/branches/upstream/current/src/com/vividsolutions/jts/algorithm/InteriorPointArea.java 2007-06-15 19:34:59 UTC (rev 877)
@@ -0,0 +1,162 @@
+
+/*
+ * 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 V8