Main Page | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | Related Pages

geosAlgorithm.h

00001 /**********************************************************************
00002  * $Id: geosAlgorithm.h,v 1.6 2004/09/13 10:12:49 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.6  2004/09/13 10:12:49  strk
00017  * Added invalid coordinates checks in IsValidOp.
00018  * Cleanups.
00019  *
00020  * Revision 1.5  2004/07/19 13:19:31  strk
00021  * Documentation fixes
00022  *
00023  * Revision 1.4  2004/07/08 19:34:49  strk
00024  * Mirrored JTS interface of CoordinateSequence, factory and
00025  * default implementations.
00026  * Added DefaultCoordinateSequenceFactory::instance() function.
00027  *
00028  * Revision 1.3  2004/07/07 10:29:54  strk
00029  * Adjusted exceptions documentation.
00030  *
00031  * Revision 1.2  2004/07/07 09:38:12  strk
00032  * Dropped WKTWriter::stringOfChars (implemented by std::string).
00033  * Dropped WKTWriter default constructor (internally created GeometryFactory).
00034  * Updated XMLTester to respect the changes.
00035  * Main documentation page made nicer.
00036  *
00037  * Revision 1.1  2004/07/02 13:20:42  strk
00038  * Header files moved under geos/ dir.
00039  *
00040  * Revision 1.32  2004/06/30 20:59:12  strk
00041  * Removed GeoemtryFactory copy from geometry constructors.
00042  * Enforced const-correctness on GeometryFactory arguments.
00043  *
00044  * Revision 1.31  2004/04/20 12:47:57  strk
00045  * MinimumDiameter leaks plugged.
00046  *
00047  * Revision 1.30  2004/03/17 02:00:33  ybychkov
00048  * "Algorithm" upgraded to JTS 1.4
00049  *
00050  * Revision 1.29  2004/02/27 17:42:15  strk
00051  * made CGAlgorithms::signedArea() and CGAlgorithms::length() arguments const-correct
00052  *
00053  * Revision 1.28  2003/11/07 01:23:42  pramsey
00054  * Add standard CVS headers licence notices and copyrights to all cpp and h
00055  * files.
00056  *
00057  *
00058  **********************************************************************/
00059 
00060 
00061 #ifndef GEOS_ALGORITHM_H
00062 #define GEOS_ALGORITHM_H
00063 
00064 #include <memory>
00065 #include <geos/geom.h>
00066 #include <geos/util.h>
00067 #include <geos/platform.h>
00068 #include <geos/indexBintree.h>
00069 #include <geos/indexStrtree.h>
00070 #include <geos/indexStrtree.h>
00071 #include <geos/indexChain.h>
00072 
00073 namespace geos {
00074 
00075 class Coordinate;
00076 
00077 /*
00078  * \class NotRepresentableException geosAlgorithm.h geos/geosAlgorithm.h
00079  * \brief
00080  * Indicates that a HCoordinate has been computed which is
00081  * not representable on the Cartesian plane.
00082  *
00083  * @version 1.4
00084  * @see HCoordinate
00085  */
00086 class NotRepresentableException: public GEOSException {
00087 public:
00088         NotRepresentableException();
00089         NotRepresentableException(string msg);
00090         ~NotRepresentableException();
00091 };
00092 
00093 class PointInRing{
00094 public:
00095         virtual ~PointInRing(){};
00096         virtual bool isInside(const Coordinate& pt)=0;
00097 };
00098 
00099 class CGAlgorithms {
00100 public:
00101         enum {
00102                 CLOCKWISE=-1,
00103                 COLLINEAR,
00104                 COUNTERCLOCKWISE
00105         };
00106         enum {
00107                 RIGHT=-1,
00108                 LEFT,
00109                 STRAIGHT
00110         };
00111         CGAlgorithms(){};
00112 
00126         static bool isPointInRing(const Coordinate& p, const CoordinateSequence* ring);
00134         static bool isOnLine(const Coordinate& p, const CoordinateSequence* pt);
00145         static bool isCCW(const CoordinateSequence* ring);
00155         static int computeOrientation(const Coordinate& p1, const Coordinate& p2, const Coordinate& q);
00156         static double distancePointLine(const Coordinate& p,const Coordinate& A,const Coordinate& B);
00166         static double distancePointLinePerpendicular(const Coordinate& p,const Coordinate& A,const Coordinate& B);
00167         static double distanceLineLine(const Coordinate& A, const Coordinate& B, const Coordinate& C, const Coordinate& D);
00168         static double signedArea(const CoordinateSequence* ring);
00175         static double length(const CoordinateSequence* pts);
00189         static int orientationIndex(const Coordinate& p1,const Coordinate& p2,const Coordinate& q);
00190 
00191 };
00192 
00194 class HCoordinate {
00195 public:
00196         static Coordinate* intersection(Coordinate& p1,Coordinate& p2,Coordinate& q1,Coordinate& q2);
00197         double x,y,w;
00198         HCoordinate();
00199         HCoordinate(double _x, double _y, double _w);
00200         HCoordinate(Coordinate& p);
00201         HCoordinate(HCoordinate p1, HCoordinate p2);
00202         double getX();
00203         double getY();
00204         Coordinate* getCoordinate();
00205 };
00206 
00207 class SimplePointInRing: public PointInRing {
00208 public:
00209         SimplePointInRing(LinearRing *ring);
00210         virtual ~SimplePointInRing();
00211         bool isInside(const Coordinate& pt);
00212 private:
00213         const CoordinateSequence* pts;
00214 };
00215 
00216 class LineIntersector{
00217 public: 
00218         static double computeEdgeDistance(const Coordinate& p, const Coordinate& p0, const Coordinate& p1);
00219         static double nonRobustComputeEdgeDistance(const Coordinate& p,const Coordinate& p1,const Coordinate& p2);
00220         LineIntersector();
00221         virtual ~LineIntersector();
00227         virtual bool isInteriorIntersection();
00233         virtual bool isInteriorIntersection(int inputLineIndex);
00234         virtual void setMakePrecise(const PrecisionModel *newPM);
00235         virtual void setPrecisionModel(const PrecisionModel *newPM);
00242         virtual void computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2) =0;
00243         enum {
00244                 DONT_INTERSECT,
00245                 DO_INTERSECT,
00246                 COLLINEAR
00247         };
00248         virtual void computeIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& p3, const Coordinate& p4);
00249         virtual string toString() const;
00250         virtual bool hasIntersection() const;
00251         virtual int getIntersectionNum() const;
00252         virtual const Coordinate& getIntersection(int intIndex) const;
00253         static bool isSameSignAndNonZero(double a,double b);
00254         virtual bool isIntersection(const Coordinate& pt) const;
00255         virtual bool isProper() const;
00256         virtual const Coordinate& getIntersectionAlongSegment(int segmentIndex,int intIndex);
00257         virtual int getIndexAlongSegment(int segmentIndex,int intIndex);
00258         virtual double getEdgeDistance(int geomIndex,int intIndex) const;
00259 protected:
00264         const PrecisionModel *precisionModel;
00265         int result;
00266         Coordinate inputLines[2][2];
00267         Coordinate intPt[2];
00272         int intLineIndex[2][2];
00273         bool isProperVar;
00274         Coordinate pa;
00275         Coordinate pb;
00276         virtual bool isCollinear() const;
00277         virtual int computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2)=0;
00278         virtual bool isEndPoint() const;
00279         virtual void computeIntLineIndex();
00280         virtual void computeIntLineIndex(int segmentIndex);
00281 };
00282 
00283 class RobustDeterminant {
00284 public:
00285         static int signOfDet2x2(double x1,double y1,double x2,double y2);
00286 };
00287 
00288 class RobustLineIntersector: public LineIntersector {
00289 public:
00290         RobustLineIntersector();
00291         virtual ~RobustLineIntersector();
00292         void computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2);
00293         int computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2);
00294 private:
00295 //      bool between(Coordinate& p1,Coordinate& p2,Coordinate& q);
00296         int computeCollinearIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2);
00297         Coordinate* intersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2) const;
00298         void normalize(Coordinate *n1,Coordinate *n2,Coordinate *n3,Coordinate *n4,Coordinate *normPt) const;
00299         double smallestInAbsValue(double x1,double x2,double x3,double x4) const;
00309         bool isInSegmentEnvelopes(const Coordinate& intPt);
00310 };
00311 
00312 class NonRobustLineIntersector: public LineIntersector {
00313 public:
00314         NonRobustLineIntersector();
00315         void computeIntersection(const Coordinate& p,const Coordinate& p1,const Coordinate& p2);
00316 protected:
00317         int computeIntersect(const Coordinate& p1,const Coordinate& p2,const Coordinate& p3,const Coordinate& p4);
00318 private:
00319         int computeCollinearIntersection(const Coordinate& p1,const Coordinate& p2,const Coordinate& p3,const Coordinate& p4);
00320         double rParameter(const Coordinate& p1,const Coordinate& p2,const Coordinate& p) const;
00321 };
00322 
00323 /*
00324  * Stub version of RobustCGAlgorithms for backwards compatibility.
00325  * Will be deprecated in next release - use CGAlgorithms instead.
00326  */
00327 class RobustCGAlgorithms: public CGAlgorithms {
00328 };
00329 
00330 class NonRobustCGAlgorithms: public CGAlgorithms {
00331 public:
00332         NonRobustCGAlgorithms();
00333         ~NonRobustCGAlgorithms();
00343         static bool isPointInRing(const Coordinate& p, const CoordinateSequence* ring);
00344 //      static bool isOnLine(const Coordinate& p, const CoordinateSequence* pt) const;
00355         static bool isCCW(const CoordinateSequence* ring);
00356         static int computeOrientation(const Coordinate& p1,const Coordinate& p2,const Coordinate& q);
00357 };
00358 
00359 class SimplePointInAreaLocator {
00360 public:
00361         static int locate(const Coordinate& p, const Geometry *geom);
00362         static bool containsPointInPolygon(const Coordinate& p,const Polygon *poly);
00363 private:
00364         static bool containsPoint(const Coordinate& p,const Geometry *geom);
00365 };
00366 
00367 /*
00368  * \class PointLocator geosAlgorithm.h geos/geosAlgorithm.h
00369  *
00370  * \brief
00371  * Computes the topological relationship (Location)
00372  * of a single point to a Geometry.
00373  *
00374  * The algorithm obeys the SFS boundaryDetermination rule to correctly determine
00375  * whether the point lies on the boundary or not.
00376  * Note that instances of this class are not reentrant.
00377  * @version 1.3
00378  */
00379 class PointLocator {
00380 public:
00381         PointLocator();
00382         ~PointLocator();
00383         int locate(const Coordinate& p,const Geometry *geom);
00384         bool intersects(const Coordinate& p,const Geometry *geom);
00385         int locate(const Coordinate& p,const LineString *l);
00386         int locate(const Coordinate& p,const LinearRing *ring);
00387         int locate(const Coordinate& p,const Polygon *poly);
00388 private:
00389         bool isIn;         // true if the point lies in or on any Geometry element
00390         int numBoundaries;    // the number of sub-elements whose boundaries the point lies in
00391         void computeLocation(const Coordinate& p,const Geometry *geom);
00392         void updateLocationInfo(int loc);
00393 };
00394 
00395 
00396 class MCPointInRing: public PointInRing {
00397 public:
00398         MCPointInRing(LinearRing *newRing);
00399         virtual ~MCPointInRing();
00400         bool isInside(const Coordinate& pt);
00401         void testLineSegment(Coordinate& p,LineSegment *seg);
00402         class MCSelecter: public MonotoneChainSelectAction {
00403         private:
00404                 Coordinate p;
00405                 MCPointInRing *parent;
00406         public:
00407                 MCSelecter(const Coordinate& newP,MCPointInRing *prt);
00408             void select(LineSegment *ls);
00409         };
00410 private:
00411         LinearRing *ring;
00412         BinTreeInterval *interval;
00413         CoordinateSequence *pts;
00414         Bintree *tree;
00415         int crossings;  // number of segment/ray crossings
00416         void buildIndex();
00417         void testMonotoneChain(Envelope *rayEnv,MCSelecter *mcSelecter,indexMonotoneChain *mc);
00418 };
00419 
00420 class SIRtreePointInRing: public PointInRing {
00421 private:
00422         LinearRing *ring;
00423         SIRtree *sirTree;
00424         int crossings;  // number of segment/ray crossings
00425         void buildIndex();
00426         void testLineSegment(const Coordinate& p,LineSegment *seg);
00427 public:
00428         SIRtreePointInRing(LinearRing *newRing);
00429         bool isInside(const Coordinate& pt);
00430 };
00431 
00432 class CentroidPoint {
00433 private:
00434         int ptCount;
00435         Coordinate* centSum;
00436 public:
00437         CentroidPoint();
00438         virtual ~CentroidPoint();
00439         void add(const Geometry *geom);
00440         void add(const Coordinate *pt);
00441         Coordinate* getCentroid() const;
00442 };
00443 
00444 class CentroidLine {
00445 private:
00446         Coordinate* centSum;
00447         double totalLength;
00448 public:
00449         CentroidLine();
00450         virtual ~CentroidLine();
00451         void add(const Geometry *geom);
00452         void add(const CoordinateSequence *pts);
00453         Coordinate* getCentroid() const;
00454 };
00455 
00456 /*
00457  * \class CentroidArea geosAlgorithm.h geos/geosAlgorithm.h
00458  *
00459  * \brief Computes the centroid of an area geometry.
00460  *
00461  * Algorithm:
00462  *
00463  * Based on the usual algorithm for calculating
00464  * the centroid as a weighted sum of the centroids
00465  * of a decomposition of the area into (possibly overlapping) triangles.
00466  * The algorithm has been extended to handle holes and multi-polygons.
00467  * See <code>http://www.faqs.org/faqs/graphics/algorithms-faq/</code>
00468  * for further details of the basic approach.
00469  */
00470 class CentroidArea {
00471 public:
00472         CentroidArea();
00473         virtual ~CentroidArea();
00474         void add(const Geometry *geom);
00475         void add(const CoordinateSequence *ring);
00476         Coordinate* getCentroid() const;
00477 private:
00478         CGAlgorithms *cga;
00479         Coordinate* basePt;// the point all triangles are based at
00480         Coordinate* triangleCent3;// temporary variable to hold centroid of triangle
00481         double areasum2;        /* Partial area sum */
00482         Coordinate* cg3; // partial centroid sum
00483         void setBasePoint(const Coordinate *newbasePt);
00484         void add(const Polygon *poly);
00485         void addShell(const CoordinateSequence *pts);
00486         void addHole(const CoordinateSequence *pts);
00487         inline void addTriangle(const Coordinate &p0, const Coordinate &p1, const Coordinate &p2,bool isPositiveArea);
00488         static inline  void centroid3(const Coordinate &p1,const Coordinate &p2,const Coordinate &p3,Coordinate *c);
00489         static inline double area2(const Coordinate &p1,const Coordinate &p2,const Coordinate &p3);
00490 };
00491 
00492 /*
00493  * \class InteriorPointPoint geosAlgorithm.h geos/geosAlgorithm.h
00494  * \brief
00495  * Computes a point in the interior of an point geometry.
00496  *
00497  * Algorithm:
00498  *
00499  * Find a point which is closest to the centroid of the geometry.
00500  */
00501 class InteriorPointPoint {
00502 private:
00503         const Coordinate* centroid;
00504         double minDistance;
00505         Coordinate *interiorPoint;
00506         void add(const Geometry *geom);
00507         void add(const Coordinate *point);
00508 public:
00509         InteriorPointPoint(const Geometry *g);
00510         virtual ~InteriorPointPoint();
00511         Coordinate* getInteriorPoint() const;
00512 };
00513 
00514 /*
00515  * Computes a point in the interior of an linear geometry.
00516  * <h2>Algorithm</h2>
00517  * <ul>
00518  * <li>Find an interior vertex which is closest to
00519  * the centroid of the linestring.
00520  * <li>If there is no interior vertex, find the endpoint which is
00521  * closest to the centroid.
00522  * </ul>
00523  */
00524 class InteriorPointLine {
00525 public:
00526         InteriorPointLine(Geometry *g);
00527         virtual ~InteriorPointLine();
00528         Coordinate* getInteriorPoint() const;
00529 private:
00530         const Coordinate *centroid;
00531         double minDistance;
00532         Coordinate *interiorPoint;
00533         void addInterior(const Geometry *geom);
00534         void addInterior(const CoordinateSequence *pts);
00535         void addEndpoints(const Geometry *geom);
00536         void addEndpoints(const CoordinateSequence *pts);
00537         void add(const Coordinate *point);
00538 };
00539 
00540 /*
00541  * Computes a point in the interior of an area geometry.
00542  *
00543  * <h2>Algorithm</h2>
00544  * <ul>
00545  *   <li>Find the intersections between the geometry
00546  *       and the horizontal bisector of the area's envelope
00547  *   <li>Pick the midpoint of the largest intersection (the intersections
00548  *       will be lines and points)
00549  * </ul>
00550  *
00551  * <b>
00552  * Note: If a fixed precision model is used,
00553  * in some cases this method may return a point
00554  * which does not lie in the interior.
00555  * </b>
00556  */
00557 class InteriorPointArea {
00558 private:
00559         static double avg(double a, double b);
00560         const GeometryFactory *factory;
00561         Coordinate *interiorPoint;
00562         double maxWidth;
00563         void add(const Geometry *geom);
00564 public:
00565         InteriorPointArea(const Geometry *g);
00566         virtual ~InteriorPointArea();
00567         Coordinate* getInteriorPoint() const;
00568         void addPolygon(const Geometry *geometry);
00569         Coordinate* centre(const Envelope *envelope) const;
00570 protected:
00571         const Geometry *widestGeometry(const Geometry *geometry);
00572         const Geometry *widestGeometry(const GeometryCollection *gc);
00573         LineString *horizontalBisector(const Geometry *geometry);
00574 
00575 };
00576 
00577 class BigQuad {
00578 public:
00579         Coordinate northmost;
00580         Coordinate southmost;
00581         Coordinate westmost;
00582         Coordinate eastmost;
00583 };
00584 
00585 class ConvexHull {
00586 private:
00587         PointLocator *pointLocator;
00588         //CGAlgorithms *cgAlgorithms;
00589         const Geometry *geometry;
00590         const GeometryFactory *factory;
00591         CoordinateSequence* reduce(const CoordinateSequence *pts);
00592         CoordinateSequence* preSort(CoordinateSequence *pts);
00593         CoordinateSequence* grahamScan(const CoordinateSequence *c);
00594         void radialSort(CoordinateSequence *p);
00595         int polarCompare(Coordinate o, Coordinate p, Coordinate q);
00596         bool isBetween(Coordinate c1, Coordinate c2, Coordinate c3);
00597     BigQuad* makeBigQuad(const CoordinateSequence *pts);
00598         Geometry* lineOrPolygon(CoordinateSequence *newCoordinates);
00599         CoordinateSequence* cleanRing(CoordinateSequence *original);
00600 public:
00601         ConvexHull(const Geometry *newGeometry);
00602         ~ConvexHull();
00603         Geometry* getConvexHull();
00604 };
00605 
00606 
00607 /*
00608  * Computes the minimum diameter of a {@link Geometry}.
00609  * The minimum diameter is defined to be the
00610  * width of the smallest band that
00611  * contains the geometry,
00612  * where a band is a strip of the plane defined
00613  * by two parallel lines.
00614  * This can be thought of as the smallest hole that the geometry can be
00615  * moved through, with a single rotation.
00616  * <p>
00617  * The first step in the algorithm is computing the convex hull of the Geometry.
00618  * If the input Geometry is known to be convex, a hint can be supplied to
00619  * avoid this computation.
00620  *
00621  * @see ConvexHull
00622  *
00623  */
00624 class MinimumDiameter {
00625 private:
00626         const Geometry* inputGeom;
00627         bool isConvex;
00628         LineSegment* minBaseSeg;
00629         Coordinate* minWidthPt;
00630         int minPtIndex;
00631         double minWidth;
00632         void computeMinimumDiameter();
00633         void computeWidthConvex(const Geometry* geom);
00641         void computeConvexRingMinDiameter(const CoordinateSequence *pts);
00642         int findMaxPerpDistance(const CoordinateSequence* pts, LineSegment* seg, int startIndex);
00643         static int getNextIndex(const CoordinateSequence* pts, int index);
00644 public:
00645         ~MinimumDiameter();
00646 
00652         MinimumDiameter(const Geometry* newInputGeom);
00653 
00664         MinimumDiameter(const Geometry* newInputGeom,const bool newIsConvex);
00665 
00671         double getLength();
00672 
00678         Coordinate* getWidthCoordinate();
00679 
00685         LineString* getSupportingSegment();
00686 
00692         LineString* getDiameter();
00693 };
00694 
00695 }
00696 #endif

Generated on Fri Nov 26 21:30:45 2004 for GEOS by  doxygen 1.3.9.1