Cohen-Sutherland 2D line clipping algorithm

Question

Please, review the following implementation of Cohen-Sutherland line clipping algorithm (p-91):

Bits.cpp

class Bits
{
public:
    int bit1;
    int bit2;
    int bit3;
    int bit4;
public:
    Bits()
    {
        bit1 = bit2 = bit3 = bit4 = 0;
    }
    Bits(Bits & b)
    {
        *this = b;
    }
    Bits & operator & (Bits & b)
    {
        bit1 = bit1 & b.bit1;
        bit2 = bit2 & b.bit2;
        bit3 = bit3 & b.bit3;
        bit4 = bit4 & b.bit4;
        return *this;
    }
    Bits & operator | (Bits & b)
    {
        bit1 = bit1 | b.bit1;
        bit2 = bit2 | b.bit2;
        bit3 = bit3 | b.bit3;
        bit4 = bit4 | b.bit4;
        return *this;
    }
    Bits & operator = (Bits & b)
    {
        bit1 = b.bit1;
        bit2 = b.bit2;
        bit3 = b.bit3;
        bit4 = b.bit4;
        return *this;
    }
    bool operator == (Bits & b)
    {
        if(bit1 == b.bit1 && bit2 == b.bit2 && bit3 == b.bit3 && bit4 == b.bit4) return true;
        else return false;
    }
private:
    int Sign(double a)
    {
        if(a>0.01f) return 1;
        else return 0;
    }
    int GetBit1(double y, double yMax)
    {
        return Sign(y - yMax);
    }
    int GetBit2(double y, double yMin)
    {
        return Sign(yMin - y);
    }
    int GetBit3(double x, double xMax)
    {
        return Sign(x - xMax);
    }
    int GetBit4(double x, double xMin)
    {
        return Sign(xMin - x);
    }
public:
    void PointToBits(Point2d & clipMax, Point2d & clipMin, Point2d & pnt)
    {
        bit1 = GetBit1(pnt.y, clipMax.y);
        bit2 = GetBit2(pnt.y, clipMin.y);
        bit3 = GetBit3(pnt.x, clipMax.x);
        bit4 = GetBit4(pnt.x, clipMin.x);
    }
    bool IsClippingCandidate(Bits & bits)
    {
        Bits zeroBits;
        Bits andedBits = *this | bits;

        if(andedBits == zeroBits) return false;
        else return true;
    }
};

ClippingLine2d.cpp

#include "Line2d.h"
#include "Rectangle2d.h"
#include "Coordinates2d.h"

class ClippingLine2d
{
private:
    Rectangle2d rectangle;//clipping rectangle
    Line2d line;//line to be clipped
private:
    Bits startPointBits;//bits for start point of line
    Bits endPointsBits;//bits for end point of line
public:
    ClippingLine2d(Rectangle2d rect, Line2d line)
    {
        this->rectangle = rect;
        this->line = line;      
    }       
private:        
    Line2d GetClippedLine(std::vector<Line2d> clippingRegionLines, Line2d ln)
    {
        Point2d start = ln.GetStart();
        Point2d end = ln.GetEnd();

        if(startPointBits.bit4 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[3]);//DA
        }
        else if(startPointBits.bit3 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[1]);//BC
        }
        else if(startPointBits.bit2 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[0]);//AB
        }
        else if(startPointBits.bit1 == 1)
        {
            start = ln.GetIntersection(clippingRegionLines[2]);//CD
        }


        if(endPointsBits.bit4 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[3]);//DA
        }
        else if(endPointsBits.bit3 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[1]);//BC
        }
        else if(endPointsBits.bit2 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[0]);//AB
        }
        else if(endPointsBits.bit1 == 1)
        {
            end = ln.GetIntersection(clippingRegionLines[2]);//CD
        }

        return Line2d(start.Round(), end.Round());
    }
public:
    Line2d GetClippedLine()
    {
        Point2d min = rectangle.GetStart();
        Point2d max = rectangle.GetEnd();

        startPointBits.PointToBits(max, min, line.GetStart());
        endPointsBits.PointToBits(max, min, line.GetEnd());

        std::vector<Line2d> clippingRegionLines = rectangle.GetLines();

        Line2d tempLine = this->line;
        Bits start = startPointBits;
        Bits end = endPointsBits;

        while(start.IsClippingCandidate(end))
        {
            tempLine = GetClippedLine(clippingRegionLines, tempLine);

            Point2d startP = tempLine.GetStart();
            Point2d endP = tempLine.GetEnd();

            start.PointToBits(max, min, startP);
            end.PointToBits(max, min, endP);
        }

        return tempLine;
    }
};

int main()
{
    Line2d ln(Point2d(-120, -40), Point2d(270, 160)); 
    Rectangle2d rect(Point2d(20, 20), Point2d(160, 120));   

    Coordinates2d::ShowWindow("Cohen-Sutherland Line Clipping");
    Coordinates2d::Draw(ln, Red);
    Coordinates2d::Draw(rect, LightGreen);  

    ClippingLine2d clip(rect, ln);

    Line2d clippedLine = clip.GetClippedLine();

    Coordinates2d::Draw(clippedLine, Yellow);

    Coordinates2d::Wait();

    return 0;
}

