C++

Forum

 
how to split a square into smaller squares with equal size?

m2020 (15)
My question is if we have fixed size square how can we partition it to have say 4 or 25 smaller squares?
square partitioning:
https://drive.google.com/open?id=1UvrvAbqxSTzcXSjL7ejumqAsgRCBHLlQ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
typedef std::pair<int, int> Point;

class Square
{
Point left_down = {0, 0};
Point up_right;
public:
int lowerB(){ return left_down.first; }
int upperB() { return up_right.first; };

Square(){}
Square(int size) :up_right({size, size}) {};
Square(Point p1, Point p2): left_down(p1), up_right(p2) 
{}

static int number_of_squares;
};
int Square::number_of_squares = 1;

and i derived a class from Square to form the sub-squares:
1
2
3
4
5
6
7
8
9
10
11
 
class Sub_sqr: public Square
{
Point xy1;
Point xy2;

int S_indx; // an identifier

public:
Sub_sqr() { number_of_squares++; }
int indx() { return S_indx; }
};


I've tried the above algorithm, is it correct? the number of instances we make the number of squares we have. for example if we want to extract 256(square number: 1 4 9 16 25 ...) not overlapping sub-squares out of square with size 80 * 80 or whatever, we should have 256 instances of sub_sqr class.

and for grid i wrote the followings:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
class Grid
{
int size;

public:
vector<vector<Point>> grid;

Grid(int size) :size(size), grid(size, vector<Point>(size)) 
{
    for (size_t y = 0; y < grid.size(); y++)
    {
        vector<Point> loc;
        for (size_t x = 0; x < grid[y].size(); x++)
        {
            loc.push_back({ x, y });
        }
        grid[y] = loc;
    }
 }
};


My final goal to make grid inside the square by partitioning it into equal size sub-squares and assign each cell of grid some property.


Is there any algorithm or library for doing this? if yes can you share it please.
Regards
Last edited on
closed account (SECMoG1T)
there is no special requirement i know of ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
 
#include <iostream>
#include <iomanip>
#include <cmath>
#include <list>

struct Coord
{
    double x;
    double y;
};

template<typename ostream>
ostream& operator <<(ostream& os, const Coord& coord_)
{
    os<<std::left;
    os<<" [x: "<<std::setw(5)<<coord_.x<<" , y: "<<std::setw(5)<<coord_.y<<std::right<<"] \n";
    return os;
}

/* assumes that the {x,y} coordnates of the square increase downwards and right
 *    |---------------------------> x increases this way
 *    |    point A|-----------  point B
 *    |           |           |
 *    |           |           |
 *    |    point C|___________|point D
 *    \/
 *    y increases donwards
 *    such that if point A=(0,0) then B=(0,1) , C=(1,0), D=(1,1)
 *
 *   Requires: for a square to be divided into smaller squares where N = number of squares then
 *             N must be a perfect square such that sqroot(N) == whole number
 *             N can be numbers like 1,4,9,16,25,36,64,81 ...
 *             if N isn't a perfect square then the result would be rectangles.
 */

class Square
{
    private:
        Coord top_left;
        double   side_length;

    public:
        Square()=default;
        Square(const Coord& point_,double side_len)
         :top_left(point_),side_length(side_len){}

        Square(const Square&)=default;
        Square& operator=(const Square&)=default;
        virtual ~Square(){}

        inline Coord get_top_left()const {return top_left;}
        inline Coord get_top_right()const {return {top_left.x+side_length,top_left.y};}
        inline Coord get_lower_left()const {return {top_left.x,top_left.y+side_length};}
        inline Coord get_lower_right()const {return {top_left.x+side_length, top_left.y+side_length};}

        inline double get_area()const {return side_length*side_length;}
        inline double get_side_length()const{return side_length;}
};

class Sub_square : public Square
{
    private:
        std::size_t identifier;
    public:
        Sub_square(): Square(),identifier(0){}
        Sub_square(const Coord& point_,double side_len,std::size_t id_)
         :Square(point_,side_len),identifier(id_){}

        inline std::size_t get_id()const{return identifier;}

        void print_detail()const
        {
            std::cout<<"\nsub Square id : "<<identifier<<"\n";
            std::cout<<"     length     : "<<get_side_length()<<"\n";
            std::cout<<"     area       : "<<get_area()<<"\n";
            std::cout<<"----------------------------------------\n";
            std::cout<<"top left        : "<<get_top_left();
            std::cout<<"top right       : "<<get_top_right();
            std::cout<<"lower left      : "<<get_lower_left();
            std::cout<<"lower right     : "<<get_lower_right();
            std::cout<<"----------------------------------------\n";
        }

