StelSphereGeometry.hpp

Go to the documentation of this file.

/*
 * Stellarium
 * Copyright (C) 2009 Fabien Chereau
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA  02110-1335, USA.
 */

#ifndef _STELSPHEREGEOMETRY_HPP_
#define _STELSPHEREGEOMETRY_HPP_

#include "OctahedronPolygon.hpp"
#include "StelVertexArray.hpp"
#include "VecMath.hpp"

#include <QVector>
#include <QVariant>
#include <QDebug>
#include <QSharedPointer>
#include <QVarLengthArray>
#include <QDataStream>

#include <stdio.h>

class SphericalRegion;
class SphericalPolygon;
class SphericalConvexPolygon;
class SphericalCap;
class SphericalPoint;
class AllSkySphericalRegion;
class EmptySphericalRegion;


class SphericalRegionP : public QSharedPointer<SphericalRegion>
{
public:
    // Override the constructors of QSharedPointer
    SphericalRegionP() {;}
    SphericalRegionP(SphericalRegion* ptr) : QSharedPointer<SphericalRegion>(ptr) {;}
    template <class Deleter> SphericalRegionP(SphericalRegion* ptr, Deleter deleter) : QSharedPointer<SphericalRegion>(ptr, deleter) {;}
    SphericalRegionP(const SphericalRegionP& other) : QSharedPointer<SphericalRegion>(other) {;}
    SphericalRegionP(const QWeakPointer<SphericalRegion>& other) : QSharedPointer<SphericalRegion>(other) {;}

    static SphericalRegionP loadFromJson(QIODevice* in);

    static SphericalRegionP loadFromJson(const QByteArray& a);

    static SphericalRegionP loadFromQVariant(const QVariantMap& map);
    // It can only be a pure shape definition, without texture coords
    static SphericalRegionP loadFromQVariant(const QVariantList& list);

    static void serializeToJson(const QVariant& jsonObject, QIODevice* output, int indentLevel=0);

    static int metaTypeId;

private:

    static int initialize();
};

// Allow to use SphericalRegionP with the Qt MetaType system.
Q_DECLARE_METATYPE(SphericalRegionP)

QDataStream& operator<<(QDataStream& out, const SphericalRegionP& region);
QDataStream& operator>>(QDataStream& in, SphericalRegionP& region);

class SphericalRegion
{
public:
    enum SphericalRegionType
    {
        Point = 0,
        Cap = 1,
        AllSky = 2,
        Polygon = 3,
        ConvexPolygon = 4,
        Empty = 5,
        Invalid = 6
    };

    virtual ~SphericalRegion() {;}

    virtual SphericalRegionType getType() const = 0;

    virtual OctahedronPolygon getOctahedronPolygon() const =0;

    virtual double getArea() const {return getOctahedronPolygon().getArea();}

    virtual bool isEmpty() const {return getOctahedronPolygon().isEmpty();}

    virtual Vec3d getPointInside() const {return getOctahedronPolygon().getPointInside();}

    virtual QVector<SphericalCap> getBoundingSphericalCaps() const;

    virtual SphericalCap getBoundingCap() const;

    virtual SphericalRegionP getEnlarged(double margin) const;

    virtual StelVertexArray getFillVertexArray() const {return getOctahedronPolygon().getFillVertexArray();}

    virtual StelVertexArray getOutlineVertexArray() const {return getOctahedronPolygon().getOutlineVertexArray();}

    virtual QVector<QVector<Vec3d > > getSimplifiedContours() const;
    
    virtual QVariantList toQVariant() const = 0;

    virtual void serialize(QDataStream& out) const = 0;

    QByteArray toJSON() const;

