geom.h

/**********************************************************************
 * $Id: geom.h,v 1.34.2.2.2.5 2006/04/28 18:39:57 sgillies Exp $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 * Copyright (C) 2005 Refractions Research Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************/

#ifndef GEOS_GEOM_H
#define GEOS_GEOM_H

#include <memory>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <geos/platform.h>

using namespace std;

namespace geos {

string geosversion();

string jtsport();

enum GeometryTypeId {
        GEOS_POINT,
        GEOS_LINESTRING,
        GEOS_LINEARRING,
        GEOS_POLYGON,
        GEOS_MULTIPOINT,
        GEOS_MULTILINESTRING,
        GEOS_MULTIPOLYGON,
        GEOS_GEOMETRYCOLLECTION
};

class Coordinate;

class PrecisionModel {
friend class Unload;
public:
        /*
        * This class is only for use to support the "enums"
        * for the types of precision model.
        */
        typedef enum {

                FIXED,

                FLOATING,

                FLOATING_SINGLE

        } Type;
        
        PrecisionModel(void);


        PrecisionModel(Type nModelType);

        /*
         * Creates a <code>PrecisionModel</code> with Fixed precision.
         *
         * Fixed-precision coordinates are represented as precise internal
         * coordinates, which are rounded to the grid defined by the
         * scale factor.
         *
         * @param  scale
         *      amount by which to multiply a coordinate after subtracting
         *      the offset, to obtain a precise coordinate
         * @param  offsetX  not used.
         * @param  offsetY  not used.
         *
         * @deprecated offsets are no longer supported, since internal
         * representation is rounded floating point
         */
        PrecisionModel(double newScale, double newOffsetX, double newOffsetY);

        PrecisionModel(double newScale);

        // copy constructor
        PrecisionModel(const PrecisionModel &pm);

        virtual ~PrecisionModel(void);



        static const double maximumPreciseValue;

        double makePrecise(double val) const;

        void makePrecise(Coordinate *coord) const;


        bool isFloating() const;


        int getMaximumSignificantDigits() const;


        Type getType() const;

        double getScale() const;

        /*
        * Returns the x-offset used to obtain a precise coordinate.
        *
        * @return the amount by which to subtract the x-coordinate before
        *         multiplying by the scale
        * @deprecated Offsets are no longer used
        */
        double getOffsetX() const;

        /*
        * Returns the y-offset used to obtain a precise coordinate.
        *
        * @return the amount by which to subtract the y-coordinate before
        *         multiplying by the scale
        * @deprecated Offsets are no longer used
        */
        double getOffsetY() const;

        /*
         *  Sets <code>internal</code> to the precise representation of <code>external</code>.
         *
         * @param external the original coordinate
         * @param internal the coordinate whose values will be changed to the
         *                 precise representation of <code>external</code>
         * @deprecated use makePrecise instead
         */
        void toInternal(const Coordinate& external, Coordinate* internal) const;

        /*
        *  Returns the precise representation of <code>external</code>.
        *
        *@param  external  the original coordinate
        *@return
        *       the coordinate whose values will be changed to the precise
        *       representation of <code>external</code>
        * @deprecated use makePrecise instead
        */
        Coordinate* toInternal(const Coordinate& external) const;

        /*
        *  Returns the external representation of <code>internal</code>.
        *
        *@param  internal  the original coordinate
        *@return           the coordinate whose values will be changed to the
        *      external representation of <code>internal</code>
        * @deprecated no longer needed, since internal representation is same as external representation
        */
        Coordinate* toExternal(const Coordinate& internal) const;

        /*
        *  Sets <code>external</code> to the external representation of
        *  <code>internal</code>.
        *
        * @param  internal  the original coordinate
        * @param  external
        *       the coordinate whose values will be changed to the
        *       external representation of <code>internal</code>
        * @deprecated no longer needed, since internal representation is same as external representation
        */
        void toExternal(const Coordinate& internal, Coordinate* external) const;

        string toString() const;


        int compareTo(const PrecisionModel* other) const;

private:
        void setScale(double newScale);
        Type modelType;
        double scale;
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = 7777263578777803835I64;
#else        
        static const int64 serialVersionUID = 7777263578777803835LL;
#endif        
};

// Define the following to make assignments and copy constructions
// NON-inline (will let profilers report usages)
//#define PROFILE_COORDINATE_COPIES 1
class Coordinate {
public:
        //void setNull(void);
        //static Coordinate& getNull(void);
        virtual ~Coordinate(){};
        //Coordinate(double xNew, double yNew, double zNew);
        //Coordinate(const Coordinate& c);
        //Coordinate(double xNew, double yNew);
        //void setCoordinate(Coordinate& other);
        //bool equals2D(Coordinate& other);
        //int compareTo(Coordinate& other);
        //bool equals3D(Coordinate& other);
        string toString() const;
        //void makePrecise();
        //double distance(Coordinate& p);
        static Coordinate nullCoord;

        void setNull() {
                x=DoubleNotANumber;
                y=DoubleNotANumber;
                z=DoubleNotANumber;
        }

        static Coordinate& getNull() {
                return nullCoord;
        }

        Coordinate() {
                x=0.0;
                y=0.0;
                z=DoubleNotANumber;
        }

        Coordinate(double xNew, double yNew, double zNew) {
                x=xNew;
                y=yNew;
                z=zNew;
        }

#ifndef PROFILE_COORDINATE_COPIES
        Coordinate(const Coordinate& c){
                x=c.x;
                y=c.y;
                z=c.z;
        }
#else
        Coordinate(const Coordinate& c);
        Coordinate &operator=(const Coordinate &c);
#endif

        Coordinate(double xNew, double yNew){
                x=xNew;
                y=yNew;
                z=DoubleNotANumber;
        }

        void setCoordinate(const Coordinate& other) {
                x = other.x;
                y = other.y;
                z = other.z;
        }

        bool equals2D(const Coordinate& other) const {
                if (x != other.x) {
                return false;
                }
                if (y != other.y) {
                return false;
                }
                return true;
        }

