3
\$\begingroup\$

I'm working on class Striped_polyline which represents a closed poly-line filled with equidistant horizontal lines1:

stripedpoly.cpp:

#include <iostream> 
#include <vector>
#include <algorithm>
#include "Graph.h"
#include "Simple_window.h"
#include "stripedpoly.h"

int main(){
    Point tl(x_max()/2,0);
    int width = 700;
    int height = 700;
    string label = "Striped Closed poly-line";
    Simple_window sw(tl, width, height, label);
    try{ 
        // generate points for the poly-line
        vector<Point> polyPoints;
        generatePoints(polyPoints);
        // create a poly-line
        Striped_closed_polyline scp;
        for (auto it = polyPoints.begin(); it != polyPoints.end(); ++it) scp.add(*it); 
        scp.set_spacing(5);
        sw.attach(scp);
        sw.wait_for_button();
    }catch(exception& e){
        cerr << e.what() << endl;
        getchar();
    }catch(...){
        cerr <<"Default exception!"<< endl;
        getchar();
    }
}

stripedpoly.h:

// Helper functions
static void generatePoints(vector<Point>& p){
    p.push_back(Point(50,50));
    p.push_back(Point(200,50));
    p.push_back(Point(250,100));
    p.push_back(Point(200,200));
    p.push_back(Point(100,225));
    p.push_back(Point(50,200));
    p.push_back(Point(25,100));
}
// compare function for sorting by the x-coordinates of a Point
struct XLessThan{
    inline bool operator()(Point& p1, Point& p2){ return (p1.x < p2.x); }
};  
// compare function for sorting by the y-coordinates of a Point
struct YLessThan{
    inline bool operator()(Point& p1, Point& p2){ return (p1.y < p2.y); }
};  
// class Edge: representing lines segments of the poly-line
struct Edge{
    Edge(Point p0, Point p1) : start(p0), end(p1){ 
        if (p0.x == p1.x && p0.y == p1.y) throw std::invalid_argument("Edge: Identical points!");
        if (p0.y > p1.y) std::swap(start, end);
        yMin = start.y;
        yMax = end.y;
    } 
    bool operator<(const Edge& e){ return (yMax < e.yMax); }
    // data members 
Point start;
Point end;
int yMin;
int yMax;
};
// intesection between two lines (8 coordinates)
Point intersectPoint(float p0_x, float p0_y, float p1_x, float p1_y, float p2_x, float p2_y, float p3_x, float p3_y){
    float s1_x, s1_y, s2_x, s2_y;
    s1_x = p1_x - p0_x;     s1_y = p1_y - p0_y;
    s2_x = p3_x - p2_x;     s2_y = p3_y - p2_y;
    float s, t;
    s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);
    t = ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y);
    if (s >= 0 && s <= 1 && t >= 0 && t <= 1){
        int x = p0_x + (t * s1_x); 
        int y = p0_y + (t * s1_y);
        return Point(x, y);
    }
    int noIntersection = -1;
    return Point(noIntersection, noIntersection);  
}
// overloaded for Points (4 points)
Point  intersectPoint(Point p0, Point p1, Point p2, Point p3){
    return  intersectPoint(p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y);
}
// overloaded for Edges (2 edges)
Point intersectPoint(Edge& e1, Edge& e2){
    return intersectPoint(e1.start, e1.end, e2.start, e2.end);
}
// Class Striped_closed_polyline
class Striped_closed_polyline: public Closed_polyline{
public:
    void set_spacing(int s) { spacing = s; }
    void draw_lines() const;    
private:
    static int spacing;
};
// default value of the spacing between the horizontal lines
int Striped_closed_polyline::spacing = 10;
// member function
void Striped_closed_polyline::draw_lines() const{
    Closed_polyline::draw_lines();
    // create edges using the points stored in the base class 
    vector<Edge> polyEdges;
    Point first = point(0);
    Point last = point(number_of_points()-1);
    polyEdges.push_back(Edge(last, first));
    for (size_t i = 1; i < number_of_points(); ++i) polyEdges.push_back(Edge(point(i-1), point(i)));
    // sort by increasing yMax (ordinate of the end point)
    std::sort(polyEdges.begin(), polyEdges.end());
    // find Xmin and Xmax of the poly-line (end coordinates of the horizontal scan-line)
    vector<Point> polyPoints2;
    for (size_t i = 0; i < number_of_points(); ++i) polyPoints2.push_back(point(i)); 
    sort(polyPoints2.begin(), polyPoints2.end(), XLessThan());
    int polyXmin =  polyPoints2[0].x;
    int polyXmax =  polyPoints2[polyPoints2.size()-1].x;
    // find intersection points between the horizontal line and the poly-line
    vector<Point> intersections;
    for (size_t i = 0; i < polyEdges.size(); ++i){
        for (size_t j = polyEdges[i].yMin; j < polyEdges[i].yMax; j += spacing){
            Edge horizontal(Point(polyXmin, j), Point(polyXmax, j));
            // check if polyEdge not horizontal
            if (polyEdges[i].start.y != polyEdges[i].end.y){
                Point s = intersectPoint(polyEdges[i], horizontal);
                // check if point is not a valid intersection
                int noIntersection = -1;
                if (s.x != noIntersection && s.y != noIntersection) intersections.push_back(s);
            }
        }
    }
    // sort intersection points by their y-coordinate (form a sequence of pair-points making horizontal lines)
    std::sort(intersections.begin(), intersections.end(), YLessThan());
    // draw scan-lines
    if (color().visibility()){ 
        for (size_t i = 1; i < intersections.size(); i += 2){
        // test if points inside the poly-line
        fl_line(intersections[i-1].x, intersections[i-1].y, intersections[i].x, intersections[i].y);    
        }
    }   
}