    bool contains(const SphericalRegion* r) const;
    bool contains(const SphericalRegionP r) const {return contains(r.data());}
    virtual bool contains(const Vec3d& p) const {return getOctahedronPolygon().contains(p);}
    virtual bool contains(const SphericalPolygon& r) const;
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& r) const;
    virtual bool contains(const SphericalPoint& r) const;
    virtual bool contains(const AllSkySphericalRegion& r) const;
    bool contains(const EmptySphericalRegion&) const {return false;}

    bool intersects(const SphericalRegion* r) const;
    bool intersects(const SphericalRegionP r) const {return intersects(r.data());}
    bool intersects(const Vec3d& p) const {return contains(p);}
    virtual bool intersects(const SphericalPolygon& r) const;
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalCap& r) const;
    virtual bool intersects(const SphericalPoint& r) const;
    virtual bool intersects(const AllSkySphericalRegion& r) const;
    bool intersects(const EmptySphericalRegion&) const {return false;}

    SphericalRegionP getIntersection(const SphericalRegion* r) const;
    SphericalRegionP getIntersection(const SphericalRegionP r) const {return getIntersection(r.data());}
    virtual SphericalRegionP getIntersection(const SphericalPolygon& r) const;
    virtual SphericalRegionP getIntersection(const SphericalConvexPolygon& r) const;
    virtual SphericalRegionP getIntersection(const SphericalCap& r) const;
    virtual SphericalRegionP getIntersection(const SphericalPoint& r) const;
    virtual SphericalRegionP getIntersection(const AllSkySphericalRegion& r) const;
    SphericalRegionP getIntersection(const EmptySphericalRegion& r) const;

    SphericalRegionP getUnion(const SphericalRegion* r) const;
    SphericalRegionP getUnion(const SphericalRegionP r) const {return getUnion(r.data());}
    virtual SphericalRegionP getUnion(const SphericalPolygon& r) const;
    virtual SphericalRegionP getUnion(const SphericalConvexPolygon& r) const;
    virtual SphericalRegionP getUnion(const SphericalCap& r) const;
    virtual SphericalRegionP getUnion(const SphericalPoint& r) const;
    SphericalRegionP getUnion(const AllSkySphericalRegion& r) const;
    virtual SphericalRegionP getUnion(const EmptySphericalRegion& r) const;

    SphericalRegionP getSubtraction(const SphericalRegion* r) const;
    SphericalRegionP getSubtraction(const SphericalRegionP r) const {return getSubtraction(r.data());}
    virtual SphericalRegionP getSubtraction(const SphericalPolygon& r) const;
    virtual SphericalRegionP getSubtraction(const SphericalConvexPolygon& r) const;
    virtual SphericalRegionP getSubtraction(const SphericalCap& r) const;
    virtual SphericalRegionP getSubtraction(const SphericalPoint& r) const;
    SphericalRegionP getSubtraction(const AllSkySphericalRegion& r) const;
    virtual SphericalRegionP getSubtraction(const EmptySphericalRegion& r) const;

private:
    bool containsDefault(const SphericalRegion* r) const;
    bool intersectsDefault(const SphericalRegion* r) const;
    SphericalRegionP getIntersectionDefault(const SphericalRegion* r) const;
    SphericalRegionP getUnionDefault(const SphericalRegion* r) const;
    SphericalRegionP getSubtractionDefault(const SphericalRegion* r) const;
};


class SphericalCap : public SphericalRegion
{
    using SphericalRegion::contains;
public:
    SphericalCap() : d(0) {;}

    SphericalCap(double x, double y, double z) : n(x,y,z), d(0) {;}

    SphericalCap(const Vec3d& an, double ar) : n(an), d(ar) {//n.normalize();
        Q_ASSERT(d==0 || std::fabs(n.lengthSquared()-1.)<0.0000001);}
    // FIXME: GZ reports 2013-03-02: apparently the Q_ASSERT is here because n should be normalized at this point, but
    // for efficiency n.normalize() should not be called at this point.
    // However, when zooming in a bit in Hammer-Aitoff and Mercator projections, this Assertion fires.
    // Atmosphere must be active
    // It may have to do with DSO texture rendering.
    // found at r5863.
    // n.normalize() prevents this for now, but may cost performance.
    // AARGH - activating n.normalize() inhibits mouse-identification/selection of stars!
    // May be compiler dependent (seen on Win/MinGW), AW cannot confirm it on Linux.

    SphericalCap(const SphericalCap& other) : SphericalRegion(), n(other.n), d(other.d) {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Cap;}
    virtual OctahedronPolygon getOctahedronPolygon() const;

    virtual double getArea() const {return 2.*M_PI*(1.-d);}

    virtual bool isEmpty() const {return d>=1.;}

    virtual Vec3d getPointInside() const {return n;}

    virtual SphericalCap getBoundingCap() const {return *this;}