        int compareTo(const Coordinate& other) const {
                if (x < other.x) {
                return -1;
                }
                if (x > other.x) {
                return 1;
                }
                if (y < other.y) {
                return -1;
                }
                if (y > other.y) {
                return 1;
                }
                return 0;
        }

        bool equals3D(const Coordinate& other) const {
                return (x == other.x) && ( y == other.y) && ((z == other.z)||(ISNAN(z) && ISNAN(other.z)));
        }

        void makePrecise(const PrecisionModel *precisionModel) {
                x = precisionModel->makePrecise(x);
                y = precisionModel->makePrecise(y);
        }

        double distance(const Coordinate& p) const {
                double dx = x - p.x;
                double dy = y - p.y;
                return sqrt(dx * dx + dy * dy);
        }

        int hashCode() {
                //Algorithm from Effective Java by Joshua Bloch [Jon Aquino]
                int result = 17;
                result = 37 * result + hashCode(x);
                result = 37 * result + hashCode(y);
                return result;
        }

        static int hashCode(double x) {
                int64 f = (int64)(x);
                return (int)(f^(f>>32));
        }


        double x;
        double y;
        double z;

private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID=6683108902428366910I64;
#else
        static const int64 serialVersionUID=6683108902428366910LL;
#endif

};


//* class CoordinateList geom.h geos.h
//*
//* brief A list of Coordinates, which may be set to prevent
//* repeated coordinates from occuring in the list.
//
//class CoordinateList {
//public:
//      ~CoordinateList(){};
//
//      // copy constructor
//      CoordinateList(const CoordinateList &cl);
//
//      // constructor an empty CoordinateList
//      CoordinateList();
//
//      /*
//       * Constructs a new list from a vector of Coordinates.
//       * Caller can specify if repeated points are to be removed.
//       * Default is allowing repeated points.
//       * Will take ownership of coords.
//       */
//      CoordinateList(vector<Coordinate> *coords, bool allowRepeted=false);
//
//      // Get a reference to the nth Coordinate 
//      const Coordinate& getCoordinate(int n) const;
//
//      /*
//       * \brief Add an array of coordinates 
//       * @param vc The coordinates
//       * @param allowRepeated if set to false, repeated coordinates
//       *      are collapsed
//       * @return true (as by general collection contract)
//       */
//      void add(vector<Coordinate>* vc, bool allowRepeated);
//
//      /*
//       * \brief Add an array of coordinates 
//       * @param cl The coordinates
//       * @param allowRepeated if set to false, repeated coordinates
//       * are collapsed
//       * @param direction if false, the array is added in reverse order
//       * @return true (as by general collection contract)
//       */
//      void add(CoordinateList *cl,bool allowRepeated,bool direction);
//
//      /*
//       * \brief Add a coordinate
//       * @param c The coordinate to add
//       * @param allowRepeated if set to false, repeated coordinates
//       * are collapsed
//       * @return true (as by general collection contract)
//       */
//      void add(const Coordinate& c,bool allowRepeated);
//
//      // Add a Coordinate to the list
//      void add(const Coordinate& c);
//
//      // Get vector
//      const vector<Coordinate>* toCoordinateArray() const;
//
//private:
//
//      vector<Coordinate> *vect;
//};

class CoordinateSequence {
public:
        virtual ~CoordinateSequence(){};

        virtual CoordinateSequence *clone() const=0;

        //virtual const Coordinate& getCoordinate(int i) const=0;
        virtual const Coordinate& getAt(int i) const=0;

        //virtual int size() const=0;
        virtual int getSize() const=0;

        virtual const vector<Coordinate>* toVector() const=0;

        void add(const vector<Coordinate>* vc, bool allowRepeated);

        /* This is here for backward compatibility.. */
        void add(CoordinateSequence *cl,bool allowRepeated,bool direction);

        void add(const CoordinateSequence *cl,bool allowRepeated,bool direction);

        void add(const Coordinate& c,bool allowRepeated);

        virtual bool isEmpty() const=0;

        virtual void add(const Coordinate& c)=0;

        // Get number of coordinates
        //virtual int getSize() const=0;

        //virtual       const Coordinate& getAt(int pos) const=0;

        virtual void setAt(const Coordinate& c, int pos)=0;

        virtual void deleteAt(int pos)=0;

        virtual string toString() const=0;

        virtual void setPoints(const vector<Coordinate> &v)=0;
        
        bool hasRepeatedPoints() const;

        const Coordinate* minCoordinate() const;


        static CoordinateSequence* removeRepeatedPoints(const CoordinateSequence *cl);

        static bool hasRepeatedPoints(const CoordinateSequence *cl);

        static CoordinateSequence* atLeastNCoordinatesOrNothing(int n, CoordinateSequence *c);

        static const Coordinate* minCoordinate(CoordinateSequence *cl);

        static int indexOf(const Coordinate *coordinate, const CoordinateSequence *cl);
        static bool equals(CoordinateSequence *cl1, CoordinateSequence *cl2);

        static void scroll(CoordinateSequence *cl, const Coordinate *firstCoordinate);

        static void reverse(CoordinateSequence *cl);

        virtual unsigned int getDimension() const=0;

        virtual double getOrdinate(unsigned int index, unsigned int ordinateIndex) const=0;

        virtual void setOrdinate(unsigned int index, unsigned int ordinateIndex, double value)=0;

        enum { X,Y,Z,M };

        double getX(unsigned int index) const { return getOrdinate(index, X); }
        double getY(unsigned int index) const { return getOrdinate(index, Y); }
        double getZ(unsigned int index) const { return getOrdinate(index, Z); }
};

class DefaultCoordinateSequence : public CoordinateSequence {
public:

        DefaultCoordinateSequence(const DefaultCoordinateSequence &cl);

        CoordinateSequence *clone() const;

        //const Coordinate& getCoordinate(int pos) const;
        const Coordinate& getAt(int pos) const;

        //int size() const;
        int getSize() const;
        const vector<Coordinate>* toVector() const;