Result:

enter image description here

Is there something else that can be done for optimization? Is there a better way to fill a closed poly-line with horizontal lines?

Edit:

Following the valuable suggestions, the following changes have been made:

1.Points are generated using:

static void generatePoints(Striped_closed_polyline* s){
    s->add(Point(50,50));
    s->add(Point(200,50));
    s->add(Point(250,100));
    s->add(Point(200,200));
    s->add(Point(100,225));
    s->add(Point(50,200));
    s->add(Point(25,100));
} 

2.Intersection points are found using (to be integrated as a class Edge member function):

// does two lines (p1,p2) and (p3,p4) intersect?
// if se return the distance of the intersect point as distances from p1
inline pair<double,double> line_intersect(Point p1, Point p2, Point p3, Point p4, bool& parallel){
    double x1 = p1.x;
    double x2 = p2.x;
    double x3 = p3.x;
    double x4 = p4.x;
    double y1 = p1.y;
    double y2 = p2.y;
    double y3 = p3.y;
    double y4 = p4.y;

    double denom = ((y4 - y3)*(x2-x1) - (x4-x3)*(y2-y1));
    if (denom == 0){
        parallel= true;
        return pair<double,double>(0,0);
    }
    parallel = false;
    return pair<double,double>( ((x4-x3)*(y1-y3) - (y4-y3)*(x1-x3))/denom,
                            ((x2-x1)*(y1-y3) - (y2-y1)*(x1-x3))/denom);
}

// intersection between two line segments
// returns true if the two segments intersect,
// in which case intersection is set to the point of intersection
bool line_segment_intersect(Point p1, Point p2, Point p3, Point p4, Point& intersection){
    bool parallel;
    pair<double,double> u = line_intersect(p1,p2,p3,p4,parallel);
    if (parallel || u.first < 0 || u.first > 1 || u.second < 0 || u.second > 1) return false;
    intersection.x = p1.x + u.first*(p2.x - p1.x);
    intersection.y = p1.y + u.first*(p2.y - p1.y);
    return true;
}
// overloaded for edge
bool edge_intersect(Edge e1, Edge e2, Point& intersection){
     return line_segment_intersect(e1.start, e1.end, e2.start, e2.end, intersection);
}

3.Xmin and Xmax are found using:

int polyXmin =  1000;
int polyXmax =  -1;
for (size_t i = 0; i < number_of_points(); ++i){
    if(point(i).x < polyXmin) polyXmin = point(i).x; 
    if(point(i).x > polyXmax) polyXmax = point(i).x; 
}

Finally, the result is:

enter image description here


1. Chapter 14 Exercise 7 Bjarne Stroustrup "C++ Programming: Principles and Practice".

2. Additional files for compilation are here. The FLTK could be found here.

\$\endgroup\$
  • 1
    \$\begingroup\$ What kind of optimizations are you looking for. Performance? Clarity? Is C++11/14 an option for you? \$\endgroup\$ – Zulan Oct 13 '15 at 19:17
  • \$\begingroup\$ Probably clarity and simplicity. C++11 is an option. \$\endgroup\$ – Ziezi Oct 13 '15 at 20:15
7
\$\begingroup\$

Don't use using namespace std;. Seriously