    // Contain and intersect    
    virtual bool contains(const Vec3d &v) const {Q_ASSERT(d==0 || std::fabs(v.lengthSquared()-1.)<0.0000002);return (v*n>=d);}
    virtual bool contains(const Vec3f &v) const {Q_ASSERT(d==0 || std::fabs(v.lengthSquared()-1.f)<0.000002f);return (v[0]*n[0]+v[1]*n[1]+v[2]*n[2]>=d);}
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& h) const
    {
        const double a = n*h.n-d*h.d;
        return d<=h.d && ( a>=1. || (a>=0. && a*a >= (1.-d*d)*(1.-h.d*h.d)));
    }
    virtual bool contains(const AllSkySphericalRegion&) const {return d<=-1;}
    virtual bool intersects(const SphericalPolygon& r) const;
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalCap& h) const
    {
        const double a = d*h.d - n*h.n;
        return d+h.d<=0. || a<=0. || (a<=1. && a*a <= (1.-d*d)*(1.-h.d*h.d));
    }
    virtual bool intersects(const AllSkySphericalRegion&) const {return d<=1.;}

    virtual QVariantList toQVariant() const;

    virtual void serialize(QDataStream& out) const {out << n << d;}

    // Methods specific to SphericalCap

    double getRadius() const {return std::acos(d);}

    inline bool intersectsHalfSpace(double hn0, double hn1, double hn2) const
    {
        const double a = n[0]*hn0+n[1]*hn1+n[2]*hn2;
        return d<=0. || a<=0. || (a<=1. && a*a <= (1.-d*d));
    }

    bool clipGreatCircle(Vec3d& v1, Vec3d& v2) const;

    bool operator==(const SphericalCap& other) const {return (n==other.n && d==other.d);}

    QVector<Vec3d> getClosedOutlineContour() const;

    bool intersectsConvexContour(const Vec3d* vertice, int nbVertice) const;

    bool containsTriangle(const Vec3d* vertice) const;

    bool intersectsTriangle(const Vec3d* vertice) const;

    static SphericalRegionP deserialize(QDataStream& in);

    static double relativeAreaOverlap(const SphericalCap& c1, const SphericalCap& c2);

    static double relativeDiameterOverlap(const SphericalCap& c1, const SphericalCap& c2);

    static bool intersectionPoints(const SphericalCap& h1, const SphericalCap& h2, Vec3d& p1, Vec3d& p2);

    Vec3d n;
    double d;
};

inline bool sideHalfSpaceContains(const Vec3d& v1, const Vec3d& v2, const Vec3d& p)
{
    return (v1[1] * v2[2] - v1[2] * v2[1])*p[0] +
            (v1[2] * v2[0] - v1[0] * v2[2])*p[1] +
            (v1[0] * v2[1] - v1[1] * v2[0])*p[2]>=-1e-17;
}

inline bool sideHalfSpaceContains(const Vec3d& v1, const Vec3d& v2, const SphericalCap& h)
{
    Vec3d n(v1[1]*v2[2]-v1[2]*v2[1], v2[0]*v1[2]-v2[2]*v1[0], v2[1]*v1[0]-v2[0]*v1[1]);
    n.normalize();
    const double a = n*h.n;
    return 0<=h.d && ( a>=1. || (a>=0. && a*a >= 1.-h.d*h.d));
}

inline bool sideHalfSpaceIntersects(const Vec3d& v1, const Vec3d& v2, const SphericalCap& h)
{
    Vec3d n(v1[1]*v2[2]-v1[2]*v2[1], v2[0]*v1[2]-v2[2]*v1[0], v2[1]*v1[0]-v2[0]*v1[1]);
    n.normalize();
    return  h.intersectsHalfSpace(n[0], n[1], n[2]);
}

class SphericalPoint : public SphericalRegion
{
public:
    SphericalPoint(const Vec3d& an) : n(an) {Q_ASSERT(std::fabs(1.-n.length())<0.0000001);}
    virtual ~SphericalPoint() {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Point;}
    virtual OctahedronPolygon getOctahedronPolygon() const;
    virtual double getArea() const {return 0.;}
    virtual bool isEmpty() const {return false;}
    virtual Vec3d getPointInside() const {return n;}
    virtual SphericalCap getBoundingCap() const {return SphericalCap(n, 1);}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const {out << n;}

