I have searched throughout the internet and found no OO approach to implement Weiler-Atherton algorithm, so I implemented the following.
Please, help me to make the implementation more efficient and concise.
#include <iostream>
#include <vector>
#include <cmath>
//#include <graphics.h>
#include <algorithm>
using namespace std;
// Define Infinite (Using INT_MAX caused overflow problems
#define INF 10000.00l
//#define M_PI 3.14
#define SHOW(X) std::cout << # X " = " << (X) << std::endl;
// Converts degrees to radians.
#define degreesToRadians(angleDegrees) (angleDegrees * M_PI / 180.0)
// Converts radians to degrees.
#define radiansToDegrees(angleRadians) (angleRadians * 180.0 / M_PI)
#define INVALID -9999
class Point2d
{
void Copy(Point2d const & point)
{
x = point.x;
y = point.y;
}
public:
double x;
double y;
Point2d():x(0), y(0)
{}
Point2d(double x, double y):x(x), y(y)
{}
Point2d(Point2d const & pt)
{
Copy(pt);
}
Point2d& operator=(Point2d const & pt)
{
Copy(pt);
return *this;
}
Point2d operator-(Point2d const & pt)
{
return Point2d(x - pt.x, y-pt.y);
}
double GetDistance(Point2d const & pt)
{
double dx = pt.x - x;
double dy = pt.y - y;
return (double)sqrt(dx*dx + dy*dy);
}
static int GetOrientation(Point2d const&p, Point2d const&q, Point2d const&r)
{
double val = (q.y - p.y) * (r.x - q.x) -
(q.x - p.x) * (r.y - q.y);
if (val == 0) return 0; // colinear
return (val > 0)? 1: 2; // clock or counterclock wise
}
bool IsValid()
{
if(x!=INVALID && y!=INVALID)
{
return true;
}
else return false;
}
bool operator==(const Point2d & point)
{
return (x == point.x)&&(y == point.y);
}
bool operator!=(const Point2d & point)
{
return (x != point.x)&&(y != point.y);
}
void Show()
{
std::cout<<"("<<x<<","<<y<<")\n";
}
};
template <class T>
class Collection
{
private:
std::vector<T> collection;
void Copy(Collection const& pc)
{
std::vector<T> col = pc.GetList();
this->Add(col);
}
public:
Collection(){}
Collection(Collection const& pc)
{
Copy(pc);
}
Collection & operator=(Collection const & pc)
{
Copy(pc);
return *this;
}
void Add(double x, double y)
{
collection.push_back(Point2d(x,y));
}
void Add(T const& point)
{
collection.push_back(point);
}
void Add(std::vector<T> const& points)
{
for(size_t i=0 ; i<points.size() ; i++)
{
this->Add(points[i]);
}
}
int size()
{
return collection.size();
}
T & operator[](int index)
{
return collection[index];
}
T operator[](int index) const//reader
{
return collection[index];
}
bool IsExistent(T & item)
{
if (std::find(collection.begin(), collection.end(), item) != collection.end()) return true;
else false;
}
int GetIndex(T & item)
{
return find(collection.begin(), collection.end(), item) - collection.begin();
}
std::vector<T> GetList() const
{
return collection;
}
T Remove(int index)
{
Point2d pt = collection[index];
collection.erase(collection.begin() + index);
return pt;
}
void clear()
{
collection.clear();
}
void Show()
{
for(size_t i=0 ; i<collection.size() ; i++)
{
collection[i].Show();
}
}
};
class Vector2d
{
private:
Point2d point;
public:
Vector2d()
{
}
Vector2d(double x, double y)
{
point = Point2d(x,y);
}
Vector2d(Point2d const& point): point(point)
{
}
void Set(double x, double y)
{
point = Point2d(x,y);
}
void Set(Point2d const& pt)
{
point = pt;
}
double GetMagnitude(void)
{
return (double)sqrt((double)(point.x*point.x + point.y*point.y));
}
Point2d Component(void)
{
return Point2d();
}
Vector2d Normal();
Vector2d & Add(Vector2d const& rhs)
{
point.x = point.x + rhs.point.x;
point.y = point.y + rhs.point.y;
return *this;
}
Vector2d & Subtract(Vector2d const& rhs)
{
point.x = point.x - rhs.point.x;
point.y = point.y - rhs.point.y;
return *this;
}
Vector2d & Multiply(double scalar)
{
point.x = point.x * scalar;
point.y = point.y * scalar;
return *this;
}
double DotProduct(Vector2d const& rhs)
{
return (point.x*rhs.point.x) + (point.y*rhs.point.y);
}
Vector2d & CrossProduct(Vector2d rhs);
double GetDirectionAngle()
{
return radiansToDegrees(atan(point.y/point.x));
}
double GetAngleBetween(Vector2d & v)
{
double rad = this->DotProduct(v)/(this->GetMagnitude()* v.GetMagnitude());
return radiansToDegrees(acos(rad));
}
bool IsInbound(Vector2d const& anotherVect)
{
return false;
}
bool IsOutbound(Vector2d const& anotherVect)
{
return false;
}
};
#pragma region line2d
class Line2d
{
Point2d start;
Point2d end;
private:
void Copy(Line2d const& line)
{
start = line.start;
end = line.end;
}
public:
Vector2d GetVector2d()
{
return Vector2d(end - start);
}
Line2d(){}
Line2d(double x1, double y1, double x2, double y2)
{
start = Point2d(x1, y1);
end = Point2d(x2, y2);
}
Line2d(Point2d const& start, Point2d const& end):start(start), end(end)
{
}
Line2d(Line2d const& line)
{
Copy(line);
}
Line2d & operator=(Line2d const& line)
{
Copy(line);
return *this;
}
void SetStart(Point2d const& pt)
{
start = pt;
}
void SetEnd(Point2d const& pt)
{
end = pt;
}
Point2d & GetStart(){return start;}
Point2d & GetEnd(){return end;}
//Boundary test
/*bool OnSegment(Point2d q)
{
Point2d p = start;
Point2d r = end;
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;
return false;
}*/
static bool IsOnSegment(Point2d const& start, Point2d const&end, Point2d const&q)
{
if (q.x <= max(start.x, end.x) && q.x >= min(start.x, end.x) &&
q.y <= max(start.y, end.y) && q.y >= min(start.y, end.y))
return true;
return false;
}
bool IsOnLine(Point2d const& point)
{
double dx = end.x - start.x;
double dy = end.y - start.y;
double lhs = (point.x - start.x) * dy;
double rhs = (point.y - start.y) * dx;
return (lhs == rhs);
}
bool IsOnLine(double x, double y)
{
return IsOnLine(Point2d(x, y));
}
bool IsOnSegment(double x, double y)
{
Point2d p = start;
Point2d q(x, y);
Point2d r = end;
if((p.GetDistance(q)+q.GetDistance(r)) == p.GetDistance(r)) return true;
else return false;
}
double GetSlope()
{
double dx = end.x - start.x;
double dy = end.y - start.y;
double m = dy/dx;
return m;
}
bool IsIntersectableLine(Line2d const& ln)
{
double dx1 = end.x - start.x; double dy1 = end.y - start.y;
double dx2 = ln.end.x - ln.start.x; double dy2 = ln.end.y - ln.start.y;
return (dy1 * dx2 != dy2 * dx1);
}
// The function that returns true if line segment 'p1q1'
// and 'p2q2' intersect.
bool IsIntersectableSegment(Line2d &line2)
{
Line2d line1(start, end);
Point2d p1 = line1.GetStart();
Point2d q1=line1.GetEnd();
Point2d p2=line2.GetStart();
Point2d q2=line2.GetEnd();
// Find the four orientations needed for general and
// special cases
int o1 = Point2d::GetOrientation(p1, q1, p2);
int o2 = Point2d::GetOrientation(p1, q1, q2);
int o3 = Point2d::GetOrientation(p2, q2, p1);
int o4 = Point2d::GetOrientation(p2, q2, q1);
// General case
if (o1 != o2 && o3 != o4)
return true;
// Special Cases
// p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 && Line2d::IsOnSegment(p1, q1, p2)) return true;
// p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 && Line2d::IsOnSegment(p1, q1, q2)) return true;
// p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 && Line2d::IsOnSegment(p2, q2, p1)) return true;
// p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 && Line2d::IsOnSegment(p2, q2, q1)) return true;
return false; // Doesn't fall in any of the above cases
}
Point2d Intersection(Line2d & line)
{
double x1 = start.x;
double y1 = start.y;
double x2 = end.x;
double y2=end.y;
double x3 = line.start.x;
double y3 = line.start.y;
double x4 = line.end.x;
double y4 = line.end.y;
double d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4);
if (d == 0) return Point2d(INVALID, INVALID);
double xi = ((x3-x4)*(x1*y2-y1*x2)-(x1-x2)*(x3*y4-y3*x4))/d;
double yi = ((y3-y4)*(x1*y2-y1*x2)-(y1-y2)*(x3*y4-y3*x4))/d;
Point2d p(xi,yi);
if (xi < min(x1,x2) || xi > max(x1,x2)) return Point2d(INVALID, INVALID);
if (xi < min(x3,x4) || xi > max(x3,x4)) return Point2d(INVALID, INVALID);
return p;
}
};
#pragma endregion
#pragma region polygon
class Polygon2d
{
private:
Collection<Point2d> polygon;
void Copy(Polygon2d const& poly)
{
polygon.clear();
Collection<Point2d> pol = poly.GetVertices();
this->Add(pol);
}
public:
Polygon2d(){}
Polygon2d(Polygon2d const& poly)
{
Copy(poly);
}
Polygon2d & operator=(Polygon2d const& poly)
{
Copy(poly);
return *this;
}
void Add(double x, double y)
{
polygon.Add(Point2d(x,y));
}
void Add(Point2d & point)
{
polygon.Add(point);
}
void Add(std::vector<Point2d> & points)
{
for(size_t i=0 ; i<points.size() ; i++)
{
this->Add(points[i]);
}
}
void Add(Collection<Point2d> & points)
{
for(int i=0 ; i<points.size() ; i++)
{
this->Add(points[i]);
}
}
int size()
{
return polygon.size();
}
Point2d & operator[](int index)
{
return polygon[index];
}
Point2d operator[](int index) const//reader
{
return polygon[index];
}
bool IsExistentIn(Point2d & item)
{
polygon.IsExistent(item);
}
int GetIndex(Point2d & item)
{
return polygon.GetIndex(item);
}
Collection<Point2d> GetVertices()const
{
return polygon;
}
// Returns true if the point p lies inside the polygon[] with n vertices
bool IsInside(Point2d const&p)
{
int n = polygon.size();
// There must be at least 3 vertices in polygon[]
if (n < 3) return false;
// Create a point for line segment from p to infinite
Point2d extreme(INF, p.y);
// Count intersections of the above line with sides of polygon
int count = 0, i = 0;
do
{
int next = (i+1)%n;
Line2d line1(polygon[i], polygon[next]);
Line2d line2(p, extreme);
// Check if the line segment from 'p' to 'extreme' intersects
// with the line segment from 'polygon[i]' to 'polygon[next]'
if (line1.IsIntersectableSegment(line2))
{
// If the point 'p' is colinear with line segment 'i-next',
// then check if it lies on segment. If it lies, return true,
// otherwise false
if (Point2d::GetOrientation(polygon[i], p, polygon[next]) == 0)
{
return Line2d::IsOnSegment(polygon[i], polygon[next], p);
}
count++;
}
i = next;
}
while (i != 0);
// Return true if count is odd, false otherwise
return count&1; // Same as (count%2 == 1)
}
void Show()
{
polygon.Show();
std::cout<<"\n";
}
};
#pragma endregion
#pragma region Graphics System
//typedef enum Color
//{
// Black=0,
// Blue=1,
// Green=2,
// Cyan=3,
// Red=4,
// Magenta=5,
// Brown=6,
// LightGray=7,
// DarkGray=8,
// LightBlue=9,
// LightGreen=10,
// LightCyan=11,
// LightRed=12,
// LightMagenta=13,
// Yellow=14,
// White=15
//}Color;
//
//typedef enum DrawType {Thin, Thick} DrawType;
//
//#define DIST 20
//
//class Coordinates2d
//{
//private:
// static Point2d origin;
//
//public:
// static void Wait()
// {
// while (!kbhit())
// {
// delay(200);
// }
// }
// static void ShowWindow(char str[])
// {
// initwindow(1350, 680, str);
// origin.x = (getmaxx()/2)-(getmaxx()/2)%DIST;
// origin.y = (getmaxy()/2)-(getmaxy()/2)%DIST;
// setcolor(GREEN);
// for(int j=0 ; j<getmaxy() ; j+=DIST)
// {
// line(0,j, getmaxx(), j);
// }
//
// for(int i=0 ; i<getmaxx() ; i+=DIST)
// {
// line(i,0, i, getmaxy());
// }
//
// setcolor(BLUE);
// //vertical thick line
// line((int)origin.x-1, 0, (int)origin.x-1, getmaxy());
// line((int)origin.x+1, 0, (int)origin.x+1, getmaxy());
// //horizontal thick line
// line(0, (int)origin.y-1, getmaxx(), (int)origin.y-1);
// line(0, (int)origin.y+1, getmaxx(), (int)origin.y+1);
// }
// static void Draw(Line2d & ln, Color col=LightRed)
// {
// setcolor(col);
// line((int)(ln.GetStart().x) + (int)origin.x, (int)(origin.y - ln.GetStart().y), (int)(ln.GetEnd().x + origin.x), (int)(origin.y - ln.GetEnd().y));
// }
// static void Draw(Point2d & ln, Color col=Yellow, DrawType drawType=Thick)
// {
// setcolor(col);
// putpixel((int)(ln.x + origin.x), (int)(origin.y - ln.y), YELLOW);
// if(drawType == Thick)
// {
// circle((int)(ln.x + origin.x), (int)(origin.y - ln.y), 2);
// }
// }
// static void Draw(Polygon2d & polygon, Color col=LightGreen)
// {
// for(int i=0 ; i<polygon.size() ; i++)
// {
// Line2d line(polygon[i], polygon[(i+1)%polygon.size()]);
// Coordinates2d::Draw(line, col);
// }
// }
// static Color GetRandomColor()
// {
// Color outPut = (Color)(Black + (rand() % (int)(White - Black + 1)));
//
// return outPut;
// }
// static void Draw(std::vector<Point2d> verticesList, DrawType drawType=Thick, Color color=LightCyan)
// {
// for(size_t i=0 ; i<verticesList.size() ; i++)
// {
// Coordinates2d::Draw(verticesList[i], color, drawType);
// }
// }
//};
//
//Point2d Coordinates2d::origin;
#pragma endregion
#pragma region Point2dWithInfo
struct Point2dWithInfo
{
Point2d Point;
bool Entering;
bool IsIntersection;
Point2dWithInfo(){}
Point2dWithInfo(Point2d & point, bool enter=false, bool intersection=false):
Point(point), Entering(enter), IsIntersection(intersection) {}
void Copy(Point2dWithInfo const & pt)
{
Point = pt.Point;
Entering = pt.Entering;
IsIntersection = pt.IsIntersection;
}
Point2dWithInfo(Point2dWithInfo const & pt)
{
Copy(pt);
}
Point2dWithInfo & operator=(Point2dWithInfo const & pt)
{
Copy(pt);
return *this;
}
bool operator==( Point2dWithInfo const & point)
{
return (Point == point.Point) && (Entering == point.Entering) && (IsIntersection == point.IsIntersection);
}
bool operator!=( Point2dWithInfo const & point)
{
return (Point != point.Point) && (Entering != point.Entering) && (IsIntersection != point.IsIntersection);
}
void Show()
{
Point.Show();
}
};
#pragma endregion
class WeilerAthertonClipping
{
Polygon2d clipping;
Polygon2d candidate;
public:
void Show()
{
clipping.Show();
candidate.Show();
}
WeilerAthertonClipping(){}
void SetClippingArea(Polygon2d & clipper)
{
clipping = clipper;
}
void SetCandidatePolygon(Polygon2d & can)
{
candidate = can;
}
void ShowIntersectionList()
{
intersectionList.Show();
}
private:
Collection<Point2dWithInfo> intersectionList;
public:
Collection<Point2dWithInfo> CollectCandidateVertices()
{
intersectionList.clear();
Collection<Point2dWithInfo> candidateVertexListWithIntersection;
for(int i=0 ; i<candidate.size() ; i++)
{
Point2d start = candidate[i];
Point2d end = candidate[(i + 1) % candidate.size()];
Line2d candidateEdge(start, end);
candidateVertexListWithIntersection.Add(Point2dWithInfo(start));
for(int j=0 ; j<clipping.size() ; j++)
{
Line2d clippingEdge(clipping[j], clipping[(j + 1) % clipping.size()]);
bool startInside = clipping.IsInside(start);
bool endInside = clipping.IsInside(end);
if(startInside != endInside)
{
Point2d pt = clippingEdge.Intersection(candidateEdge);
if(pt.IsValid())
{
intersectionList.Add(Point2dWithInfo(pt,endInside, true));
candidateVertexListWithIntersection.Add(Point2dWithInfo(pt,endInside, true));
}
}
}
}
char ch = 'a';
return candidateVertexListWithIntersection;
}
Collection<Point2d> CollectClipVertices()
{
intersectionList.clear();
Collection<Point2d> clippingVertexListWithIntersection;
for(int i=0 ; i<clipping.size() ; i++)
{
Point2d start = clipping[i];
Point2d end = clipping[(i + 1) % clipping.size()];
Line2d clippingEdge(start, end);
clippingVertexListWithIntersection.Add(start);
for(int j=0 ; j<candidate.size() ; j++)
{
Point2d startCl = candidate[j];
Point2d endCl = candidate[(j + 1) % candidate.size()];
Line2d candidateEdge(startCl, endCl);
bool startInside = clipping.IsInside(startCl);
bool endInside = clipping.IsInside(endCl);
if(startInside != endInside)
{
Point2d pt = candidateEdge.Intersection(clippingEdge);
if(pt.IsValid())
{
clippingVertexListWithIntersection.Add(pt);
if(endInside==true)
{
intersectionList.Add(Point2dWithInfo(pt, true));
}
else
{
intersectionList.Add(Point2dWithInfo(pt));
}
}
}
}
}
return clippingVertexListWithIntersection;
}
public:
Collection<Polygon2d> GetClippedPolygon()
{
Collection<Polygon2d> polygons;
//Collection clippingList = this->CollectClipVertices();
Collection<Point2dWithInfo> candidateListx = this->CollectCandidateVertices();
for(int i=0 ; i<intersectionList.size() ; i++)
{
Polygon2d tempPolygon;
Point2dWithInfo intPoint= intersectionList[i];
if(intPoint.Entering)
{
int index = candidateListx.GetIndex(intPoint);
Point2dWithInfo ppt = candidateListx[index];
do
{
tempPolygon.Add(ppt.Point);
ppt = candidateListx[++index];
}
while(!ppt.IsIntersection && !ppt.Entering);
tempPolygon.Add(ppt.Point);
tempPolygon.Add(intPoint.Point);
polygons.Add(tempPolygon);
}
}
return polygons;
}
};
int main()
{
Polygon2d clipping;
clipping.Add(160,20);
clipping.Add(160,220);
clipping.Add(340,220);
clipping.Add(340,20);
//clipping.Show();
Polygon2d candidate;
candidate.Add(20,40);
candidate.Add(20,180);
candidate.Add(240,180);
candidate.Add(60,100);
candidate.Add(240,40);
//candidate.Show();
WeilerAthertonClipping waClip;
waClip.SetClippingArea(clipping);
waClip.SetCandidatePolygon(candidate);
//waClip.Show();
Collection<Polygon2d> po = waClip.GetClippedPolygon();
po.Show();
return 0;
}
EDIT: This code has a bug. If the tip of the iceberg is outside the clipping region, it doesn't work.