The lack of std:: implies you have using namespace std; in a header somewhere. This is bad for the following reasons:

  • Having it localized to one translation unit is one thing, but putting it into a header propogates it to whoever chooses to include your header. This is a Bad Thing™ in of itself.

  • Many trivial programs will not suffer from name conflicts; but a program that deals with shapes and drawing increases the chances you'll have a name conflict like distance or vector.

  • Using a third party library (if you are) increases the chances of conflicts exponentially. If you wrote it yourself, consider a namespace akin to std or sfml.

Where are your newlines and spaces?

Your code is incredibly hard to read. I'm not going to tell you specifically how you should format your code, but at least consider formatting it to increase readability.

emplace_back over push_back

push_back will delegate to emplace_back. The advantage emplace_back has over push_back is that it will forward the arguments to the constructor, so you don't have to specify the type.

polyEdges.emplace_back(last, first);

Explain your algorithm; choose better variable names

intersectPoint is incredibly difficult to read. p0_x is easy to deduce, but what is s1_x? What is this line doing?

s = (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y);

Even putting the name of the algorithm in a comment will give the reader enough context to figure it out.

Redundancy

You have wrapper functions that pass arguments along but this is pointless. Why duplicate the interface? As you can imagine, the more granular you get, the more bloated your interface will be.

\$\endgroup\$
  • 1
    \$\begingroup\$ Excellent first answer! Welcome to Code Review. \$\endgroup\$ – glampert Oct 14 '15 at 1:56
  • \$\begingroup\$ Thank you for the remarks! 1. Unfortunately, using namepace std is included in the additional external files, otherwise I would definitely follow your advice. 2. Newlines and spaces were omitted to make the code more concise, however, it has resulted in making it hard to read, thus I'll add them back. 3. emplace_back() will be considered and used. Finally, interectPoint is entirely replaced. \$\endgroup\$ – Ziezi Oct 14 '15 at 6:54
2
\$\begingroup\$

The code doesn't seem to work correctly. For example:

static void generatePoints(vector<Point>& p) 
{
    p.push_back(Point(50, 50));
    p.push_back(Point(200, 150)); //instead of Point(200,50)
    p.push_back(Point(250, 100));
    p.push_back(Point(200, 200));
    p.push_back(Point(100, 225));
    p.push_back(Point(50, 200));
    p.push_back(Point(25, 100));
}

And you'll get result as follows:

enter image description here

\$\endgroup\$
1
\$\begingroup\$

Redundancy

I see a lot of code that packages stuff up and then moves it into another wrapper. For example, in main() you put a bunch of points into a vector, then you iterate over the vector and add those points to a Striped_closed_polyline. Why not just directly add them to the polyline? The generatePoints function could look like this:

static void generatePoints(Striped_closed_polyline& scp)
{
    scp.add(Point(50, 50));
    scp.add(Point(200,50));
    scp.add(Point(200,100));
    scp.add(Point(200,200));
    scp.add(Point(100,225));
    scp.add(Point(50,200));
    scp.add(Point(25,100));
}

Also in draw_lines(), you're putting points into a vector, sorting them, and then only using the first one. You don't need to sort to find the min or max. You can just iterate over them and keep a running min or max.

Naming and Location

The IntersectPoint() function is poorly named. 2 points are either coincident or they're not. But you're not finding the intersection of points, you're finding the intersection of edges. This tells me 2 things:

  1. It should be a part of the Edge class
  2. It should just be named Intersection and take a second Edge as its only argument

Errors

Why is the Striped_closed_polyline::spacing variable declared static? That means that every instance of that class will have the same value. If you want to have 1 with a spacing of 5 and another with a spacing of 10, you can't.

If IntersectPoint() does not find an intersection, it returns a valid Point with the coordinates (-1, -1). What if someone has 2 line segments that intersect at (-1, -1)? You should return a separate error code.

The lines in your drawing are not evenly spaced. I don't immediately see what the problem is, but clearly, the output doesn't look right.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the useful advice! 1. Following your suggestion, to generate points I use static void generatePoints(Striped_closed_polyline* scp), using pointers was the only valid way to implement it, possibly because add() function in the base class is protected and the container holding the points is private. 2. sort() is no longer used to find min and max, instead a loop is used. 3. The function finding intersections is changed and I'll consider integrating it in class Edge. 4. variable spacing is instead added to a (default) constructor \$\endgroup\$ – Ziezi Oct 14 '15 at 7:32
1
\$\begingroup\$

For quaranteed convex shapes like in your example, it might be worth breaking the Bresenham algorithm for the outside polylines apart and insert the horizontal stripe start and end coordinates into a vector every time the vertical coordinate reaches the next stripe position. This can save you the time to calculate start and end points of the horizontal stripes twice.

Once your shape is closed, draw the stripes from the pre-calculated start and end points in the vector.

Doesn't work for concave shapes, though.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.