    // Contain and intersect
    virtual bool contains(const Vec3d& p) const {return n==p;}
    virtual bool contains(const SphericalPolygon&) const {return false;}
    virtual bool contains(const SphericalConvexPolygon&) const {return false;}
    virtual bool contains(const SphericalCap&) const {return false;}
    virtual bool contains(const SphericalPoint& r) const {return n==r.n;}
    virtual bool contains(const AllSkySphericalRegion&) const {return false;}
    virtual bool intersects(const SphericalPolygon&) const;
    virtual bool intersects(const SphericalConvexPolygon&) const;
    virtual bool intersects(const SphericalCap& r) const {return r.contains(n);}
    virtual bool intersects(const SphericalPoint& r) const {return n==r.n;}
    virtual bool intersects(const AllSkySphericalRegion&) const {return true;}

    static SphericalRegionP deserialize(QDataStream& in);

    Vec3d n;
};

class AllSkySphericalRegion : public SphericalRegion
{
public:
    virtual ~AllSkySphericalRegion() {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::AllSky;}
    virtual OctahedronPolygon getOctahedronPolygon() const {return OctahedronPolygon::getAllSkyOctahedronPolygon();}
    virtual double getArea() const {return 4.*M_PI;}
    virtual bool isEmpty() const {return false;}
    virtual Vec3d getPointInside() const {return Vec3d(1,0,0);}
    virtual SphericalCap getBoundingCap() const {return SphericalCap(Vec3d(1,0,0), -2);}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream&) const {;}

    // Contain and intersect
    virtual bool contains(const Vec3d&) const {return true;}
    virtual bool contains(const SphericalPolygon&) const {return true;}
    virtual bool contains(const SphericalConvexPolygon&) const {return true;}
    virtual bool contains(const SphericalCap&) const {return true;}
    virtual bool contains(const SphericalPoint&) const {return true;}
    virtual bool contains(const AllSkySphericalRegion&) const {return true;}
    virtual bool intersects(const SphericalPolygon&) const {return true;}
    virtual bool intersects(const SphericalConvexPolygon&) const {return true;}
    virtual bool intersects(const SphericalCap&) const {return true;}
    virtual bool intersects(const SphericalPoint&) const {return true;}
    virtual bool intersects(const AllSkySphericalRegion&) const {return true;}

    static const SphericalRegionP staticInstance;
};

class EmptySphericalRegion : public SphericalRegion
{
public:
    // Avoid name hiding when overloading the virtual methods.
    using SphericalRegion::intersects;
    using SphericalRegion::contains;
    using SphericalRegion::getIntersection;
    using SphericalRegion::getUnion;
    using SphericalRegion::getSubtraction;

    EmptySphericalRegion() {;}
    virtual ~EmptySphericalRegion() {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Empty;}
    virtual OctahedronPolygon getOctahedronPolygon() const {return OctahedronPolygon::getEmptyOctahedronPolygon();}
    virtual double getArea() const {return 0.;}
    virtual bool isEmpty() const {return true;}
    virtual Vec3d getPointInside() const {return Vec3d(1,0,0);}
    virtual SphericalCap getBoundingCap() const {return SphericalCap(Vec3d(1,0,0), 2);}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream&) const {;}

    // Contain and intersect
    virtual bool contains(const Vec3d&) const {return false;}
    virtual bool contains(const SphericalPolygon&) const {return false;}
    virtual bool contains(const SphericalConvexPolygon&) const {return false;}
    virtual bool contains(const SphericalCap&) const {return false;}
    virtual bool contains(const SphericalPoint&) const {return false;}
    virtual bool contains(const AllSkySphericalRegion&) const {return false;}
    virtual bool intersects(const SphericalPolygon&) const {return false;}
    virtual bool intersects(const SphericalConvexPolygon&) const {return false;}
    virtual bool intersects(const SphericalCap&) const {return false;}
    virtual bool intersects(const SphericalPoint&) const {return false;}
    virtual bool intersects(const AllSkySphericalRegion&) const {return false;}

    static const SphericalRegionP staticInstance;
};


class SphericalPolygon : public SphericalRegion
{
public:
    // Avoid name hiding when overloading the virtual methods.
    using SphericalRegion::intersects;
    using SphericalRegion::contains;
    using SphericalRegion::getIntersection;
    using SphericalRegion::getUnion;
    using SphericalRegion::getSubtraction;

    SphericalPolygon() {;}
    SphericalPolygon(const QVector<QVector<Vec3d> >& contours) : octahedronPolygon(contours) {;}
    SphericalPolygon(const QVector<Vec3d>& contour) : octahedronPolygon(contour) {;}
    SphericalPolygon(const OctahedronPolygon& octContour) : octahedronPolygon(octContour) {;}
    SphericalPolygon(const QList<OctahedronPolygon>& octContours) : octahedronPolygon(octContours) {;}

