189 lines
6.1 KiB
C++
189 lines
6.1 KiB
C++
|
|
/*
|
|
----
|
|
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
|
|
|
|
|