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
00062
00063
00064
00065
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
00089
00090
00091
00092
00093
00094
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
00148
00149
00150
00151
00152
00153
00154
00155
00156
00157
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
00234
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
00243
00244
00245
00246
00247
00248 virtual bool isInteriorIntersection();
00249
00250
00251
00252
00253
00254
00255
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
00265
00266
00267
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
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
00360
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
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
00404
00405
00406
00407
00408
00409
00410
00411
00412
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;
00425 int numBoundaries;
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;
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;
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
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
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;
00515 Coordinate* triangleCent3;
00516 double areasum2;
00517 Coordinate* cg3;
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
00529
00530
00531
00532
00533
00534
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
00551
00552
00553
00554
00555
00556
00557
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
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
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
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
00644
00645
00646
00647
00648
00649
00650
00651
00652
00653
00654
00655
00656
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