        DefaultCoordinateSequence();

        DefaultCoordinateSequence(vector<Coordinate> *coords);

        DefaultCoordinateSequence(int n);

        virtual ~DefaultCoordinateSequence();

        bool isEmpty() const;
        void add(const Coordinate& c);
        void setAt(const Coordinate& c, int pos);
        void deleteAt(int pos);
        string toString() const;
        void setPoints(const vector<Coordinate> &v);
private:
        vector<Coordinate> *vect;

public:
        unsigned int getDimension() const { return 3; }
        void setOrdinate(unsigned int index, unsigned int ordinateIndex, double value);
        double getOrdinate(unsigned int index, unsigned int ordinateIndex) const;
};

struct point_3d {
        double x;
        double y;
        double z;
};

class PointCoordinateSequence : public CoordinateSequence {
public:
        PointCoordinateSequence();
        PointCoordinateSequence(int n);
        PointCoordinateSequence(const Coordinate& c);
        PointCoordinateSequence(const PointCoordinateSequence &cl);
        PointCoordinateSequence(const CoordinateSequence *c);
        virtual ~PointCoordinateSequence();
        CoordinateSequence *clone() const;
        bool isEmpty() const;
        void add(const Coordinate& c);
        void add(point_3d p);
        int getSize() const;
        const Coordinate& getAt(int pos) const;
        point_3d getPointAt(int pos);
        void setAt(const Coordinate& c, int pos);
        void setAt(point_3d p, int pos);
        void deleteAt(int pos);
        const vector<Coordinate>* toVector() const;
        vector<point_3d>* toPointVector();
        string toString() const;
        void setPoints(const vector<Coordinate> &v);
        void setPoints(vector<point_3d> &v);
private:
        vector<point_3d> *vect;
        mutable vector<Coordinate>*cached_vector;
public:
        unsigned int getDimension() const { return 3; }
        void setOrdinate(unsigned int index, unsigned int ordinateIndex, double value);
        double getOrdinate(unsigned int index, unsigned int ordinateIndex) const;
};

class CoordinateSequenceFactory {
public:
        // create an empty CoordinateSequence
        //virtual CoordinateSequence* createCoordinateSequence()=0;

        // create an empty CoordinateSequence with 'size' Coordinate slots
        //virtual CoordinateSequence* createCoordinateSequence(int size)=0;

        //virtual CoordinateSequence* createCoordinateSequence(const Coordinate& c)=0;
        // create an CoordinateSequence containing the given Coordinate 
        //virtual CoordinateSequence* createCoordinateSequence(const CoordinateSequence *c)=0;

        virtual CoordinateSequence *create(vector<Coordinate> *coordinates) const=0;

        virtual CoordinateSequence *create(unsigned int size, unsigned int dims) const=0;
};

class DefaultCoordinateSequenceFactory: public CoordinateSequenceFactory {

public:
        // create an empty DefaultCoordinateSequence
        //CoordinateSequence *createCoordinateSequence() {return new DefaultCoordinateSequence();};
        // create an empty DefaultCoordinateSequence with 'size' Coordinate slots
        //CoordinateSequence* createCoordinateSequence(int size) {return new DefaultCoordinateSequence(size);};
        //CoordinateSequence* createCoordinateSequence(const Coordinate& c) {return new DefaultCoordinateSequence(c);};

        // create an DefaultCoordinateSequence containing the given Coordinate 
        //CoordinateSequence* createCoordinateSequence(const CoordinateSequence *cl) {return new DefaultCoordinateSequence(cl);};


        CoordinateSequence *create(vector<Coordinate> *coords) const;

        static const CoordinateSequenceFactory *instance();

        CoordinateSequence *create(unsigned int size, unsigned int dims) const;
};

/*
 * \class PointCoordinateSequenceFactory geom.h geos.h
 *
 * \brief
 * Factory for PointCoordinateSequence objects.
 */
class PointCoordinateSequenceFactory: public CoordinateSequenceFactory {
public:

        CoordinateSequence *create(vector<Coordinate> *coords) const;
        CoordinateSequence *create(unsigned int size, unsigned int dims) const;
};

/*
 * <code>Geometry</code> classes support the concept of applying a
 * coordinate filter to every coordinate in the <code>Geometry</code>. A
 * coordinate filter can either record information about each coordinate or
 * change the coordinate in some way. Coordinate filters implement the
 * interface <code>CoordinateFilter</code>. (<code>CoordinateFilter</code> is
 * an example of the Gang-of-Four Visitor pattern). Coordinate filters can be
 * used to implement such things as coordinate transformations, centroid and
 * envelope computation, and many other functions.
 *
 */
class CoordinateFilter {
public:
   virtual ~CoordinateFilter() {}
   virtual void filter_rw(Coordinate* coord)=0;
   virtual void filter_ro(const Coordinate* coord)=0;
};

class Geometry;

/*
 *  <code>Geometry</code> classes support the concept of applying
 *  a <code>GeometryComponentFilter</code>
 *  filter to the <code>Geometry</code>.
 *  The filter is applied to every component of the <code>Geometry</code>
 *  which is itself a <code>Geometry</code>.
 *  A <code>GeometryComponentFilter</code> filter can either
 *  record information about the <code>Geometry</code>
 *  or change the <code>Geometry</code> in some way.
 *  <code>GeometryComponentFilter</code>
 *  is an example of the Gang-of-Four Visitor pattern.
 *
 */
class GeometryComponentFilter {
public:
//      virtual void filter(Geometry *geom)=0;
        virtual void filter_rw(Geometry *geom);
        virtual void filter_ro(const Geometry *geom); // Unsupported
};


/*
 * Constants representing the dimensions of a point, a curve and a surface.
 * Also, constants representing the dimensions of the empty geometry and
 * non-empty geometries, and a wildcard dimension meaning "any dimension".
 * 
 */
class Dimension {
public:
        enum {
                DONTCARE=-3,    
                True,                   
                False,                  
                P,                              
                L,                              
                A                               
        };
        //static const int P = 0;                       /// Dimension value of a point (0).
        //static const int L = 1;                       /// Dimension value of a curve (1).
        //static const int A = 2;                       /// Dimension value of a surface (2).
        //static const int False = -1;  /// Dimension value of the empty geometry (-1).
        //static const int True = -2;           /// Dimension value of non-empty geometries (= {P, L, A}).
        //static const int DONTCARE = -3;       /// Dimension value for any dimension (= {FALSE, TRUE}).
        static char toDimensionSymbol(int dimensionValue);
        static int toDimensionValue(char dimensionSymbol);
};

class Envelope {
public:
        Envelope(void);
        Envelope(double x1, double x2, double y1, double y2);
        Envelope(const Coordinate& p1, const Coordinate& p2);
        Envelope(const Coordinate& p);
        Envelope(const Envelope &env);
        virtual ~Envelope(void);
        static bool intersects(const Coordinate& p1,const Coordinate& p2,const Coordinate& q);
        static bool intersects(const Coordinate& p1,const Coordinate& p2,const Coordinate& q1,const Coordinate& q2);
        void init(void);
        void init(double x1, double x2, double y1, double y2);
        void init(const Coordinate& p1, const Coordinate& p2);
        void init(const Coordinate& p);
        void init(Envelope env);
        void setToNull(void);
        bool isNull(void) const;
        double getWidth(void) const;
        double getHeight(void) const;
        double getMaxY() const;
        double getMaxX() const;
        double getMinY() const;
        double getMinX() const;
        void expandToInclude(const Coordinate& p);
        void expandToInclude(double x, double y);
        void expandToInclude(const Envelope* other);
        bool contains(const Coordinate& p) const;
        bool contains(double x, double y) const;
        bool contains(const Envelope* other) const;
        bool overlaps(const Coordinate& p) const;
        bool overlaps(double x, double y) const;
        bool overlaps(const Envelope* other) const;
        bool intersects(const Coordinate& p) const;
        bool intersects(double x, double y) const;
        bool intersects(const Envelope* other) const;
        bool equals(const Envelope* other) const;
        string toString(void) const;
        double distance(const Envelope* env) const;
        int hashCode() const;

private:
        static double distance(double x0,double y0,double x1,double y1);
        double minx;    
        double maxx;    
        double miny;    
        double maxy;    
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID=5873921885273102420I64;
#else        
        static const int64 serialVersionUID=5873921885273102420LL;
#endif        
};

class Geometry;
class GeometryFilter;
class IntersectionMatrix;


class CGAlgorithms;
class Point;
class GeometryFactory;

class Geometry{
friend class Unload;
public:

        Geometry(const Geometry &geom);

        Geometry(const GeometryFactory *factory);

        virtual ~Geometry();

        virtual Geometry* clone() const=0;

        const GeometryFactory* getFactory() const;

        void setUserData(void* newUserData);

        void* getUserData();

        /*
         * \brief
         * Returns the ID of the Spatial Reference System used by the
         * <code>Geometry</code>.
         *
         * GEOS supports Spatial Reference System information in the simple way
         * defined in the SFS. A Spatial Reference System ID (SRID) is present
         * in each <code>Geometry</code> object. <code>Geometry</code>
         * provides basic accessor operations for this field, but no others.
         * The SRID is represented as an integer.
         *
         * @return the ID of the coordinate space in which the
         * <code>Geometry</code> is defined.
         *
         * @deprecated use getUserData instead
         */
        virtual int getSRID() const;

        /*
         * Sets the ID of the Spatial Reference System used by the
         * <code>Geometry</code>.
         * @deprecated use setUserData instead
         */
        virtual void setSRID(int newSRID);

        virtual const PrecisionModel* getPrecisionModel() const;

        virtual const Coordinate* getCoordinate() const=0; //Abstract

        virtual CoordinateSequence* getCoordinates() const=0; //Abstract

        virtual int getNumPoints() const=0; //Abstract

        virtual bool isSimple() const=0; //Abstract

        virtual string getGeometryType() const=0; //Abstract

        virtual GeometryTypeId getGeometryTypeId() const=0; //Abstract

        virtual bool isValid() const;

        virtual bool isEmpty() const=0; //Abstract

        virtual int getDimension() const=0; //Abstract

        virtual Geometry* getBoundary() const=0; //Abstract

        virtual int getBoundaryDimension() const=0; //Abstract

        virtual Geometry* getEnvelope() const;

        virtual const Envelope* getEnvelopeInternal() const;

        virtual bool disjoint(const Geometry *other) const;

        virtual bool touches(const Geometry *other) const;

        virtual bool intersects(const Geometry *g) const;

        virtual bool crosses(const Geometry *g) const;

        virtual bool within(const Geometry *g) const;

        virtual bool contains(const Geometry *g) const;

        virtual bool overlaps(const Geometry *g) const;

        virtual bool relate(const Geometry *g, string intersectionPattern) const;
        virtual IntersectionMatrix* relate(const Geometry *g) const;

        virtual bool equals(const Geometry *g) const;

        virtual string toString() const;

        virtual string toText() const;
        
        virtual Geometry* buffer(double distance) const;

        virtual Geometry* buffer(double distance,int quadrantSegments) const;

        virtual Geometry* convexHull() const;

        virtual Geometry* intersection(const Geometry *other) const;

        virtual Geometry* Union(const Geometry *other) const;
                // throw(IllegalArgumentException *, TopologyException *);

        virtual Geometry* difference(const Geometry *other) const;

        virtual Geometry* symDifference(const Geometry *other) const;

        virtual bool equalsExact(const Geometry *other, double tolerance)
                const=0; //Abstract

        virtual void apply_rw(CoordinateFilter *filter)=0; //Abstract
        virtual void apply_ro(CoordinateFilter *filter) const=0; //Abstract
        virtual void apply_rw(GeometryFilter *filter);
        virtual void apply_ro(GeometryFilter *filter) const;
        virtual void apply_rw(GeometryComponentFilter *filter);
        virtual void apply_ro(GeometryComponentFilter *filter) const;