    virtual SphericalRegionType getType() const {return SphericalRegion::Polygon;}
    virtual OctahedronPolygon getOctahedronPolygon() const {return octahedronPolygon;}

    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const;

    virtual SphericalCap getBoundingCap() const;

    virtual bool contains(const Vec3d& p) const {return octahedronPolygon.contains(p);}
    virtual bool contains(const SphericalPolygon& r) const {return octahedronPolygon.contains(r.octahedronPolygon);}
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& r) const {return octahedronPolygon.contains(r.getOctahedronPolygon());}
    virtual bool contains(const SphericalPoint& r) const {return octahedronPolygon.contains(r.n);}
    virtual bool contains(const AllSkySphericalRegion& r) const {return octahedronPolygon.contains(r.getOctahedronPolygon());}

    virtual bool intersects(const SphericalPolygon& r) const {return octahedronPolygon.intersects(r.octahedronPolygon);}
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalCap& r) const {return r.intersects(*this);}
    virtual bool intersects(const SphericalPoint& r) const {return octahedronPolygon.contains(r.n);}
    virtual bool intersects(const AllSkySphericalRegion&) const {return !isEmpty();}

    virtual SphericalRegionP getIntersection(const SphericalPoint& r) const {return contains(r.n) ? SphericalRegionP(new SphericalPoint(r)) : EmptySphericalRegion::staticInstance;}
    virtual SphericalRegionP getIntersection(const AllSkySphericalRegion& ) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}

    virtual SphericalRegionP getUnion(const SphericalPoint&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}
    virtual SphericalRegionP getUnion(const EmptySphericalRegion&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}

    virtual SphericalRegionP getSubtraction(const SphericalPoint&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}
    virtual SphericalRegionP getSubtraction(const EmptySphericalRegion&) const {return SphericalRegionP(new SphericalPolygon(octahedronPolygon));}

    // Methods specific to SphericalPolygon
    void setContours(const QVector<QVector<Vec3d> >& contours) {octahedronPolygon = OctahedronPolygon(contours);}

    void setContour(const QVector<Vec3d>& contour) {octahedronPolygon = OctahedronPolygon(contour);}

    QVector<QVector<Vec3d> > getClosedOutlineContours() const {Q_ASSERT(0); return QVector<QVector<Vec3d> >();}

    static SphericalRegionP deserialize(QDataStream& in);

    static SphericalRegionP multiUnion(const QList<SphericalRegionP>& regions, bool optimizeByPreGrouping=false);
    
    static SphericalRegionP multiIntersection(const QList<SphericalRegionP>& regions);

private:
    OctahedronPolygon octahedronPolygon;
};


class SphericalConvexPolygon : public SphericalRegion
{
public:
    // Avoid name hiding when overloading the virtual methods.
    using SphericalRegion::intersects;
    using SphericalRegion::contains;

    SphericalConvexPolygon() {;}

    SphericalConvexPolygon(const QVector<QVector<Vec3d> >& contours) {Q_ASSERT(contours.size()==1); setContour(contours.at(0));}
    SphericalConvexPolygon(const QVector<Vec3d>& contour) {setContour(contour);}
    SphericalConvexPolygon(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2) {contour << e0 << e1 << e2; updateBoundingCap();}
    SphericalConvexPolygon(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2, const Vec3d &e3)  {contour << e0 << e1 << e2 << e3; updateBoundingCap();}

    virtual SphericalRegionType getType() const {return SphericalRegion::ConvexPolygon;}
    virtual OctahedronPolygon getOctahedronPolygon() const {return OctahedronPolygon(contour);}
    virtual StelVertexArray getFillVertexArray() const {return StelVertexArray(contour, StelVertexArray::TriangleFan);}
    virtual StelVertexArray getOutlineVertexArray() const {return StelVertexArray(contour, StelVertexArray::LineLoop);}
    virtual double getArea() const;
    virtual bool isEmpty() const {return contour.isEmpty();}
    virtual Vec3d getPointInside() const;
    virtual SphericalCap getBoundingCap() const {return cachedBoundingCap;}
    QVector<SphericalCap> getBoundingSphericalCaps() const;
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const {out << contour;}