        ///other members
};

class Square_grid
{
    private:
        Square source_square;
        std::size_t total_squares;
        std::list<std::list<Sub_square>> sub_sqr_list;
        bool populated;

        static bool is_perfect_square(std::size_t x)
        {
            //!cant use use std::sqrt() because of floating point rounding errors
            //Let n be the number, a=5n and b=5.
            //While a>=b,  a=a−b and add 10 to b.
            //When you get a<b, then n is a square if and only if a=0.
            std::size_t checkr =(x*5);
            std::size_t bound  = 5;
            std::size_t increment =10;

            while(checkr >= bound)
            {
                checkr -= bound;
                bound  += increment;
            }

            if(checkr==0)
                return true;
            return false;
        }

        /*square_: original square to be divided
         *nom_of_squares: (>0) number of squares it should be divided into.
         *              :  this number must be a perfect square e.g 4,9,16,25,36 such that sqrt(num_of_squares) = whole number
         *                 otherwise you will be dividing into rectangles
         */

        void grid_init(const Square& square_,std::size_t num_squares)
        {
            if(is_perfect_square(num_squares))
            {
                source_square = square_;
                total_squares = num_squares;
                populated     = true;

                std::size_t sqr_id_=1;
                std::size_t div_per_side = (std::size_t)std::sqrt(num_squares);
                double sub_sqr_len = (square_.get_side_length()/div_per_side);

                ///dividing the square
                double x_coord = square_.get_top_left().x;
                double y_coord = square_.get_top_left().y;

                for(std::size_t x =0; x < div_per_side; x++, x_coord += sub_sqr_len)
                {
                    std::list<Sub_square>  column{};
                    for(std::size_t y = 0; y < div_per_side; y++, y_coord += sub_sqr_len)
                    {
                        Coord sqr_coord={x_coord,y_coord};
                        Sub_square  this_square(sqr_coord,sub_sqr_len,sqr_id_);
                        column.push_back(this_square);
                        ++sqr_id_;
                    }
                    sub_sqr_list.push_back(column);
                    y_coord = square_.get_top_left().y;
                }
            }

        }

        void reset(){source_square= Square(); total_squares=0;sub_sqr_list={}; populated=false;}
    public:
        Square_grid() :source_square(),total_squares(0),sub_sqr_list({}), populated(false){}
        Square_grid(const Square& square_, std::size_t num_squares)
         :source_square(),total_squares(0),sub_sqr_list({}), populated(false)
        {
            grid_init(square_,num_squares);
        }

        inline std::list<std::list<Sub_square>> get_all_sub_squares() const{return sub_sqr_list;}
        inline std::size_t get_square_count() const{return total_squares;}
        inline Square      get_original_square()const {return source_square;}
        inline bool        valid_grid() const{return populated;}

        void construct_from(const Square& square_, std::size_t num_squares)
        {
            reset();
            grid_init(square_,num_squares);
        }
       
       ///return pointer to sub square containing the coordinates point;
        Sub_square* get_coord_owner(Coord& point)///new function
        {
            if(coord_within_grid(point))
            {
                Coord point_of_origin = source_square.get_top_left();

                double dist_x_from_orig = point.x - point_of_origin.x;
                double dist_y_from_orig = point.y - point_of_origin.y;

                int column_num = (int)(dist_x_from_orig/sub_sqr_length);
                int row_num    = (int)(dist_y_from_orig/sub_sqr_length);

                return &sub_sqr_vector[column_num][row_num];
            }

            return nullptr; ///coordinates outside the grid
        }

        void print_grid() const
        {
            if(sub_sqr_list.empty())
            {
                std::cout<<"ERROR: Failed to divide your square: \nthe number of squares to be divided into\nshould be sqrt(num_square)==whole number\n\n";
                return;
            }

            int col = 1;
            for(auto& column : sub_sqr_list)
            {
                std::cout<<"\n^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n";
                std::cout<<"grid column : "<<col<<"\n";
                std::cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^\n";
                for(auto& coord : column)
                {
                    coord.print_detail();
                }
                ++col;
            }
        }
};


///driver prog
int main()
{
    Coord coord={47,95};///top left x,y coordinates for the main square
    std::size_t sub_squares_to_divide = 25, main_sq_side_length=73;

    Square       big_sq(coord,main_sq_side_length);
    Square_grid  grid(big_sq,sub_squares_to_divide);

    grid.print_grid();
}
Last edited on
m2020 (15)
Thanks a million dear Yolanda.

could you please guide me how to do next step of my project? just how to do it. not the code.