        virtual void normalize()=0; //Abstract

        virtual int compareTo(const Geometry *geom) const;

        virtual double distance(const Geometry *g) const;

        virtual double getArea() const;

        virtual double getLength() const;

        virtual bool isWithinDistance(const Geometry *geom,double cDistance);

        virtual Point* getCentroid() const;

        virtual Point* getInteriorPoint();

        /*
         * \brief
         * Notifies this Geometry that its Coordinates have been changed
         * by an external party (using a CoordinateFilter, for example).
         */
        virtual void geometryChanged();

        /*
         * \brief
         * Notifies this Geometry that its Coordinates have been changed
         * by an external party.
         */
        void geometryChangedAction();

protected:
        mutable Envelope* envelope;
        
        static bool hasNonEmptyElements(const vector<Geometry *>* geometries);

        static bool hasNullElements(const CoordinateSequence* list);

        static bool hasNullElements(const vector<Geometry *>* lrs);

//      static void reversePointOrder(CoordinateSequence* coordinates);
//      static Coordinate& minCoordinate(CoordinateSequence* coordinates);
//      static void scroll(CoordinateSequence* coordinates,Coordinate* firstCoordinate);
//      static int indexOf(Coordinate* coordinate,CoordinateSequence* coordinates);
//
        virtual bool isEquivalentClass(const Geometry *other) const;

        static void checkNotGeometryCollection(const Geometry *g); // throw(IllegalArgumentException *);
        //virtual void checkEqualSRID(Geometry *other);
        //virtual void checkEqualPrecisionModel(Geometry *other);
        virtual Envelope* computeEnvelopeInternal() const=0; //Abstract
        virtual int compareToSameClass(const Geometry *geom) const=0; //Abstract
        int compare(vector<Coordinate> a, vector<Coordinate> b) const;
        int compare(vector<Geometry *> a, vector<Geometry *> b) const;
        bool equal(const Coordinate& a, const Coordinate& b,double tolerance) const;
        int SRID;

        Geometry* toInternalGeometry(const Geometry *g) const;
        Geometry* fromInternalGeometry(const Geometry *g) const;
private:
        virtual int getClassSortIndex() const;
        static GeometryComponentFilter geometryChangedFilter;
#ifdef INT64_CONST_IS_I64
    static const int64 serialVersionUID = 8763622679187376702I64;
#else
    static const int64 serialVersionUID = 8763622679187376702LL;
#endif
        const GeometryFactory *factory;
        static const GeometryFactory* INTERNAL_GEOMETRY_FACTORY;
        void* userData;
        Point* createPointFromInternalCoord(const Coordinate* coord,const Geometry *exemplar) const;
};

/*
 * Geometry classes support the concept of applying a Geometry
 * filter to the Geometry. In the case of GeometryCollection
 * subclasses, the filter is applied to every element Geometry.
 * A Geometry filter can either record information about the Geometry
 * or change the Geometry in some way.
 * Geometry filters implement the interface GeometryFilter.
 * (GeometryFilter is an example of the Gang-of-Four Visitor pattern).
 */
class GeometryFilter {
public:
        /*
         * Performs an operation with or on <code>geom</code>.
         *
         * @param  geom  a <code>Geometry</code> to which the filter
         *         is applied.
         */
        virtual void filter_ro(const Geometry *geom)=0;
        virtual void filter_rw(Geometry *geom)=0;
};

/*
 * Represents a line segment defined by two {@link Coordinate}s.
 * Provides methods to compute various geometric properties
 * and relationships of line segments.
 * 
 * This class is designed to be easily mutable (to the extent of
 * having its contained points public).
 * This supports a common pattern of reusing a single LineSegment
 * object as a way of computing segment properties on the
 * segments defined by arrays or lists of {@link Coordinate}s.
 *
 */
class LineSegment {
public:
        Coordinate p0; 
        Coordinate p1; 
        LineSegment(void);
        LineSegment(const LineSegment &ls);
        LineSegment(const Coordinate& c0, const Coordinate& c1);
        virtual ~LineSegment(void);
        virtual void setCoordinates(const Coordinate& c0, const Coordinate& c1);
        virtual const Coordinate& getCoordinate(int i) const;
        virtual void setCoordinates(const LineSegment ls);
        virtual double getLength() const;
        virtual bool isHorizontal() const;
        virtual bool isVertical() const;
        virtual int orientationIndex(LineSegment *seg) const;
        virtual void reverse();
        virtual void normalize();
        virtual double angle() const;
        virtual double distance(const LineSegment ls) const;
        virtual double distance(const Coordinate& p) const;
        virtual double distancePerpendicular(const Coordinate& p) const;
        virtual double projectionFactor(const Coordinate& p) const;
        virtual Coordinate* project(const Coordinate& p) const;
        virtual LineSegment* project(const LineSegment *seg) const;
        virtual Coordinate* closestPoint(const Coordinate& p) const;
        virtual int compareTo(const LineSegment other) const;
        virtual bool equalsTopo(const LineSegment other) const;

        virtual CoordinateSequence* closestPoints(const LineSegment *line);

