secondo/Algebras/Spatial/RegionCreator.h

/*
----
This file is part of SECONDO.

Copyright (C) 2012, University in Hagen, Department of Computer Science,
Database Systems for New Applications.

SECONDO 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.

SECONDO 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 SECONDO; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
----

*/

#ifndef REGIONCREATOR_H
#define REGIONCREATOR_H



#include "RegionT.h"
#include <vector>
/*
1 Class RegionCreator

This class contains functions for a creation of a region from a set 
of halfsegments.

*/

 template<template<typename T>class Array>
class RegionCreator{

  public:

/*
1.1 Public Function

This function creates a region from a set of halfsegments.
The Halfsegmentarray must be:
  - complete : for each halfsegment, the corresponding partner is inside
  - correct respective to partner numbers
  - realminized, i.e. overlapping or crossing halfsegments are not allowed
  - sorted with respect to the halfsegment order

*/
   static  void createRegion(const Array<HalfSegment>*, RegionT<Array>* result);

    // sets the partner, assumes equal edgenos for partners
    static void setPartnerNo(Array<HalfSegment>* hss);

    // find the critical points within hss
    static void findCritical(const Array<HalfSegment>* hss, char* critical);

    // returns the length of the segment starting at (x,y) 
    // going horizontal to left
    // until the interscetion point with hs, if no intersection point exists,
    // -1 is returned
    static double getLeftDist(const HalfSegment& hs, 
                       const double x, const double y, const bool move);

    static double getLeftDist(const HalfSegment& hs,
                              const double x, const double y){
      return getLeftDist(hs,x,y,false);
    }

    
    static double getUpDist(const HalfSegment& hs, 
                       const double x, const double y);
    
     static double getRightDist(const HalfSegment& hs, 
                       const double x, const double y);
     
     static double getDownDist(const HalfSegment& hs, 
                       const double x, const double y);

    // checks whether r is to the right of the ray defined by p qnd q 
    static bool isRight(const Point& p, const Point& q, const Point& r);
    
    // checks whether a horizontal ray starting at (x,y) to left 
    // intersects hs
    static size_t intersects(const double x, const double y, 
                      const HalfSegment& hs); 
  private:

/*
1.2 Members 

*/
     std::vector<std::vector<HalfSegment> > cycles; // stored cycles found
     std::vector<bool> holes;                  // flags whethe a cycle is a hole
     std::vector<int> correspondingOuters;// cooresponding outer cycles for 
                                          // each cycle
                                          // outer cycles refer to themself
     std::vector<int> leftMostPoints;     // index of the leftmost dominating 
                                          // point of each cycle

     // Constructor
     RegionCreator(const Array<HalfSegment>* hss, RegionT<Array>* _result);



    // forcePairsFromLeftDom
    static Array<HalfSegment>* 
       forcePairsFromLeftDom(const Array<HalfSegment>* hss);



    // findCycles, fills the cycles vector from the halfsegments
    void findCycles(const Array<HalfSegment>* hss);

    // finds a single cycle
    void findCycle(const Array<HalfSegment>* hss, int pos, 
                   char* usage, const char* critical);

    
    // returns the Halfsegment with maximum slope at a given dominating point 
    // i.e. the dominating point of the halfsgement indexed by pos within hss
    static int getStartPos(const Array<HalfSegment>* hss, 
                           int pos, char* usage);

    // returns an extension of a cycle, or -1 if no extension is possible
    static int getNext(const Array<HalfSegment>* hss, int pos,  
                       const char* usage);

    


    // checks whether hs2 is more right than hs1
    static bool moreRight(const HalfSegment& hs1, const HalfSegment& hs2);

    // output functions
    void printCycles() const;
    void printCycle(size_t i) const;
  

     double getLeftDist(const int cycle, 
                        const double x, const double y) const;

    // detects holes within the cycles vector
    void detectHoles();
    // checks whether the cycle at position index is a hole
    bool isHole(size_t index) const; 
    // checks whether a point is inside the region defined by all cycles except 
    // the one at position ommit
    bool isInside(const double x, const double y, size_t ommit) const;

    // finds out the outer cycles where the holes belongs to
    void findCorrespondingOuters();
    // find the nearest outer cycle intersecting a horizontal ray
    // starting at(x,y) to left
    int findLeftNearestOuter(const double x, const double y) const;
    // sets the insideabove flags of the halfsegments within the cycles
    void setInsideAbove();
    // sets the insideAbove flags for the halfsegments of a specified cycle
    void setInsideAbove(const int i);
    // creates a region from the halfsegments and all other vectors
    void buildRegion(RegionT<Array>* result) const;
    // saves a single face
    void saveFace(const int cycle, const int faceno, 
                  int& edgeno, RegionT<Array> * result) const;
    // saves a single cycle
    bool saveCycle(const int cycle, const int faceno, 
                   const int cycleno, int& edgeno, 
                   RegionT<Array>* result) const;

};

template<template<typename T> class Array>
void markUsage(const Array<HalfSegment>* line, char* usage, char* critical );


#include "RegionCreatorImpl.h"


#endif