my next step is to fit a graph inside this grid. such that each edges of the graph knows the cells it traverses. and along the traversal conveys each cell property. i.e. if two edges completely resides in on cell, they both must have the same property of that cell. but if we have edge passes through 3 cells then the property the edge should have is the sum of properties of the cells it traverses.

https://drive.google.com/open?id=1h7Xip0bQaLznipqpruMD2e_HtL1gq22L

Assumptions: we have the coordinates of each node of graph as pair<int, int>

and the Graph i have:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
class Graph
{
  int V; // No. of vertices’

public:
  int getV() { return V; }


   std::vector<int>* parents;
   std::vector<int>* childs;

   std::map<int, Point> nodes_location;

   Graph(){}

   Graph(int V) // Constructor
   {
        parents = new std::vector<int>[V];
        childs = new std::vector<int>[V];
   }; 

   void Insert_Node(int u, int v)
   {
       childs[u].push_back(v);
       parents[v].push_back(u);
   }

}


could you please tell me what should i do?

Thank you
Regards.
closed account (SECMoG1T)
i thought your question was completely solved: mark you thread as solved only after you av bagged enough solutions and different perspectives from different people.

so after seeing your second question i couldn't completely get what you meant by this
"properties" so i decided to solve the question:

how do you determine what cells/squares an edge passes through in a square grid?


unfortunately i couldn't also perfectly explain that to myself without writing some code.

the code itself is rather brute force but if you read it you might get the idea. i created a class Edge

the code is based on the previous post so you can delete the main() from the prvious
post and paste this |
\/

test, read it, get the concept, modify as it will suit you.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
class Edge///for this example i'll need this class to store extra edge properties
{
    typedef Coord dx_dy;

    /*assumes: an edge connects two nodes */
    private:
        Coord NodeA_coords; //this is just an example, your nodes could be complex or simple objects
        Coord NodeB_coords; //i choose to store only the node coordinates for simplicity
        std::vector<Sub_square*> transit_sub_cells;
        //holds pointers to sub_squares in a grid that this edge transits
        //you can use those pointers to retrieve properties from the sub_square
        //anything your are interested in in such a sub square

        /* if: node_A == coord{x,y). and node_B == coord{x1,y1);
         * dx = x-x1  dy = y-y1
         */
        dx_dy get_dx_dy()
        {
            return {(NodeA_coords.x - NodeB_coords.x),(NodeA_coords.y - NodeB_coords.y)};
        }

        Coord get_incrimental_point_change(double sub_sq_unit_length, double coord_resolution = 10.0);//defined outside

    public:
        Edge()=default;
        Edge(const Coord& node_A_coord, const Coord& node_B_coord)
         :NodeA_coords(node_A_coord), NodeB_coords(node_B_coord),transit_sub_cells({}){}

        //other members
        inline void add_transit_cells(const std::vector<Sub_square*>& tr_cells)
        {
            transit_sub_cells = tr_cells;
        }

        inline std::pair<Coord,Coord> get_nodes() const
        {
            return {NodeA_coords,NodeB_coords};
        }

        void load_transit_grid_cells(Square_grid& grid);///defined outside

        void print_transit_sqrs() const
        {
            std::cout<<"this edge passes through this sub squares in the grid\n";
            std::cout<<"-----------------------------------------------------\n\n";
            for(auto Sq_ptr : transit_sub_cells)
            {
                Sq_ptr->print_detail();
            }
        }
};



///driver prog
int main()
{
    Coord coord={47,95};///top left x,y coordinates for the main square
    std::size_t sub_squares_to_divide = 25, main_sq_side_length=100;

    Square       big_sq(coord,main_sq_side_length);
    Square_grid  grid(big_sq,sub_squares_to_divide);

    Coord NodeA_coord{47.6,97.1}, NodeB_coord{146.6,145.5};

    Edge test_edge(NodeA_coord,NodeB_coord);

    test_edge.load_transit_grid_cells(grid);

    test_edge.print_transit_sqrs();


}




///computes change in every resolution of a sub square unit length
///that way we can determine if a point (x,y) lies within a sub square
///let coord_A and coord_b represent coordinates of nodes connected by
///the edge,and let length = the distance(coord_A,coord_B)
///goal: we want to determine if at any point in length above
///      passes through different Square cells in a grid;
///resolution: we will use this parameter to sub divide length
///            so that we get |resolution| new coordinates
///            that we can query with grid.get_coord_owner(new_coords);
///            if they fall in a different sub_square cell
///            then add them to the edge's vector of transit cells
/*
 *     so if resolution = 4;  and coord_A={0,1) coord_B={1,1} we will get {(0.25,1), (0.5,1), (0.75,1)} new coordinates
 *      coord_A (0,1)------new_coord1(0.25,1)------new_coord2(0.5,1)--------new_coord3(0.75,1)----coord_B(1,1)
 *
 *     so we will use get_incrimental_point_change(edge_slant,sub_sq_unit_length,resolution) to get an incrimental coord value
 *     such that    we can  temp_coord = coord_A; while(resolution--){new_coord = (temp_coord+incr_coord)}
 */
 ///returns:   incremental_coord value
