Weiler-Atherton polygon-clipping algorithm in C++

Question

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.

Answer 1

I will focus on the C++ parts, not necesarily the algorithm.

using namespace std;

Don't! In header files this should never appear, and in C++ files (if you must use it) use it only in local namespaces. When you add it at the top of the file like you did, it imports every symbol in std:: locally (and prevents your code - or the code of any future mantainer's) to avoid certain names.

The defines for INF and INVALID should be declared using const or constexpr and the defines for SHOW, degreesToRadians and radiansToDegrees should be declared as functions.

Consider using C++-style casts (static_cast and reinterpret_cast are what you need). The C-style casts are unsafe, they introduce hard-to-find points in code that are inflexible to change and they are impossible to parse unless you parse/compile the entire code.

Consider writing GetOrientation like this:

enum class Orientation { clockwise, counterclockwise };
static Orientation GetOrientation(Point2d const&p, Point2d const&q, Point2d const&r);

You have a comment on the return value of GetOrientation specifying what the values (1 and 2) mean. Using the enum class Orientation as a return type removes the need of the comment and keeps the code mode clear in intent (than the function returning int).

IsValid returns a boolean, so the code could be written like this:

bool IsValid()
{
    return x!=INVALID && y!=INVALID;
}

You can write the Point2D::operator== as:

bool operator==(const Point2d & point) const
//                                     ^^^^^ <- notice the const
{
    return std::tie(x, y) == std::tie(point.x, point.y);
//  and tie the values in a tuple, performing single comparison
}

You can write operator!= to return !(*this == point);. This has two advantages:

• if you want to change what it means for points to be equal and different, you only change one operator (this is much better for future maintenance)

• you make it clear to whoever is reading the code that the two operations are opposite.

Collection<Point2D> should be called PointsCollection (or similar) and not be defined as a template.

You define it as a template, but it is specifically implemented for Point2D instances in various places.

Even better, you can discard the class completely and use a std::vector<Point2D> The underlying std::vector already implements all the functionality you added here.

Consider splitting your code into multiple files (instead of using #pragma region for separating code areas).

Also consider splitting your classes into declaration and definition.

Your pattern of copy construction and assignment operator using a private Copy function should probably be re-written using the copy&swap idiom (it is less code to write/maintain, exception safe and minimalistic).

Answer 2

So, now that you have had a bit of advice concerning the C++ and design stuff, let's talk about the math. There is of course less to say, but there are still a few things to be noted:

• c++11 Instead of rolling your own algorithm to implement GetDistance, you could use std::hypot instead. Be careful though: it uses a special algorithm to avoid intermediate overflows and undeflows that might occur. That means that, while being safer, the algorithm might also be a bit slower.

  double GetDistance(Point2d const & pt)
  {
      double dx = pt.x - x;
      double dy = pt.y - y;
  
      return std::hypot(dx, dy);
  }
  

  Same remark for Vector2d::GetMagnitude.

• Instead of std::atan(point.y / point.x), you can use std::atan2 which does exactly that while always properly handling the job:

  std::atan2(point.y, point.x)
  

• By the way, when comparing distances, you can generally compare the squared distances instead, which often save you from computing a somewhat expensive square root:

  bool IsOnSegment(double x, double y)
  {
      Point2d p = start;
      Point2d q(x, y);
      Point2d r = end;
  
      double a = p.GetDistance(q) + q.GetDistance(r);
      double b = p.GetSquaredDistance(r);
      return a*a == b*b;
  }
  

  This function uses an hypothetical Point2d::GetSquaredDistance method that would be defined as:

  double GetSquaredDistance(Point2d const & pt)
  {
      double dx = pt.x - x;
      double dy = pt.y - y;
  
      return dx*dx + dy*dy;
  }
  

• Vector2d::GetAngleBetween doesn't check whether any Vector2d::GetMagnitude call returns \$0\$ before performing the division. That means that if either of the vector has an underlying Point2d with coordinates \$(0, 0)\$, it will perform a division by \$0\$ which is undefined behavior (generally speaking, it will segfault).

• In Polygon2d::IsInside, you are automatically returning false if there are less than three vertices. While I understand the reason, would it be correct for a point to be « inside » the polygon if it is on one of the vertices?

Answer 3

I concur with most of what's been said above. Your code is pretty clean and easy to read, which is great!

Object-orientedness

You mention that you haven't found an OO approach to clipping. I think the reason for that is that it doesn't make a lot of sense to have a clipping class. Clipping is an action, not an object. In fact, there's really only 1 method that isn't a setup method in your clipping class - GetClippedPolygon(). To me that's a clue that this design isn't the right one.

In most drawing systems, there is either a global clipping mask, or an individual object has a mask associated with it. Whichever you choose is up to you. In my opinion it would make more sense to have a stand-alone function that takes a clipping polygon and a polygon to draw and returns the clipped collection of polygons. In other words, just make GetClippedPolygon() a stand-alone function. I'd probably do something like:

Collection<Polygon2D> ClipPolygonToPolygon(const Polygon2D& drawPoly, const Polygon2D& clipPoly);

Internally, it would call the setup functions for collecting the candidate and clip vertices, then do the rest of its calculations.

Encapsulation

I notice almost all of your classes have their instance variables declared as public. I think that's a mistake. While it removes the need to write accessors, it allows any other part of the code to modify it. That can make it very hard to track down when an instance is getting modified and you don't know where. If you have setX() method, then you can add a breakpoint to it and see who the caller is and where it's being changed. It can also help when you decide you need to use these classes in a multithreaded environment and need to add a mutex to protect access to the instance variables.

Overclassification

I notice that you've made 2 different classes for a 2D point and a 2D vector. This is a double-edged sword. They are used differently, but you will frequently need to turn one into the other or do math on both at the same time. This makes it inconvenient as you write more complex code. You start needing more conversion routines, and calculations become increasingly difficult to deal with.