The whole Visual C++ 2008 Express source code can be found here.

Answer 1

Extra Copying

ClippingLine2d(Rectangle2d rect, Line2d line)
{
    this->rectangle = rect;
    this->line = line;      
}

This will default-initialize rectangle and line, copy the input parameters into rect and line, and then copy them again into your member variables. You can save a copy and an extra initialization by direct initializing them from references to const:

ClippingLine2d(Rectangle2d const& rect, Line2d const& line)
: rectangle(rect)
, line(line)
{ }

The same is true of GetClippedLine. This:

Line2d GetClippedLine(std::vector<Line2d> clippingRegionLines, Line2d ln)

does an extra copy of the vector and the Line2d. This:

Line2d GetClippedLine(std::vector<Line2d> const& clippingRegionLines, Line2d const& ln)

does not.

Is this copy even necessary?

Bits start = startPointBits;
Bits end = endPointsBits;

Bits

Now that you posted the code, lots to say here. First, there is a standard C++ container to use for storing bits: std::bitset. Use it:

class Bits {
    std::bitset<4> bits;
    ...
};

That way you don't need to write the copy constructor/assignment operators. For the other other operators, they're wrong in two ways:

Bits & operator & (Bits & b)

That actually implements &=. It'd be pretty surprising to users if they did Bits c = a & b; and found out that a had changed too! Also there's no reason to restrict the input to non-const references. This should become:

Bits& operator&=(const Bits& b) {
    bits &= b.bits;
    return *this;
}

Bits operator&(const Bits& b) const {
    Bits lhs(*this);
    lhs &= b;
    return lhs;
}

And similarly for operator|.

For operator==, writing if (expr) return true else return false is an antipattern. It should just be return expr. Also, comparison should be const:

bool operator==(const Bits& rhs) const {
    return bits == rhs.bits;
}

Next the main methods. PointToBits makes zero sense as a member function. It should be a free function. Also you have 4 one-line functions that are all only used in one place. That makes it harder to read without adding any value. Just write them all inline:

Bits PointToBits(Point2d const& clipMax, Point2d const& clipMin, Point2d const& pnt)
{
    Bits b;
    static const double epsilon = 0.01;

    b[0] = pnt.y - clipMax.y > epsilon;
    b[1] = clipMin.y - pnt.y > epsilon;
    b[2] = pnt.x - clipMax.x > epsilon;
    b[3] = clipMin.x - pnt.x > epsilon;

    return b;
}

You'll have to add operator[] on Bits. It'll be easy.

Lastly, IsClippingCandidate(). We're not modifying this (or at least we wouldn't be if operator| was correct), so the function should be const. The variable is named andedBits - so presumably you meant to use & and not |. The argument should be taken by const reference. And we have the same antipattern about returning true or false. The whole thing can be reduced to:

bool IsClippingCandidate(Bits const& b) const {
    return (bits & b.bits).any(); // check if any of the bits specified
                                  // by 'b' are set
}

Repetition

In the overload of GetClippedLine that takes a vector, you have the same block twice. You can refactor that:

size_t bitsToIndex(Bits const& bits) {
    if (bits.bit4 == 1) {
        return 3; // DA
    }
    else if ( ... ) { ... }
    else {
        return -1;
    }
}

Point2d getIntersectionPoint(std::vector<line2d> const& clippingRegionLines,
                             Line2d const& ln, bool isStart)
{
    Bits& bits = isStart ? startPointBits : endPointBits;
    size_t idx = bitsToIndex(bits);

    if (idx != -1) {
        return ln.GetIntersection(clippingRegionLines[idx]);
    }
    else {
        return isStart ? ln.GetStart() : ln.GetEnd();
    }
}

Line2d GetClippedLine(std::vector<Line2d> const& clippingRegionLines, Line2d const& ln) {
    return Line2d(
        getIntersectionPoint(clippingRegionLines, ln, true).Round(),
        getIntersectionPoint(clippingRegionLines, ln, false).Round()
        );
}

That's a lot easier to grok. Could even avoid the awkward bool in there by introducing:

struct Start { };
struct End { };

Point2d get(Rectangle2d const& rect, Start ) { return rect.GetStart(); }
Point2d get(Rectangle2d const& rect, End ) { return rect.GetEnd(); }
// likewise for other cases

Then:

template <typename SIDE>
Point2d getIntersectionPoint(std::vector<line2d> const& clippingRegionLines,
                             Line2d const& ln, SIDE side)
{
    size_t idx = bitsToIndex(getBits(side));

    if (idx != -1) {
        return ln.GetIntersection(clippingRegionLines[idx]);
    }
    else {
        return get(ln, side);
    }
}

Line2d GetClippedLine(std::vector<Line2d> const& clippingRegionLines, Line2d const& ln) {
    return Line2d(
        getIntersectionPoint(clippingRegionLines, ln, Start()).Round(),
        getIntersectionPoint(clippingRegionLines, ln, End()).Round()
        );
}