/* ---- 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 /* 1 Class RegionCreator This class contains functions for a creation of a region from a set of halfsegments. */ templateclass 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*, RegionT* result); // sets the partner, assumes equal edgenos for partners static void setPartnerNo(Array* hss); // find the critical points within hss static void findCritical(const Array* 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 > cycles; // stored cycles found std::vector holes; // flags whethe a cycle is a hole std::vector correspondingOuters;// cooresponding outer cycles for // each cycle // outer cycles refer to themself std::vector leftMostPoints; // index of the leftmost dominating // point of each cycle // Constructor RegionCreator(const Array* hss, RegionT* _result); // forcePairsFromLeftDom static Array* forcePairsFromLeftDom(const Array* hss); // findCycles, fills the cycles vector from the halfsegments void findCycles(const Array* hss); // finds a single cycle void findCycle(const Array* 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* hss, int pos, char* usage); // returns an extension of a cycle, or -1 if no extension is possible static int getNext(const Array* 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* result) const; // saves a single face void saveFace(const int cycle, const int faceno, int& edgeno, RegionT * result) const; // saves a single cycle bool saveCycle(const int cycle, const int faceno, const int cycleno, int& edgeno, RegionT* result) const; }; template class Array> void markUsage(const Array* line, char* usage, char* critical ); #include "RegionCreatorImpl.h" #endif