        Coordinate* intersection(const LineSegment *line) const;
        virtual string toString() const;
private:
#ifdef INT64_CONST_IS_I64
  static const int64 serialVersionUID=3252005833466256227I64;
#else
  static const int64 serialVersionUID=3252005833466256227LL;
#endif

};

class IntersectionMatrix {
public:
        IntersectionMatrix();
        IntersectionMatrix(string elements);
        IntersectionMatrix(const IntersectionMatrix &im);
        virtual ~IntersectionMatrix();
        static bool matches(int actualDimensionValue, char requiredDimensionSymbol);
        static bool matches(string actualDimensionSymbols, string requiredDimensionSymbols);
        void add(IntersectionMatrix *im);
        void set(int row, int column, int dimensionValue);
        void set(string dimensionSymbols);
        void setAtLeast(int row, int column, int minimumDimensionValue);
        void setAtLeastIfValid(int row, int column, int minimumDimensionValue);
        void setAtLeast(string minimumDimensionSymbols);
        void setAll(int dimensionValue);
        int get(int row, int column);
        bool isDisjoint();
        bool isIntersects();
        bool isTouches(int dimensionOfGeometryA, int dimensionOfGeometryB);
        bool isCrosses(int dimensionOfGeometryA, int dimensionOfGeometryB);
        bool isWithin();
        bool isContains();
        bool isEquals(int dimensionOfGeometryA, int dimensionOfGeometryB);
        bool isOverlaps(int dimensionOfGeometryA, int dimensionOfGeometryB);
        bool matches(string requiredDimensionSymbols);
        IntersectionMatrix* transpose();
        string toString();
private:
        int matrix[3][3];
};

/*
 *  Constants representing the location of a point relative to a geometry. They
 *  can also be thought of as the row or column index of a DE-9IM matrix. For a
 *  description of the DE-9IM, see the <A
 *  HREF="http://www.opengis.org/techno/specs.htm">OpenGIS Simple Features
 *  Specification for SQL</A> .
 */
class Location {
public:
        enum {
                UNDEF=-1,   

                INTERIOR,
                BOUNDARY,
                EXTERIOR = 2
        };
        //static const int INTERIOR = 0;
        //static const int BOUNDARY = 1;
        //static const int EXTERIOR = 2;
        //static const int UNDEF = -1;   ///Instead of NULL
        static char toLocationSymbol(int locationValue);
};


//Operators
bool operator==(const Coordinate& a, const Coordinate& b);
bool operator!=(const Coordinate& a, const Coordinate& b);
bool operator==(const Envelope a, const Envelope b);
bool operator==(const PrecisionModel a, const PrecisionModel b);
bool operator==(const LineSegment a, const LineSegment b);

bool lessThen(Coordinate& a,Coordinate& b);
bool greaterThen(Geometry *first, Geometry *second);

class GeometryCollection : public Geometry{
public:
        GeometryCollection(const GeometryCollection &gc);

        GeometryCollection(vector<Geometry *> *newGeoms, const GeometryFactory *newFactory);

        virtual Geometry *clone() const;

        virtual ~GeometryCollection();

        virtual CoordinateSequence* getCoordinates() const;

        virtual bool isEmpty() const;

        virtual int getDimension() const;

        virtual Geometry* getBoundary() const;

        virtual int getBoundaryDimension() const;

        virtual int getNumPoints() const;
        virtual string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        virtual bool isSimple() const;
        virtual bool equalsExact(const Geometry *other, double tolerance) const;

        virtual void apply_ro(CoordinateFilter *filter) const;
        virtual void apply_rw(CoordinateFilter *filter);
        virtual void apply_ro(GeometryFilter *filter) const;
        virtual void apply_rw(GeometryFilter *filter);
        virtual void apply_ro(GeometryComponentFilter *filter) const;
        virtual void apply_rw(GeometryComponentFilter *filter);
        virtual void normalize();
        virtual const Coordinate* getCoordinate() const;
        virtual double getArea() const;
        virtual double getLength() const;
        virtual int getNumGeometries() const;
        virtual const Geometry* getGeometryN(int n) const;
protected:
        vector<Geometry *>* geometries;
        virtual Envelope* computeEnvelopeInternal() const;
        virtual int compareToSameClass(const Geometry *gc) const;
private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = -5694727726395021467I64;
#else
        static const int64 serialVersionUID = -5694727726395021467LL;
#endif        
};

class GeometryCollectionIterator {
public:
        GeometryCollectionIterator();
        GeometryCollectionIterator(const GeometryCollectionIterator &gci);
        GeometryCollectionIterator(const GeometryCollection *newParent);
        virtual ~GeometryCollectionIterator();
        bool hasNext() const;
        const Geometry *next();
        void remove(); //Not implemented
private:
        const GeometryCollection* parent;
        bool atStart;
        int max;
        int index;
        GeometryCollectionIterator* subcollectionIterator;
};

class Point : public Geometry{
public:

        Point(CoordinateSequence *newCoords, const GeometryFactory *newFactory);

        Point(const Point &p); 
        virtual ~Point();
        Geometry *clone() const;
        CoordinateSequence* getCoordinates(void) const;
        int getNumPoints() const;
        bool isEmpty() const;
        bool isSimple() const;
        //bool isValid() const;

        int getDimension() const;

        int getBoundaryDimension() const;

        Geometry* getBoundary() const;

        double getX() const;
        double getY() const;
        const Coordinate* getCoordinate() const;
        string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        void apply_ro(CoordinateFilter *filter) const;
        void apply_rw(CoordinateFilter *filter);
        void apply_ro(GeometryFilter *filter) const;
        void apply_rw(GeometryFilter *filter);
        void apply_rw(GeometryComponentFilter *filter);
        void apply_ro(GeometryComponentFilter *filter) const;
        bool equalsExact(const Geometry *other, double tolerance) const;
        void normalize(void) { };
protected:
        Envelope* computeEnvelopeInternal() const;
        int compareToSameClass(const Geometry *p) const;
private:
        CoordinateSequence *coordinates;
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = 4902022702746614570I64;
#else        
        static const int64 serialVersionUID = 4902022702746614570LL;
#endif        
public:
        const CoordinateSequence *getCoordinatesRO() const;
};

class LineString: public Geometry {
public:
        LineString(const LineString &ls);

        LineString(CoordinateSequence *pts, const GeometryFactory *newFactory);

        virtual ~LineString();
        virtual Geometry *clone() const;
        virtual CoordinateSequence* getCoordinates() const;

        const CoordinateSequence* getCoordinatesRO() const;

        virtual const Coordinate& getCoordinateN(int n) const;

        virtual int getDimension() const;

        virtual int getBoundaryDimension() const;

        virtual Geometry* getBoundary() const;