Coord Edge::get_incrimental_point_change(double sub_sq_unit_length, double coord_resolution)
{
    const double Zero = 0;
    dx_dy edge_slant = get_dx_dy();
    double dx = edge_slant.x, dy = edge_slant.y;
    double abs_dx = std::fabs(dx), abs_dy = std::fabs(dy);
    Coord  result;
    ///dx = units of change in x from nodeA to nodeB
    ///dy = units of change in y from "    "     "

    if(abs_dx <= Zero && abs_dy <= Zero)
         return {Zero,Zero};

    else if(abs_dx <= Zero)
    {
         result={Zero,(sub_sq_unit_length/coord_resolution)};
    }

    else if(abs_dy <= Zero)
        result = {(sub_sq_unit_length/coord_resolution),Zero};

    else
    {
        ///Pythagoras theory Z^2 = X^2 + Y^2
        ///all coordinates lying on the length of the edge should maintain the gradient
        double orig_z     = std::sqrt((std::pow(dx,2) + std::pow(dy,2)));
        double sub_sqr_z  = sub_sq_unit_length;

        double z_ratio    = (sub_sqr_z / orig_z);
        double new_dx     = dx*z_ratio;
        double new_dy     = dy*z_ratio;

        result= {(new_dx/coord_resolution),(new_dy/coord_resolution)};
    }

    ///rectify direction
    if((NodeB_coords.y > NodeA_coords.y) && result.y < 0)
            result.y *=-1.0;
    else if((NodeB_coords.y < NodeA_coords.y) && result.y > 0)
         result.y *=-1.0;

    if((NodeB_coords.x > NodeA_coords.x) && result.x < 0)
         result.x *= -1.0;

    else if((NodeB_coords.x < NodeA_coords.x) && result.x > 0)
        result.x *=-1.0;

    return result;
}


void Edge::load_transit_grid_cells(Square_grid& grid)
{
     std::vector<Sub_square*>     cells{};/// keep pointers to sub squares you are passing through
                                          /// you can use them to get the "properties"
     std::set<std::size_t>      added_cells{};
     double  grid_sub_sqr_len = grid.get_sub_sqr_length();

     auto add_cell_id = [&](std::size_t cell_id){added_cells.insert(cell_id);};
     auto cell_id_added = [&](std::size_t cell_id)
     {
         if(added_cells.find(cell_id) == added_cells.end())
            return false;
         return true;
     };

     Coord incrementer      = get_incrimental_point_change(grid_sub_sqr_len);

     Sub_square* first_cell = grid.get_coord_owner(NodeA_coords);
     Sub_square* last_cell  = grid.get_coord_owner(NodeB_coords);

     if(first_cell && last_cell)
     {
         cells.push_back(first_cell);
         add_cell_id(first_cell->get_id());
         add_cell_id(last_cell->get_id());
     }

     else
     {
         std::cout<<"some of your coordinates lie outside the grid\n";
         return;
     }

     Coord transv_coord{NodeA_coords.x,NodeA_coords.y};

     transv_coord              += incrementer;
     Sub_square* sub_sqr_ptr    = grid.get_coord_owner(transv_coord);
     std::size_t this_cell_id   = sub_sqr_ptr->get_id();

     while(this_cell_id != last_cell->get_id())
     {
         if(!cell_id_added(this_cell_id))
         {
             cells.push_back(sub_sqr_ptr);
             add_cell_id(this_cell_id);
         }

         transv_coord += incrementer;
         sub_sqr_ptr   = grid.get_coord_owner(transv_coord);
         this_cell_id  = sub_sqr_ptr->get_id();
     }

     cells.push_back(last_cell);

     add_transit_cells(cells);
}
Last edited on
closed account (SECMoG1T)
if you need to test the code above and this function to class Square_grid
1
2
3
4
5
6
7
8
9
10
11
12
13
 
bool coord_within_grid(const Coord& point)
        {
            Coord    origin = source_square.get_top_left();
            double orig_len = source_square.get_side_length();

            if((point.x < origin.x ) || (point.x > (origin.x + orig_len))
               return false;

            else if((point.y < origin.y ) || (point.y > (origin.y + orig_len))
                    return false;

            return true;
        }
Topic archived. No new replies allowed.