673 lines
12 KiB
C++
673 lines
12 KiB
C++
|
|
|
|
/*
|
|
5 Auxiliary structures for plane sweep algorithms
|
|
|
|
5.1 Definition of ~ownertype~
|
|
|
|
This enumeration is used to indicate the source of an ~AVLSegment~.
|
|
|
|
*/
|
|
|
|
#ifndef _AVLSEGMENT_H_
|
|
#define _AVLSEGMENT_H_
|
|
|
|
#include "HalfSegment.h"
|
|
#include "Coord.h"
|
|
|
|
|
|
int HalfSegmentCompare(const void *a, const void *b);
|
|
|
|
|
|
|
|
class myexception: public std::exception
|
|
{
|
|
public:
|
|
myexception(const std::string& s) : err(s){}
|
|
|
|
~myexception() throw() {}
|
|
|
|
private:
|
|
virtual const char* what() const throw()
|
|
{
|
|
return err.c_str();
|
|
}
|
|
|
|
std::string err;
|
|
|
|
};
|
|
|
|
|
|
namespace avlseg{
|
|
|
|
|
|
class ExtendedHalfSegment: public HalfSegment{
|
|
public:
|
|
ExtendedHalfSegment(){initialized=false;}
|
|
|
|
ExtendedHalfSegment(const ExtendedHalfSegment& ehs):
|
|
originX1(ehs.originX1),
|
|
originX2(ehs.originX2),
|
|
originY1(ehs.originY1),
|
|
originY2(ehs.originY2),
|
|
initialized(ehs.initialized){
|
|
if(ehs.initialized){
|
|
HalfSegment::operator=(ehs);
|
|
}
|
|
}
|
|
|
|
ExtendedHalfSegment(const HalfSegment& hs):
|
|
HalfSegment(hs){
|
|
Point p = hs.GetLeftPoint();
|
|
originX1 = p.GetX();
|
|
originY1 = p.GetY();
|
|
p = hs.GetRightPoint();
|
|
originX2 = p.GetX();
|
|
originY2 = p.GetY();
|
|
initialized = true;
|
|
}
|
|
|
|
|
|
ExtendedHalfSegment& operator=(const ExtendedHalfSegment& hs){
|
|
if(hs.initialized){
|
|
HalfSegment::operator=(hs);
|
|
}
|
|
originX1 = hs.originX1;
|
|
originY1 = hs.originY1;
|
|
originX2 = hs.originX2;
|
|
originY2 = hs.originY2;
|
|
initialized = hs.initialized;
|
|
return *this;
|
|
}
|
|
|
|
void CopyFrom(const HalfSegment& hs){
|
|
HalfSegment::operator=(hs);
|
|
Point p = hs.GetLeftPoint();
|
|
originX1 = p.GetX();
|
|
originY1 = p.GetY();
|
|
p = hs.GetRightPoint();
|
|
originX2 = p.GetX();
|
|
originY2 = p.GetY();
|
|
initialized = true;
|
|
}
|
|
|
|
|
|
void setOrigin(const double x1, const double y1,
|
|
const double x2, const double y2){
|
|
originX1 = x1;
|
|
originX2 = x2;
|
|
originY1 = y1;
|
|
originY2 = y2;
|
|
}
|
|
|
|
double getOriginX1() const { return originX1; };
|
|
double getOriginX2() const { return originX2; };
|
|
double getOriginY1() const { return originY1; };
|
|
double getOriginY2() const { return originY2; };
|
|
|
|
bool isInitialized() const { return initialized; }
|
|
|
|
|
|
/*
|
|
~Print~
|
|
|
|
the usual Print function.
|
|
|
|
*/
|
|
std::ostream& Print(std::ostream& out) const{
|
|
out << "[Extended: {";
|
|
HalfSegment::Print(out);
|
|
out << "}; " ;
|
|
out << "initialized = " << initialized << ", "
|
|
<< "originX1 = " << originX1 << ", "
|
|
<< "originY1 = " << originY1 << ", "
|
|
<< "originX2 = " << originX2 << ", "
|
|
<< "originY2 = " << originY2
|
|
<< "]";
|
|
return out;
|
|
|
|
}
|
|
|
|
|
|
private:
|
|
|
|
double originX1;
|
|
double originX2;
|
|
double originY1;
|
|
double originY2;
|
|
bool initialized;
|
|
};
|
|
|
|
|
|
|
|
|
|
enum ownertype{none, first, second, both};
|
|
|
|
enum SetOperation{union_op, intersection_op, difference_op};
|
|
|
|
std::ostream& operator<<(std::ostream& o, const ownertype& owner);
|
|
|
|
|
|
const uint32_t LEFT = 1;
|
|
const uint32_t RIGHT = 2;
|
|
const uint32_t COMMON = 4;
|
|
|
|
/*
|
|
3.2 The Class ~AVLSegment~
|
|
|
|
This class is used for inserting into an avl tree during a plane sweep.
|
|
|
|
|
|
*/
|
|
|
|
class AVLSegment{
|
|
|
|
public:
|
|
|
|
/*
|
|
3.1.1 Constructors
|
|
|
|
~Standard Constructor~
|
|
|
|
*/
|
|
AVLSegment();
|
|
|
|
|
|
/*
|
|
~Constructor~
|
|
|
|
This constructor creates a new segment from the given HalfSegment.
|
|
As owner only __first__ and __second__ are the allowed values.
|
|
|
|
*/
|
|
|
|
AVLSegment(const ExtendedHalfSegment& hs, const ownertype owner);
|
|
|
|
|
|
/*
|
|
~Constructor~
|
|
|
|
Create a Segment only consisting of a single point.
|
|
|
|
*/
|
|
|
|
AVLSegment(const Point& p, const ownertype owner);
|
|
|
|
|
|
/*
|
|
~Copy Constructor~
|
|
|
|
*/
|
|
AVLSegment(const AVLSegment& src);
|
|
|
|
|
|
/*
|
|
3.2.1 Destructor
|
|
|
|
*/
|
|
~AVLSegment() {}
|
|
|
|
|
|
/*
|
|
3.3.1 Operators
|
|
|
|
*/
|
|
|
|
AVLSegment& operator=(const AVLSegment& src);
|
|
|
|
bool operator==(const AVLSegment& s) const;
|
|
|
|
bool operator<(const AVLSegment& s) const;
|
|
|
|
bool operator>(const AVLSegment& s) const;
|
|
|
|
/*
|
|
3.3.1 Further Needful Functions
|
|
|
|
~Print~
|
|
|
|
This function writes this segment to __out__.
|
|
|
|
*/
|
|
void Print(std::ostream& out)const;
|
|
|
|
/*
|
|
~CheckPoints~
|
|
|
|
This function checks whether the points (x1,y1) and (x2,y2) are
|
|
located on the segment defined by (orinigX1, originY1) and
|
|
(originY2, originY2). Furthermore, the distance from (x1,y1) to
|
|
(originX1,originY1) must be smaller than the distance to
|
|
(originX2, originY2).
|
|
|
|
*/
|
|
bool CheckPoints() const;
|
|
|
|
|
|
|
|
/*
|
|
3.5.1 Geometric Functions
|
|
|
|
~crosses~
|
|
|
|
Checks whether this segment and __s__ have an intersection point of their
|
|
interiors.
|
|
|
|
*/
|
|
bool crosses(const AVLSegment& s) const;
|
|
|
|
/*
|
|
~crosses~
|
|
|
|
This function checks whether the interiors of the related
|
|
segments are crossing. If this function returns true,
|
|
the parameters ~x~ and ~y~ are set to the intersection point.
|
|
|
|
*/
|
|
bool crosses(const AVLSegment& s,double& x, double& y) const;
|
|
|
|
|
|
/*
|
|
~commonPoint~
|
|
|
|
This function checks whether this AVLSegment and s have exactly one
|
|
common point. If so, the coordinates of this point are returned in
|
|
(x,y).
|
|
|
|
*/
|
|
bool commonPoint(const AVLSegment& s,double& x, double& y) const;
|
|
|
|
|
|
|
|
/*
|
|
~innerBoxContains~
|
|
|
|
chesks whether (x,y) is not an endpoint and within the
|
|
bounding box of this segment.
|
|
|
|
*/
|
|
bool innerBoxContains(const double x, const double y) const;
|
|
|
|
|
|
/*
|
|
~extends~
|
|
|
|
This function returns true, iff this segment is an extension of
|
|
the argument, i.e. if the right point of ~s~ is the left point of ~this~
|
|
and the slopes are equal.
|
|
|
|
*/
|
|
bool extends(const AVLSegment& s) const;
|
|
|
|
|
|
/*
|
|
~exactEqualsTo~
|
|
|
|
This function checks if s has the same geometry like this segment, i.e.
|
|
if both endpoints are equal.
|
|
|
|
*/
|
|
bool exactEqualsTo(const AVLSegment& s)const;
|
|
|
|
/*
|
|
~isVertical~
|
|
|
|
Checks whether this segment is vertical.
|
|
|
|
*/
|
|
|
|
bool isVertical() const;
|
|
|
|
|
|
/*
|
|
~isPoint~
|
|
|
|
Checks if this segment consists only of a single point.
|
|
|
|
*/
|
|
bool isPoint() const;
|
|
|
|
/*
|
|
~length~
|
|
|
|
Returns the length of this segment.
|
|
|
|
*/
|
|
double length() const;
|
|
|
|
|
|
|
|
/*
|
|
~InnerDisjoint~
|
|
|
|
This function checks whether this segment and s have at most a
|
|
common endpoint.
|
|
|
|
*/
|
|
|
|
bool innerDisjoint(const AVLSegment& s)const;
|
|
bool printInnerDisjoint(const AVLSegment& s)const;
|
|
|
|
/*
|
|
~Intersects~
|
|
|
|
This function checks whether this segment and ~s~ have at least a
|
|
common point.
|
|
|
|
*/
|
|
|
|
bool intersects(const AVLSegment& s)const;
|
|
|
|
|
|
/*
|
|
~overlaps~
|
|
|
|
Checks whether this segment and ~s~ have a common segment.
|
|
|
|
*/
|
|
bool overlaps(const AVLSegment& s) const;
|
|
|
|
/*
|
|
~ininterior~
|
|
|
|
This function checks whether the point defined by (x,y) is
|
|
part of the interior of this segment.
|
|
|
|
*/
|
|
bool ininterior(const double x,const double y)const;
|
|
|
|
|
|
/*
|
|
~contains~
|
|
|
|
Checks whether the point defined by (x,y) is located anywhere on this
|
|
segment.
|
|
|
|
*/
|
|
bool contains(const double x,const double y)const;
|
|
|
|
|
|
/*
|
|
3.6.1 Comparison
|
|
|
|
Compares this with s. The x intervals must overlap.
|
|
|
|
*/
|
|
|
|
int compareTo(const AVLSegment& s) const;
|
|
|
|
/*
|
|
~SetOwner~
|
|
|
|
This function changes the owner of this segment.
|
|
|
|
*/
|
|
void setOwner(const ownertype o);
|
|
|
|
|
|
/*
|
|
3.7.1 Some ~Get~ Functions
|
|
|
|
~getInsideAbove~
|
|
|
|
Returns the insideAbove value for such segments for which this value is unique,
|
|
e.g. for segments having owner __first__ or __second__.
|
|
|
|
*/
|
|
bool getInsideAbove() const;
|
|
|
|
|
|
inline double getX1() const { return x1; }
|
|
|
|
inline double getX2() const { return x2; }
|
|
|
|
inline double getY1() const { return y1; }
|
|
|
|
inline double getY2() const { return y2; }
|
|
|
|
inline ownertype getOwner() const { return owner; }
|
|
|
|
inline bool getInsideAbove_first() const { return insideAbove_first; }
|
|
|
|
inline bool getInsideAbove_second() const { return insideAbove_second; }
|
|
|
|
|
|
/*
|
|
3.8.1 Split Functions
|
|
|
|
~split~
|
|
|
|
This function splits two overlapping segments.
|
|
Preconditions:
|
|
|
|
1) this segment and ~s~ have to overlap.
|
|
|
|
2) the owner of this and ~s~ must be different
|
|
|
|
~left~, ~common~ and ~right~ will contain the
|
|
explicitely left part, a common part, and
|
|
an explecitely right part. The left and/or right part
|
|
my be empty. The existence can be checked using the return
|
|
value of this function. Let ret the return value. It holds:
|
|
|
|
__ret | LEFT__: the left part exists
|
|
|
|
__ret | COMMON__: the common part exist (always true)
|
|
|
|
__ret | RIGHT__: the right part exists
|
|
|
|
|
|
The constants LEFT, COMMON, and RIGHT have been defined
|
|
earlier.
|
|
|
|
*/
|
|
|
|
uint32_t split(const AVLSegment& s, AVLSegment& left, AVLSegment& common,
|
|
AVLSegment& right, const bool checkOwner = true) const;
|
|
|
|
|
|
/*
|
|
~splitAt~
|
|
|
|
This function divides a segment into two parts at the point
|
|
provided by (x, y). The point must be on the interior of this segment.
|
|
|
|
*/
|
|
|
|
void splitAt(const double x, const double y,
|
|
AVLSegment& left,
|
|
AVLSegment& right)const;
|
|
|
|
void splitAtRight(const double x, const double y,
|
|
AVLSegment& right)const;
|
|
|
|
/*
|
|
~splitCross~
|
|
|
|
Splits two crossing segments into the 4 corresponding parts.
|
|
Both segments have to cross each other.
|
|
|
|
*/
|
|
void splitCross(const AVLSegment& s, AVLSegment& left1, AVLSegment& right1,
|
|
AVLSegment& left2, AVLSegment& right2) const;
|
|
|
|
|
|
/*
|
|
3.9.1 Converting Functions
|
|
|
|
~ConvertToExtendedHs~
|
|
|
|
This functions creates a ~HalfSegment~ from this segment.
|
|
The owner must be __first__ or __second__.
|
|
|
|
*/
|
|
ExtendedHalfSegment convertToExtendedHs(const bool lpd,
|
|
const ownertype owner = both )const;
|
|
|
|
|
|
/*
|
|
3.10.1 Public Data Members
|
|
|
|
These members are not used in this class. So the user of
|
|
this class can change them without any problems within this
|
|
class itself.
|
|
|
|
*/
|
|
int con_below; // should be used as a coverage number
|
|
int con_above; // should be used as a coverage number
|
|
|
|
|
|
|
|
static bool isError(){ return x_error; }
|
|
|
|
static double getErrorValue() { return error_value; }
|
|
|
|
static void clearError(){
|
|
x_error = false;
|
|
}
|
|
|
|
|
|
/*
|
|
3.11.1 Private Part
|
|
|
|
Here the data members as well as some auxiliary functions are
|
|
collected.
|
|
|
|
*/
|
|
|
|
|
|
|
|
|
|
private:
|
|
/* data members */
|
|
double x1, x2, y1, y2; // the geometry of this segment
|
|
bool insideAbove_first;
|
|
bool insideAbove_second;
|
|
ownertype owner; // who is the owner of this segment
|
|
double originX1, originX2, originY1, originY2;
|
|
// this segments comes from
|
|
|
|
static bool x_error;
|
|
static double error_value;
|
|
|
|
public: // for debugging only
|
|
|
|
/*
|
|
~pointequal~
|
|
|
|
This function checks if the points defined by (x1, y1) and
|
|
(x2,y2) are equals using the ~AlmostEqual~ function.
|
|
|
|
*/
|
|
static bool pointEqual(const double x1, const double y1,
|
|
const double x2, const double y2);
|
|
|
|
|
|
/*
|
|
~pointSmaller~
|
|
|
|
This function checks if the point defined by (x1, y1) is
|
|
smaller than the point defined by (x2, y2).
|
|
|
|
*/
|
|
|
|
static bool pointSmaller(const double x1, const double y1,
|
|
const double x2, const double y2);
|
|
|
|
/*
|
|
~comparePoints~
|
|
|
|
*/
|
|
static int comparePoints(const double x1,const double y1,
|
|
const double x2,const double y2);
|
|
|
|
/*
|
|
~compareSlopes~
|
|
|
|
compares the slopes of __this__ and __s__. The slope of a vertical
|
|
segment is greater than all other slopes.
|
|
|
|
*/
|
|
int compareSlopes(const AVLSegment& s) const;
|
|
|
|
/*
|
|
~roundPoint~
|
|
|
|
whenever the point (x,y) is almostequal to an endpoint, its rounded
|
|
to that endpoint.
|
|
|
|
*/
|
|
|
|
void roundPoint(double& x , double& y) const;
|
|
|
|
|
|
|
|
/*
|
|
~XOverlaps~
|
|
|
|
Checks whether the x interval of this segment overlaps the
|
|
x interval of ~s~.
|
|
|
|
*/
|
|
|
|
public: // for debugging only
|
|
|
|
bool xOverlaps(const AVLSegment& s) const;
|
|
|
|
/*
|
|
~YOverlaps~
|
|
|
|
Checks whether the y interval of this segment overlaps the
|
|
y interval of ~s~.
|
|
|
|
*/
|
|
|
|
bool yOverlaps(const AVLSegment& s) const;
|
|
|
|
|
|
/*
|
|
~XContains~
|
|
|
|
Checks if the x coordinate provided by the parameter __x__ is contained
|
|
in the x interval of this segment;
|
|
|
|
*/
|
|
bool xContains(const double x) const;
|
|
|
|
/*
|
|
~yContains~
|
|
|
|
Checks if the y coordinate provided by the parameter __y__ is contained
|
|
in the y interval of this segment;
|
|
|
|
*/
|
|
bool yContains(const double y) const;
|
|
|
|
|
|
/*
|
|
~GetY~
|
|
|
|
Computes the y value for the specified __x__.
|
|
__x__ must be contained in the x-interval of this segment.
|
|
If the segment is vertical, the minimum y value of this
|
|
segment is returned.
|
|
|
|
*/
|
|
double getY(const double x) const;
|
|
};
|
|
|
|
std::ostream& operator<<(std::ostream& o, const AVLSegment& s);
|
|
|
|
} // end of namespace
|
|
|
|
|
|
std::ostream& operator<<(std::ostream& o,
|
|
const avlseg::ExtendedHalfSegment& hs);
|
|
|
|
|
|
|
|
#include "AVLSegmentImpl.h"
|
|
|
|
#endif
|
|
|