        virtual bool isEmpty() const;
        virtual int getNumPoints() const;
        virtual Point* getPointN(int n) const;
        virtual Point* getStartPoint() const;
        virtual Point* getEndPoint() const;
        virtual bool isClosed() const;
        virtual bool isRing() const;
        virtual string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        virtual bool isSimple() const;
        virtual bool isCoordinate(Coordinate& pt) const;
        virtual bool equalsExact(const Geometry *other, double tolerance) const;
        virtual void apply_rw(CoordinateFilter *filter);
        virtual void apply_ro(CoordinateFilter *filter) const;
        virtual void apply_rw(GeometryFilter *filter);
        virtual void apply_ro(GeometryFilter *filter) const;
        virtual void apply_rw(GeometryComponentFilter *filter);
        virtual void apply_ro(GeometryComponentFilter *filter) const;

        virtual void normalize();

        //was protected
        virtual int compareToSameClass(const Geometry *ls) const;
        virtual int compareTo(const LineString *ls) const;
        virtual const Coordinate* getCoordinate() const;
        virtual double getLength() const;
protected:
        virtual Envelope* computeEnvelopeInternal() const;
        CoordinateSequence* points;
private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = 3110669828065365560I64;
#else
        static const int64 serialVersionUID = 3110669828065365560LL;
#endif        
};

class LinearRing : public LineString{

public:

        LinearRing(const LinearRing &lr);

        LinearRing(CoordinateSequence* points, const GeometryFactory *newFactory);

        virtual ~LinearRing();
        bool isSimple() const;
        string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        bool isClosed() const;
        void setPoints(CoordinateSequence* cl);
    Geometry* clone() const;
private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = -4261142084085851829I64;
#else
        static const int64 serialVersionUID = -4261142084085851829LL;
#endif        
        void validateConstruction();
};

class Polygon: public Geometry{
public:
        Polygon(const Polygon &p);
        virtual ~Polygon();

        Polygon(LinearRing *newShell, vector<Geometry *> *newHoles,
                const GeometryFactory *newFactory);

        virtual Geometry *clone() const;
        CoordinateSequence* getCoordinates() const;
        int getNumPoints() const;

        int getDimension() const;

        int getBoundaryDimension() const;

        Geometry* getBoundary() const;

        bool isEmpty() const;
        bool isSimple() const;
        
        const LineString* getExteriorRing() const;

        int getNumInteriorRing() const;

        const LineString* getInteriorRingN(int n) const;

        string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        bool equalsExact(const Geometry *other, double tolerance) const;
        void apply_rw(CoordinateFilter *filter);
        void apply_ro(CoordinateFilter *filter) const;
        void apply_rw(GeometryFilter *filter);
        void apply_ro(GeometryFilter *filter) const;
        Geometry* convexHull() const;
        void normalize();
        int compareToSameClass(const Geometry *p) const; //was protected
        const Coordinate* getCoordinate() const;

        double getArea() const;

        double getLength() const;

        void apply_rw(GeometryComponentFilter *filter);
        void apply_ro(GeometryComponentFilter *filter) const;
protected:
        LinearRing *shell;
        vector<Geometry *> *holes; //Actually vector<LinearRing *>
        Envelope* computeEnvelopeInternal() const;
private:
        void normalize(LinearRing *ring, bool clockwise);
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = -3494792200821764533I64;
#else
        static const int64 serialVersionUID = -3494792200821764533LL;
#endif        
};

class MultiPoint: public GeometryCollection{
public:

        MultiPoint(vector<Geometry *> *newPoints, const GeometryFactory *newFactory);

        virtual ~MultiPoint();

        int getDimension() const;

        int getBoundaryDimension() const;

        Geometry* getBoundary() const;

        string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        //bool isValid() const;
        bool isSimple() const;
        bool equalsExact(const Geometry *other, double tolerance) const;
protected:
        const Coordinate* getCoordinate(int n) const;
private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = -8048474874175355449I64;
#else
        static const int64 serialVersionUID = -8048474874175355449LL;
#endif        
};

class MultiLineString: public GeometryCollection{
public:

        MultiLineString(vector<Geometry *> *newLines, const GeometryFactory *newFactory);

        virtual ~MultiLineString();

        int getDimension() const;

        int getBoundaryDimension() const;

        Geometry* getBoundary() const;

        string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        bool isClosed() const;
        bool isSimple() const;
        bool equalsExact(const Geometry *other, double tolerance) const;
private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = 8166665132445433741I64;
#else
        static const int64 serialVersionUID = 8166665132445433741LL;
#endif        
};

class MultiPolygon: public GeometryCollection {

public:

        MultiPolygon(vector<Geometry *> *newPolys, const GeometryFactory *newFactory);

        virtual ~MultiPolygon();

        int getDimension() const;

        int getBoundaryDimension() const;

        Geometry* getBoundary() const;

        string getGeometryType() const;
        virtual GeometryTypeId getGeometryTypeId() const;
        bool isSimple() const;
        bool equalsExact(const Geometry *other, double tolerance) const;
private:
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = -551033529766975875I64;
#else
        static const int64 serialVersionUID = -551033529766975875LL;
#endif        
};

class GeometryFactory {
public:
        GeometryFactory();

        GeometryFactory(const PrecisionModel *pm, int newSRID, CoordinateSequenceFactory *nCoordinateSequenceFactory);

        GeometryFactory(CoordinateSequenceFactory *nCoordinateSequenceFactory);

        GeometryFactory(const PrecisionModel *pm);

        GeometryFactory(const PrecisionModel* pm, int newSRID);

        GeometryFactory(const GeometryFactory &gf);

        virtual ~GeometryFactory();

//Skipped a lot of list to array convertors

        Point* createPointFromInternalCoord(const Coordinate* coord, const Geometry *exemplar) const;

        Geometry* toGeometry(const Envelope* envelope) const;

        const PrecisionModel* getPrecisionModel() const;

        Point* createPoint() const;

        Point* createPoint(const Coordinate& coordinate) const;

        Point* createPoint(CoordinateSequence *coordinates) const;

        Point* createPoint(const CoordinateSequence &coordinates) const;

        GeometryCollection* createGeometryCollection() const;