    // Contain and intersect
    virtual bool contains(const Vec3d& p) const;
    virtual bool contains(const SphericalPolygon& r) const;
    virtual bool contains(const SphericalConvexPolygon& r) const;
    virtual bool contains(const SphericalCap& r) const;
    virtual bool contains(const SphericalPoint& r) const {return contains(r.n);}
    virtual bool contains(const AllSkySphericalRegion&) const {return false;}
    virtual bool intersects(const SphericalCap& r) const {if (!cachedBoundingCap.intersects(r)) return false; return r.intersects(*this);}
    virtual bool intersects(const SphericalPolygon& r) const;
    virtual bool intersects(const SphericalConvexPolygon& r) const;
    virtual bool intersects(const SphericalPoint& r) const {return contains(r.n);}
    virtual bool intersects(const AllSkySphericalRegion&) const {return true;}

//  virtual SphericalRegionP getIntersection(const SphericalPolygon& r) const;
//  virtual SphericalRegionP getIntersection(const SphericalConvexPolygon& r) const;
//  virtual SphericalRegionP getIntersection(const SphericalCap& r) const;
//  virtual SphericalRegionP getIntersection(const SphericalPoint& r) const;
//  virtual SphericalRegionP getIntersection(const AllSkySphericalRegion& r) const;
//  virtual SphericalRegionP getUnion(const SphericalPolygon& r) const;
//  virtual SphericalRegionP getUnion(const SphericalConvexPolygon& r) const;
//  virtual SphericalRegionP getUnion(const SphericalCap& r) const;
//  virtual SphericalRegionP getUnion(const SphericalPoint& r) const;
//  virtual SphericalRegionP getUnion(const EmptySphericalRegion& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalPolygon& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalConvexPolygon& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalCap& r) const;
//  virtual SphericalRegionP getSubtraction(const SphericalPoint& r) const;
//  virtual SphericalRegionP getSubtraction(const EmptySphericalRegion& r) const;

    // Methods specific to SphericalConvexPolygon
    void setContour(const QVector<Vec3d>& acontour) {contour=acontour; updateBoundingCap();}

    const QVector<Vec3d>& getConvexContour() const {return contour;}

    bool checkValid() const;

    static bool checkValidContour(const QVector<Vec3d>& contour);

    static SphericalRegionP deserialize(QDataStream& in);

protected:
    QVector<Vec3d> contour;

    SphericalCap cachedBoundingCap;

    void updateBoundingCap();

    static bool areAllPointsOutsideOneSide(const Vec3d* thisContour, int nbThisContour, const Vec3d* points, int nbPoints);

    bool areAllPointsOutsideOneSide(const QVector<Vec3d>& points) const
    {
        return areAllPointsOutsideOneSide(contour.constData(), contour.size(), points.constData(), points.size());
    }

    bool containsConvexContour(const Vec3d* vertice, int nbVertex) const;
};


// ! @class SphericalConvexPolygonSet
// ! A special case of SphericalPolygon for which the polygon is composed of disjoint convex polygons.
//class SphericalConvexPolygonSet : public SphericalRegion
//{
//public:
//  // Avoid name hiding when overloading the virtual methods.
//  using SphericalRegion::intersects;
//  using SphericalRegion::contains;
//
//  //! Default constructor.
//  SphericalConvexPolygonSet() {;}
//
//  //! Constructor from a list of contours.
//  SphericalConvexPolygonSet(const QVector<QVector<Vec3d> >& contours);
//
//  virtual SphericalRegionType getType() const {return SphericalRegion::ConvexPolygonSet;}
//  virtual OctahedronPolygon getOctahedronPolygon() const;
//  virtual StelVertexArray getFillVertexArray() const;
//  virtual StelVertexArray getOutlineVertexArray() const;
//  virtual double getArea() const;
//  virtual bool isEmpty() const;
//  virtual Vec3d getPointInside() const;
//  virtual SphericalCap getBoundingCap() const {return cachedBoundingCap;}
//  QVector<SphericalCap> getBoundingSphericalCaps() const;
//  //! Serialize the region into a QVariant map matching the JSON format.
//  //! The format is
//  //! @code["CONVEX_POLYGON_SET", [[ra,dec], [ra,dec], [ra,dec], [ra,dec]], [[ra,dec], [ra,dec], [ra,dec], [ra,dec]]]@endcode
//  //! where the coords from a list of closed convex contour, with each points defined by ra dec in degree in the ICRS frame.
//  virtual QVariantList toQVariant() const;
//  virtual void serialize(QDataStream& out) const;
//
//  // Contain and intersect
//  virtual bool contains(const Vec3d& p) const;
//  virtual bool contains(const SphericalPolygon& r) const;
//  virtual bool contains(const SphericalConvexPolygon& r) const;
//  virtual bool contains(const SphericalCap& r) const;
//  virtual bool contains(const SphericalPoint& r) const {return contains(r.n);}
//  virtual bool contains(const AllSkySphericalRegion&) const {return false;}
//  virtual bool intersects(const SphericalCap& r) const {if (!cachedBoundingCap.intersects(r)) return false; return r.intersects(*this);}
//  virtual bool intersects(const SphericalPolygon& r) const;
//  virtual bool intersects(const SphericalConvexPolygon& r) const;
//  virtual bool intersects(const SphericalPoint& r) const {return contains(r.n);}
//  virtual bool intersects(const AllSkySphericalRegion&) const {return true;}
//
//  ////////////////////////////////////////////////////////////////////
//  // Methods specific to SphericalConvexPolygonSet
//  ////////////////////////////////////////////////////////////////////
//  //! Deserialize the region. This method must allow as fast as possible deserialization.
//  static SphericalRegionP deserialize(QDataStream& in);
//
//protected:
//  QVector<SphericalConvexPolygon> contours;
//
//  //! Cache the bounding cap.
//  SphericalCap cachedBoundingCap;
//
//  //! Update the bounding cap from the vertex list.
//  void updateBoundingCap();
//};

