Member Avatar for exca

Hi all,

I am trying to write a program that computes the areas of intersecting rectangles. The coordinates of the rectangles are given. A rectangle may intersect another one or just stand alone.
My code is:

Rectangle class:
#include "Rectangle.h"

Rectangle::Rectangle(){

	this->parent=this;
	this->area=0;
	this->x1=0;
	this->x2=0;
	this->y1=0;
	this->y2=0;
	this->visited=false;

}
/*
 *  recursive method to find the root of a rectangle object
 */
Rectangle* find(Rectangle *x){
	if(x->parent == x)
			return x;
	else
		return find(x->parent);
}
/*
 *  method to merge two sets if they are not already in the same set
 */
void unionSets(Rectangle * x, Rectangle * y){ 

	y->parent=x;

}
int dfsArea(Rectangle * currentRect, int n, vector<Rectangle*> myvector, int & area, Rectangle * root){

	currentRect->visited=true;
	area+=(currentRect->x2-currentRect->x1)*(currentRect->y2-currentRect->y1);

	if(currentRect->parent!=currentRect){
		area-=(min(currentRect->x2, currentRect->parent->x2)-max(currentRect->x1, currentRect->parent->x1))*(min(currentRect->y2, currentRect->parent->y2)-max(currentRect->y1, currentRect->parent->y1));
	}

	// for each rect intersecting with currentRect
	for(int k=0; k<n ; k++){
		if(myvector[k]->visited==false && currentRect->x2 > myvector[k]->x1 && currentRect->x1 < myvector[k]->x2 && currentRect->y2 > myvector[k]->y1 && currentRect->y1 < myvector[k]->y2)
		{
			unionSets(currentRect, myvector[k]);
			area+=dfsArea(myvector[k], n, myvector, area, root);
		}
		else if(find(myvector[k])==root && currentRect!=myvector[k]){ // &root?
			area+=(currentRect->x2-currentRect->x1)*(currentRect->y2-currentRect->y1);
			area-=(min(currentRect->x2, currentRect->parent->x2)-max(currentRect->x1, currentRect->parent->x1))*(min(currentRect->y2, currentRect->parent->y2)-max(currentRect->y1, currentRect->parent->y1));
			area-=(min(currentRect->x2, myvector[k]->x2)-max(currentRect->x1, myvector[k]->x1))*(min(currentRect->y2, myvector[k]->y2)-max(currentRect->y1, myvector[k]->y1));

		}
	}
	return area;
}

dfsArea function merges rectangles if they are intersecting and computes their total area.

My question is, am I doing it right about the parameters? Should the pointers or just the objects they (for example myvector) point to be modified? And how?

Could you please help me with this?
Thanks in advance.

  • 2 Contributors
  • 2 Replies
  • 110 Views
  • 14 Hours Discussion Span
  • Latest Post Latest Post by exca

Dani AI

Generated

Short answer for : yes — you can mix pointers and references, but pick the right one for what you want to change.

Pointers vs references (what they do)

  • Passing Rectangle *r (pointer by value) lets the function modify the Rectangle object r points to (members like visited or parent) and those changes are visible to the caller. It does NOT let the function change the caller's pointer variable itself.
  • Passing Rectangle *&r (pointer by reference) lets the function reassign the caller's pointer (make it point somewhere else).
  • Passing std::vector<Rectangle*> by value copies the container (costly). Pass const std::vector<Rectangle*>& for read-only access, or std::vector<Rectangle*>& if you will mutate which elements are in the container.
  • const references are great for read-only; avoid const if you need to flip visited flags.

Interface and code hygiene suggestions

  • Don’t pass n if you already have the vector — use rects.size().
  • Don’t both return area and pass it by reference; pick one pattern (e.g., return the computed area).
  • Implement find/union on roots (use find(x) and find(y) before linking), add path compression and union-by-rank for performance. Consider storing parents as indices (ints) if rectangles live in a single vector — that avoids pointer lifetime issues.
  • When computing intersection width/height always clamp to non-negative values (use max(0, ...)) before multiplying.

Algorithm correctness

  • Union-find groups connected rectangles but subtracting pairwise overlaps from a DFS will give incorrect results when three or more rectangles overlap in complex ways. To compute union area robustly, use a sweep-line / active-interval approach (process vertical edges, maintain union length of y-intervals per strip) or compute exact union per connected component with the same sweep. See a practical description at and background on DSU at Disjoint-set data structure (Wikipedia).

Tiny examples (semantics)

void markVisited(Rectangle* r) { r->visited = true; }   // modifies object
void reassign(Rectangle*& p, Rectangle* newP) { p = newP; } // modifies caller pointer

Follow these rules and the parameter choices will be clear and bug-resistant.

Recommended Answers

All 2 Replies

Member Avatar for mrnutty

If you can, eliminate all the pointers for const-reference.

Member Avatar for exca

If you can, eliminate all the pointers for const-reference.

Can't I do them together?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.