00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
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
00079
00080
00081
00082
00083
00084
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
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
00325
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
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
00369
00370
00371
00372
00373
00374
00375
00376
00377
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;
00390 int numBoundaries;
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;
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;
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
00458
00459
00460
00461
00462
00463
00464
00465
00466
00467
00468
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;
00480 Coordinate* triangleCent3;
00481 double areasum2;
00482 Coordinate* cg3;
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
00494
00495
00496
00497
00498
00499
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
00516
00517
00518
00519
00520
00521
00522
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
00542
00543
00544
00545
00546
00547
00548
00549
00550
00551
00552
00553
00554
00555
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
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
00609
00610
00611
00612
00613
00614
00615
00616
00617
00618
00619
00620
00621
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