class SphericalTexturedPolygon : public SphericalPolygon
{
public:
    struct TextureVertex
    {
        Vec3d vertex;
        Vec2f texCoord;
    };

    SphericalTexturedPolygon() {;}
    SphericalTexturedPolygon(const QVector<QVector<TextureVertex> >& contours) {Q_UNUSED(contours); Q_ASSERT(0);}
    SphericalTexturedPolygon(const QVector<TextureVertex>& contour) {Q_UNUSED(contour); Q_ASSERT(0);}

    virtual StelVertexArray getFillVertexArray() const {Q_ASSERT(0); return StelVertexArray();}
    virtual QVariantList toQVariant() const;
    virtual void serialize(QDataStream& out) const {Q_UNUSED(out); Q_ASSERT(0);}

    // Methods specific to SphericalTexturedPolygon
    void setContours(const QVector<QVector<TextureVertex> >& contours) {Q_UNUSED(contours); Q_ASSERT(0);}

    void setContour(const QVector<TextureVertex>& contour) {Q_UNUSED(contour); Q_ASSERT(0);}

private:
    QVector<Vec2f> textureCoords;
};


Q_DECLARE_TYPEINFO(SphericalTexturedPolygon::TextureVertex, Q_PRIMITIVE_TYPE);

class SphericalTexturedConvexPolygon : public SphericalConvexPolygon
{
public:
    SphericalTexturedConvexPolygon() {;}

    SphericalTexturedConvexPolygon(const QVector<Vec3d>& contour, const QVector<Vec2f>& texCoord) {setContour(contour, texCoord);}

    SphericalTexturedConvexPolygon(const Vec3d &e0,const Vec3d &e1,const Vec3d &e2, const Vec3d &e3) : SphericalConvexPolygon(e0,e1,e2,e3)
    {
        textureCoords << Vec2f(0.f, 0.f) << Vec2f(1.f, 0.f) << Vec2f(1.f, 1.f) << Vec2f(0.f, 1.f);
    }

    virtual StelVertexArray getFillVertexArray() const {return StelVertexArray(contour, StelVertexArray::TriangleFan, textureCoords);}

    virtual void setContour(const QVector<Vec3d>& acontour, const QVector<Vec2f>& texCoord) {SphericalConvexPolygon::setContour(acontour); textureCoords=texCoord;}

    virtual QVariantList toQVariant() const;

    virtual void serialize(QDataStream& out) const {out << contour << textureCoords;}

protected:
    QVector<Vec2f> textureCoords;
};


Vec3d greatCircleIntersection(const Vec3d& p1, const Vec3d& p2, const Vec3d& p3, const Vec3d& p4, bool& ok);

Vec3d greatCircleIntersection(const Vec3d& p1, const Vec3d& p2, const Vec3d& nHalfSpace, bool& ok);

#endif // _STELSPHEREGEOMETRY_HPP_