Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members

geosAlgorithm.h

00001 /**********************************************************************
00002  * $Id: geosAlgorithm.h,v 1.9 2004/11/23 19:53:07 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  * $Log: geosAlgorithm.h,v $
00016  * Revision 1.9  2004/11/23 19:53:07  strk
00017  * Had LineIntersector compute Z by interpolation.
00018  *
00019  * Revision 1.8  2004/11/06 08:16:46  strk
00020  * Fixed CGAlgorithms::isCCW from JTS port.
00021  * Code cleanup in IsValidOp.
00022  *
00023  * Revision 1.7  2004/10/21 22:29:54  strk
00024  * Indentation changes and some more COMPUTE_Z rules
00025  *
00026  * Revision 1.6  2004/09/13 10:12:49  strk
00027  * Added invalid coordinates checks in IsValidOp.
00028  * Cleanups.
00029  *
00030  * Revision 1.5  2004/07/19 13:19:31  strk
00031  * Documentation fixes
00032  *
00033  * Revision 1.4  2004/07/08 19:34:49  strk
00034  * Mirrored JTS interface of CoordinateSequence, factory and
00035  * default implementations.
00036  * Added DefaultCoordinateSequenceFactory::instance() function.
00037  *
00038  * Revision 1.3  2004/07/07 10:29:54  strk
00039  * Adjusted exceptions documentation.
00040  *
00041  * Revision 1.2  2004/07/07 09:38:12  strk
00042  * Dropped WKTWriter::stringOfChars (implemented by std::string).
00043  * Dropped WKTWriter default constructor (internally created GeometryFactory).
00044  * Updated XMLTester to respect the changes.
00045  * Main documentation page made nicer.
00046  *
00047  * Revision 1.1  2004/07/02 13:20:42  strk
00048  * Header files moved under geos/ dir.
00049  *
00050  * Revision 1.32  2004/06/30 20:59:12  strk
00051  * Removed GeoemtryFactory copy from geometry constructors.
00052  * Enforced const-correctness on GeometryFactory arguments.
00053  *
00054  * Revision 1.31  2004/04/20 12:47:57  strk
00055  * MinimumDiameter leaks plugged.
00056  *
00057  * Revision 1.30  2004/03/17 02:00:33  ybychkov
00058  * "Algorithm" upgraded to JTS 1.4
00059  *
00060  * Revision 1.29  2004/02/27 17:42:15  strk
00061  * made CGAlgorithms::signedArea() and CGAlgorithms::length() arguments const-correct
00062  *
00063  * Revision 1.28  2003/11/07 01:23:42  pramsey
00064  * Add standard CVS headers licence notices and copyrights to all cpp and h
00065  * files.
00066  *
00067  *
00068  **********************************************************************/
00069 
00070 
00071 #ifndef GEOS_ALGORITHM_H
00072 #define GEOS_ALGORITHM_H
00073 
00074 #include <memory>
00075 #include <geos/geom.h>
00076 #include <geos/util.h>
00077 #include <geos/platform.h>
00078 #include <geos/indexBintree.h>
00079 #include <geos/indexStrtree.h>
00080 #include <geos/indexStrtree.h>
00081 #include <geos/indexChain.h>
00082 
00083 namespace geos {
00084 
00085 class Coordinate;
00086 
00087 /*
00088  * \class NotRepresentableException geosAlgorithm.h geos/geosAlgorithm.h
00089  * \brief
00090  * Indicates that a HCoordinate has been computed which is
00091  * not representable on the Cartesian plane.
00092  *
00093  * @version 1.4
00094  * @see HCoordinate
00095  */
00096 class NotRepresentableException: public GEOSException {
00097 public:
00098         NotRepresentableException();
00099         NotRepresentableException(string msg);
00100         ~NotRepresentableException();
00101 };
00102 
00103 class PointInRing{
00104 public:
00105         virtual ~PointInRing(){};
00106         virtual bool isInside(const Coordinate& pt)=0;
00107 };
00108 
00109 class CGAlgorithms {
00110 public:
00111         enum {
00112                 CLOCKWISE=-1,
00113                 COLLINEAR,
00114                 COUNTERCLOCKWISE
00115         };
00116         enum {
00117                 RIGHT=-1,
00118                 LEFT,
00119                 STRAIGHT
00120         };
00121         CGAlgorithms(){};
00122 
00136         static bool isPointInRing(const Coordinate& p, const CoordinateSequence* ring);
00144         static bool isOnLine(const Coordinate& p, const CoordinateSequence* pt);
00145 
00146         /*
00147          * Computes whether a ring defined by an array of Coordinate is
00148          * oriented counter-clockwise.
00149          * 
00150          *  - The list of points is assumed to have the first and last
00151          *    points equal.
00152          *  - This will handle coordinate lists which contain repeated points.
00153          *  - If the ring is invalid, the answer returned may not be correct.
00154          * 
00155          *
00156          * @param ring an array of coordinates forming a ring
00157          * @return <code>true</code> if the ring is oriented counter-clockwise.
00158          */
00159         static bool isCCW(const CoordinateSequence* ring);
00160 
00170         static int computeOrientation(const Coordinate& p1, const Coordinate& p2, const Coordinate& q);
00171         static double distancePointLine(const Coordinate& p,const Coordinate& A,const Coordinate& B);
00181         static double distancePointLinePerpendicular(const Coordinate& p,const Coordinate& A,const Coordinate& B);
00182         static double distanceLineLine(const Coordinate& A, const Coordinate& B, const Coordinate& C, const Coordinate& D);
00183         static double signedArea(const CoordinateSequence* ring);
00190         static double length(const CoordinateSequence* pts);
00204         static int orientationIndex(const Coordinate& p1,const Coordinate& p2,const Coordinate& q);
00205 
00206 };
00207 
00209 class HCoordinate {
00210 public:
00211         static Coordinate* intersection(Coordinate& p1,Coordinate& p2,Coordinate& q1,Coordinate& q2);
00212         double x,y,w;
00213         HCoordinate();
00214         HCoordinate(double _x, double _y, double _w);
00215         HCoordinate(Coordinate& p);
00216         HCoordinate(HCoordinate p1, HCoordinate p2);
00217         double getX();
00218         double getY();
00219         Coordinate* getCoordinate();
00220 };
00221 
00222 class SimplePointInRing: public PointInRing {
00223 public:
00224         SimplePointInRing(LinearRing *ring);
00225         virtual ~SimplePointInRing();
00226         bool isInside(const Coordinate& pt);
00227 private:
00228         const CoordinateSequence* pts;
00229 };
00230 
00231 class LineIntersector{
00232 public: 
00233         // Return a Z value being the interpolation of Z from p0 and p1 at
00234         // the given point p
00235         static double interpolateZ(const Coordinate &p, const Coordinate &p0, const Coordinate &p1);
00236         static double computeEdgeDistance(const Coordinate& p, const Coordinate& p0, const Coordinate& p1);
00237         static double nonRobustComputeEdgeDistance(const Coordinate& p,const Coordinate& p1,const Coordinate& p2);
00238         LineIntersector();
00239         virtual ~LineIntersector();
00240 
00241         /*
00242          * Tests whether either intersection point is an interior point of
00243          * one of the input segments.
00244          *
00245          * @return <code>true</code> if either intersection point is in
00246          * the interior of one of the input segments
00247          */
00248         virtual bool isInteriorIntersection();
00249 
00250         /*
00251          * Tests whether either intersection point is an interior point
00252          * of the specified input segment.
00253          *
00254          * @return <code>true</code> if either intersection point is in
00255          * the interior of the input segment
00256          */
00257         virtual bool isInteriorIntersection(int inputLineIndex);
00258 
00259         virtual void setMakePrecise(const PrecisionModel *newPM);
00260 
00261         virtual void setPrecisionModel(const PrecisionModel *newPM);
00262 
00263         /*
00264          * Compute the intersection of a point p and the line p1-p2.
00265          * This function computes the boolean value of the hasIntersection test.
00266          * The actual value of the intersection (if there is one)
00267          * is equal to the value of <code>p</code>.
00268          */
00269         virtual void computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2)=0;
00270 
00271         enum {
00272                 DONT_INTERSECT,
00273                 DO_INTERSECT,
00274                 COLLINEAR
00275         };
00276 
00277         virtual void computeIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& p3, const Coordinate& p4);
00278 
00279         virtual string toString() const;
00280 
00281         virtual bool hasIntersection() const;
00282 
00283         virtual int getIntersectionNum() const;
00284 
00285         virtual const Coordinate& getIntersection(int intIndex) const;
00286 
00287         static bool isSameSignAndNonZero(double a,double b);
00288 
00289         virtual bool isIntersection(const Coordinate& pt) const;
00290         virtual bool isProper() const;
00291         virtual const Coordinate& getIntersectionAlongSegment(int segmentIndex,int intIndex);
00292         virtual int getIndexAlongSegment(int segmentIndex,int intIndex);
00293         virtual double getEdgeDistance(int geomIndex,int intIndex) const;
00294 protected:
00299         const PrecisionModel *precisionModel;
00300         int result;
00301         Coordinate inputLines[2][2];
00302         Coordinate intPt[2];
00307         int intLineIndex[2][2];
00308         bool isProperVar;
00309         Coordinate pa;
00310         Coordinate pb;
00311         virtual bool isCollinear() const;
00312         virtual int computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2)=0;
00313         virtual bool isEndPoint() const;
00314         virtual void computeIntLineIndex();
00315         virtual void computeIntLineIndex(int segmentIndex);
00316 };
00317 
00318 class RobustDeterminant {
00319 public:
00320         static int signOfDet2x2(double x1,double y1,double x2,double y2);
00321 };
00322 
00323 class RobustLineIntersector: public LineIntersector {
00324 public:
00325         RobustLineIntersector();
00326         virtual ~RobustLineIntersector();
00327         void computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2);
00328         int computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2);
00329 private:
00330 //      bool between(Coordinate& p1,Coordinate& p2,Coordinate& q);
00331         int computeCollinearIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2);
00332         Coordinate* intersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2) const;
00333         void normalize(Coordinate *n1,Coordinate *n2,Coordinate *n3,Coordinate *n4,Coordinate *normPt) const;
00334         double smallestInAbsValue(double x1,double x2,double x3,double x4) const;
00344         bool isInSegmentEnvelopes(const Coordinate& intPt);
00345 };
00346 
00347 class NonRobustLineIntersector: public LineIntersector {
00348 public:
00349         NonRobustLineIntersector();
00350         void computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2);
00351 protected:
00352         int computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& p3,const Coordinate& p4);
00353 private:
00354         int computeCollinearIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& p3,const Coordinate& p4);
00355         double rParameter(const Coordinate& p1,const Coordinate& p2,const Coordinate& p) const;
00356 };
00357 
00358 /*
00359  * Stub version of RobustCGAlgorithms for backwards compatibility.
00360  * Will be deprecated in next release - use CGAlgorithms instead.
00361  */
00362 class RobustCGAlgorithms: public CGAlgorithms {
00363 };
00364 
00365 class NonRobustCGAlgorithms: public CGAlgorithms {
00366 public:
00367         NonRobustCGAlgorithms();
00368         ~NonRobustCGAlgorithms();
00378         static bool isPointInRing(const Coordinate& p, const CoordinateSequence* ring);
00379 //      static bool isOnLine(const Coordinate& p, const CoordinateSequence* pt) const;
00390         static bool isCCW(const CoordinateSequence* ring);
00391         static int computeOrientation(const Coordinate& p1,const Coordinate& p2,const Coordinate& q);
00392 };
00393 
00394 class SimplePointInAreaLocator {
00395 public:
00396         static int locate(const Coordinate& p, const Geometry *geom);
00397         static bool containsPointInPolygon(const Coordinate& p,const Polygon *poly);
00398 private:
00399         static bool containsPoint(const Coordinate& p,const Geometry *geom);
00400 };
00401 
00402 /*
00403  * \class PointLocator geosAlgorithm.h geos/geosAlgorithm.h
00404  *
00405  * \brief
00406  * Computes the topological relationship (Location)
00407  * of a single point to a Geometry.
00408  *
00409  * The algorithm obeys the SFS boundaryDetermination rule to correctly determine
00410  * whether the point lies on the boundary or not.
00411  * Note that instances of this class are not reentrant.
00412  * @version 1.3
00413  */
00414 class PointLocator {
00415 public:
00416         PointLocator();
00417         ~PointLocator();
00418         int locate(const Coordinate& p,const Geometry *geom);
00419         bool intersects(const Coordinate& p,const Geometry *geom);
00420         int locate(const Coordinate& p,const LineString *l);
00421         int locate(const Coordinate& p,const LinearRing *ring);
00422         int locate(const Coordinate& p,const Polygon *poly);
00423 private:
00424         bool isIn;         // true if the point lies in or on any Geometry element
00425         int numBoundaries;    // the number of sub-elements whose boundaries the point lies in
00426         void computeLocation(const Coordinate& p,const Geometry *geom);
00427         void updateLocationInfo(int loc);
00428 };
00429 
00430 
00431 class MCPointInRing: public PointInRing {
00432 public:
00433         MCPointInRing(LinearRing *newRing);
00434         virtual ~MCPointInRing();
00435         bool isInside(const Coordinate& pt);
00436         void testLineSegment(Coordinate& p,LineSegment *seg);
00437         class MCSelecter: public MonotoneChainSelectAction {
00438         private:
00439                 Coordinate p;
00440                 MCPointInRing *parent;
00441         public:
00442                 MCSelecter(const Coordinate& newP,MCPointInRing *prt);
00443             void select(LineSegment *ls);
00444         };
00445 private:
00446         LinearRing *ring;
00447         BinTreeInterval *interval;
00448         CoordinateSequence *pts;
00449         Bintree *tree;
00450         int crossings;  // number of segment/ray crossings
00451         void buildIndex();
00452         void testMonotoneChain(Envelope *rayEnv,MCSelecter *mcSelecter,indexMonotoneChain *mc);
00453 };
00454 
00455 class SIRtreePointInRing: public PointInRing {
00456 private:
00457         LinearRing *ring;
00458         SIRtree *sirTree;
00459         int crossings;  // number of segment/ray crossings
00460         void buildIndex();
00461         void testLineSegment(const Coordinate& p,LineSegment *seg);
00462 public:
00463         SIRtreePointInRing(LinearRing *newRing);
00464         bool isInside(const Coordinate& pt);
00465 };
00466 
00467 class CentroidPoint {
00468 private:
00469         int ptCount;
00470         Coordinate* centSum;
00471 public:
00472         CentroidPoint();
00473         virtual ~CentroidPoint();
00474         void add(const Geometry *geom);
00475         void add(const Coordinate *pt);
00476         Coordinate* getCentroid() const;
00477 };
00478 
00479 class CentroidLine {
00480 private:
00481         Coordinate* centSum;
00482         double totalLength;
00483 public:
00484         CentroidLine();
00485         virtual ~CentroidLine();
00486         void add(const Geometry *geom);
00487         void add(const CoordinateSequence *pts);
00488         Coordinate* getCentroid() const;
00489 };
00490 
00491 /*
00492  * \class CentroidArea geosAlgorithm.h geos/geosAlgorithm.h
00493  *
00494  * \brief Computes the centroid of an area geometry.
00495  *
00496  * Algorithm:
00497  *
00498  * Based on the usual algorithm for calculating
00499  * the centroid as a weighted sum of the centroids
00500  * of a decomposition of the area into (possibly overlapping) triangles.
00501  * The algorithm has been extended to handle holes and multi-polygons.
00502  * See <code>http://www.faqs.org/faqs/graphics/algorithms-faq/</code>
00503  * for further details of the basic approach.
00504  */
00505 class CentroidArea {
00506 public:
00507         CentroidArea();
00508         virtual ~CentroidArea();
00509         void add(const Geometry *geom);
00510         void add(const CoordinateSequence *ring);
00511         Coordinate* getCentroid() const;
00512 private:
00513         CGAlgorithms *cga;
00514         Coordinate* basePt;// the point all triangles are based at
00515         Coordinate* triangleCent3;// temporary variable to hold centroid of triangle
00516         double areasum2;        /* Partial area sum */
00517         Coordinate* cg3; // partial centroid sum
00518         void setBasePoint(const Coordinate *newbasePt);
00519         void add(const Polygon *poly);
00520         void addShell(const CoordinateSequence *pts);
00521         void addHole(const CoordinateSequence *pts);
00522         inline void addTriangle(const Coordinate &p0, const Coordinate &p1, const Coordinate &p2,bool isPositiveArea);
00523         static inline  void centroid3(const Coordinate &p1,const Coordinate &p2,const Coordinate &p3,Coordinate *c);
00524         static inline double area2(const Coordinate &p1,const Coordinate &p2,const Coordinate &p3);
00525 };
00526 
00527 /*
00528  * \class InteriorPointPoint geosAlgorithm.h geos/geosAlgorithm.h
00529  * \brief
00530  * Computes a point in the interior of an point geometry.
00531  *
00532  * Algorithm:
00533  *
00534  * Find a point which is closest to the centroid of the geometry.
00535  */
00536 class InteriorPointPoint {
00537 private:
00538         const Coordinate* centroid;
00539         double minDistance;
00540         Coordinate *interiorPoint;
00541         void add(const Geometry *geom);
00542         void add(const Coordinate *point);
00543 public:
00544         InteriorPointPoint(const Geometry *g);
00545         virtual ~InteriorPointPoint();
00546         Coordinate* getInteriorPoint() const;
00547 };
00548 
00549 /*
00550  * Computes a point in the interior of an linear geometry.
00551  * <h2>Algorithm</h2>
00552  * <ul>
00553  * <li>Find an interior vertex which is closest to
00554  * the centroid of the linestring.
00555  * <li>If there is no interior vertex, find the endpoint which is
00556  * closest to the centroid.
00557  * </ul>
00558  */
00559 class InteriorPointLine {
00560 public:
00561         InteriorPointLine(Geometry *g);
00562         virtual ~InteriorPointLine();
00563         Coordinate* getInteriorPoint() const;
00564 private:
00565         const Coordinate *centroid;
00566         double minDistance;
00567         Coordinate *interiorPoint;
00568         void addInterior(const Geometry *geom);
00569         void addInterior(const CoordinateSequence *pts);
00570         void addEndpoints(const Geometry *geom);
00571         void addEndpoints(const CoordinateSequence *pts);
00572         void add(const Coordinate *point);
00573 };
00574 
00575 /*
00576  * Computes a point in the interior of an area geometry.
00577  *
00578  * <h2>Algorithm</h2>
00579  * <ul>
00580  *   <li>Find the intersections between the geometry
00581  *       and the horizontal bisector of the area's envelope
00582  *   <li>Pick the midpoint of the largest intersection (the intersections
00583  *       will be lines and points)
00584  * </ul>
00585  *
00586  * <b>
00587  * Note: If a fixed precision model is used,
00588  * in some cases this method may return a point
00589  * which does not lie in the interior.
00590  * </b>
00591  */
00592 class InteriorPointArea {
00593 private:
00594         static double avg(double a, double b);
00595         const GeometryFactory *factory;
00596         Coordinate *interiorPoint;
00597         double maxWidth;
00598         void add(const Geometry *geom);
00599 public:
00600         InteriorPointArea(const Geometry *g);
00601         virtual ~InteriorPointArea();
00602         Coordinate* getInteriorPoint() const;
00603         void addPolygon(const Geometry *geometry);
00604         Coordinate* centre(const Envelope *envelope) const;
00605 protected:
00606         const Geometry *widestGeometry(const Geometry *geometry);
00607         const Geometry *widestGeometry(const GeometryCollection *gc);
00608         LineString *horizontalBisector(const Geometry *geometry);
00609 
00610 };
00611 
00612 class BigQuad {
00613 public:
00614         Coordinate northmost;
00615         Coordinate southmost;
00616         Coordinate westmost;
00617         Coordinate eastmost;
00618 };
00619 
00620 class ConvexHull {
00621 private:
00622         PointLocator *pointLocator;
00623         //CGAlgorithms *cgAlgorithms;
00624         const Geometry *geometry;
00625         const GeometryFactory *factory;
00626         CoordinateSequence* reduce(const CoordinateSequence *pts);
00627         CoordinateSequence* preSort(CoordinateSequence *pts);
00628         CoordinateSequence* grahamScan(const CoordinateSequence *c);
00629         void radialSort(CoordinateSequence *p);
00630         int polarCompare(Coordinate o, Coordinate p, Coordinate q);
00631         bool isBetween(Coordinate c1, Coordinate c2, Coordinate c3);
00632     BigQuad* makeBigQuad(const CoordinateSequence *pts);
00633         Geometry* lineOrPolygon(CoordinateSequence *newCoordinates);
00634         CoordinateSequence* cleanRing(CoordinateSequence *original);
00635 public:
00636         ConvexHull(const Geometry *newGeometry);
00637         ~ConvexHull();
00638         Geometry* getConvexHull();
00639 };
00640 
00641 
00642 /*
00643  * Computes the minimum diameter of a {@link Geometry}.
00644  * The minimum diameter is defined to be the
00645  * width of the smallest band that
00646  * contains the geometry,
00647  * where a band is a strip of the plane defined
00648  * by two parallel lines.
00649  * This can be thought of as the smallest hole that the geometry can be
00650  * moved through, with a single rotation.
00651  * <p>
00652  * The first step in the algorithm is computing the convex hull of the Geometry.
00653  * If the input Geometry is known to be convex, a hint can be supplied to
00654  * avoid this computation.
00655  *
00656  * @see ConvexHull
00657  *
00658  */
00659 class MinimumDiameter {
00660 private:
00661         const Geometry* inputGeom;
00662         bool isConvex;
00663         LineSegment* minBaseSeg;
00664         Coordinate* minWidthPt;
00665         int minPtIndex;
00666         double minWidth;
00667         void computeMinimumDiameter();
00668         void computeWidthConvex(const Geometry* geom);
00676         void computeConvexRingMinDiameter(const CoordinateSequence *pts);
00677         int findMaxPerpDistance(const CoordinateSequence* pts, LineSegment* seg, int startIndex);
00678         static int getNextIndex(const CoordinateSequence* pts, int index);
00679 public:
00680         ~MinimumDiameter();
00681 
00687         MinimumDiameter(const Geometry* newInputGeom);
00688 
00699         MinimumDiameter(const Geometry* newInputGeom,const bool newIsConvex);
00700 
00706         double getLength();
00707 
00713         Coordinate* getWidthCoordinate();
00714 
00720         LineString* getSupportingSegment();
00721 
00727         LineString* getDiameter();
00728 };
00729 
00730 }
00731 #endif

Generated on Sat May 28 11:24:08 2005 for GEOS by  doxygen 1.4.2