        GeometryCollection* createGeometryCollection(vector<Geometry *> *newGeoms) const;

        GeometryCollection* createGeometryCollection(const vector<Geometry *> &newGeoms) const;

        MultiLineString* createMultiLineString() const;

        MultiLineString* createMultiLineString(vector<Geometry *> *newLines) const;

        MultiLineString* createMultiLineString(const vector<Geometry *> &fromLines) const;

        MultiPolygon* createMultiPolygon() const;

        MultiPolygon* createMultiPolygon(vector<Geometry *> *newPolys) const;

        MultiPolygon* createMultiPolygon(const vector<Geometry *> &fromPolys) const;

        LinearRing* createLinearRing() const;

        LinearRing* createLinearRing(CoordinateSequence* newCoords) const;

        LinearRing* createLinearRing(const CoordinateSequence& coordinates) const;

        MultiPoint* createMultiPoint() const;

        MultiPoint* createMultiPoint(vector<Geometry *> *newPoints) const;

        MultiPoint* createMultiPoint(const vector<Geometry *> &fromPoints) const;

        MultiPoint* createMultiPoint(const CoordinateSequence &fromCoords) const;

        Polygon* createPolygon() const;

        Polygon* createPolygon(LinearRing *shell, vector<Geometry *> *holes) const;

        Polygon* createPolygon(const LinearRing &shell, const vector<Geometry *> &holes) const;

        LineString* createLineString() const;

        LineString* createLineString(CoordinateSequence* coordinates) const;

        LineString* createLineString(const CoordinateSequence& coordinates) const;

        Geometry* buildGeometry(vector<Geometry *> *geoms) const;

        Geometry* buildGeometry(const vector<Geometry *> &geoms) const;
        
        int getSRID() const {return SRID;};

        const CoordinateSequenceFactory* getCoordinateSequenceFactory() const {return coordinateListFactory;};

        Geometry* createGeometry(const Geometry *g) const;

        void destroyGeometry(Geometry *g) const;

private:
        const PrecisionModel* precisionModel;
        int SRID;
#ifdef INT64_CONST_IS_I64
        static const int64 serialVersionUID = -6820524753094095635I64;
#else
        static const int64 serialVersionUID = -6820524753094095635LL;
#endif        
        const CoordinateSequenceFactory *coordinateListFactory;
};

/*
 * Represents a planar triangle, and provides methods for calculating various
 * properties of triangles.
 */
class Triangle {
public:
        Coordinate p0,p1,p2;
        Triangle(const Coordinate& nP0,const Coordinate& nP1,const Coordinate& nP2);
        Coordinate* inCentre();
};

} // namespace geos
#endif

/**********************************************************************
 * $Log: geom.h,v $
 * Revision 1.34.2.2.2.5  2006/04/28 18:39:57  sgillies
 * Add LinearRing::clone (bug 102)
 *
 * Revision 1.34.2.2.2.4  2006/01/16 11:08:38  strk
 * Removed invalid full qualification of in-class-declaration methods.
 *
 * Revision 1.34.2.2.2.3  2005/11/29 17:52:21  strk
 * undef PROFILE_COORDINATE_COPIES (was introduced by previous commit, to easy profiling)
 *
 * Revision 1.34.2.2.2.2  2005/11/29 17:51:15  strk
 * Forgot to add the capi/ dir
 *
 * Revision 1.34.2.2.2.1  2005/11/29 16:58:17  strk
 * Back-ported WKB IO and C api.
 * Added required higher dimensional interfaces for CoordinateSequence
 *
 * Revision 1.34.2.2  2005/11/08 09:08:07  strk
 * Cleaned up a couple of Doxygen warnings
 *
 * Revision 1.34.2.1  2005/05/23 18:16:40  strk
 * more math.h to cmath conversions
 *
 * Revision 1.34  2004/12/03 22:52:56  strk
 * enforced const return of CoordinateSequence::toVector() method to derivate classes.
 *
 * Revision 1.33  2004/12/03 16:22:36  frank
 * update to use I64 on MSVC for 64 bit integer constants, also toVector chg.
 *
 * Revision 1.32  2004/11/29 16:05:33  strk
 * Fixed a bug in LineIntersector::interpolateZ causing NaN values
 * to come out.
 * Handled dimensional collapses in ElevationMatrix.
 * Added ISNAN macro and changed ISNAN/FINITE macros to avoid
 * dispendious isnan() and finite() calls.
 *
 * Revision 1.31  2004/11/23 16:22:49  strk
 * Added ElevationMatrix class and components to do post-processing draping of overlayed geometries.
 *
 * Revision 1.30  2004/11/17 08:13:16  strk
 * Indentation changes.
 * Some Z_COMPUTATION activated by default.
 *
 * Revision 1.29  2004/11/08 10:57:42  strk
 * Moved Log lines at the bottom, and cut oldest
 *
 * Revision 1.28  2004/10/13 10:03:02  strk
 * Added missing linemerge and polygonize operation.
 * Bug fixes and leaks removal from the newly added modules and
 * planargraph (used by them).
 * Some comments and indentation changes.
 *
 * Revision 1.27  2004/09/16 09:48:06  strk
 * Added Envelope::equals
 *
 * Revision 1.26  2004/09/13 12:39:14  strk
 * Made Point and MultiPoint subject to Validity tests.
 *
 * Revision 1.25  2004/09/07 08:29:57  strk
 * Fixed doxygen malformed comment for Coordinate class
 *
 * Revision 1.24  2004/07/27 16:35:46  strk
 * Geometry::getEnvelopeInternal() changed to return a const Envelope *.
 * This should reduce object copies as once computed the envelope of a
 * geometry remains the same.
 *
 * Revision 1.23  2004/07/26 16:35:19  strk
 * Removed dangling MultiPoint::isClosed() method definition.
 *
 * Revision 1.22  2004/07/22 16:58:01  strk
 * runtime version extractor functions split. geos::version() is now
 * geos::geosversion() and geos::jtsport()
 *
 **********************************************************************/

---