Rechercher un groupe de rectangles se croisant - c ++, algorithme, intersection

Je "ai une liste de rectangles (ils ne peuvent pas tourner):

struct Rectangle {
double centerX;
double centerY;
double width;
double height;

Rectangle(double x, double y, double w, double h):centerx(x),centery(y),width(w),height(h){}
};

std::vector<Rectangle> rectangles;
rectangles.push_back(Rectangle(0  ,  0  , 1  , 1  );
rectangles.push_back(Rectangle(0.5,  0.5, 1  , 1  );
rectangles.push_back(Rectangle(3  ,  2  , 0.5, 0.6);
rectangles.push_back(Rectangle(0.2,  0.5, 0.5, 0.6);
rectangles.push_back(Rectangle(2  , -0.3, 0.4, 0.4);
rectangles.push_back(Rectangle(0.2, -0.4, 0.3, 0.4);

Je veux calculer un groupe de rectangles qui ont au moins une intersection, avec une propriété de transitivité. c'est-à-dire que si r1 intersecte r2 et r2 intersectent r3, r1, r2, r3 font partie du même groupe.

Dans cet exemple, le groupe sera

{{3}, {4, 1, 2}, {5, 6}}

L'ordre du groupe et l'ordre des éléments à l'intérieur du groupe n'ont pas d'importance.

Comment puis-je calculer ces groupes? Je peux changer la structure des données si nécessaire.

Par exemple, je peux changer std::vector à std::set et ordonnez les rectangles par la coordonnée X du sommet gauche. De cette façon, je peux utiliser un algorithme de ligne de balayage. Mais je ne suis pas en mesure de trouver un échantillon pouvant être appliqué à mon problème.

Comment puis-je obtenir des groupes qui se croisent?

Réponses:

3 pour la réponse № 1

Je pense qu'un vecteur d'ensembles ferait le travail.

Comme ça:

std::vector< std::set< int > > groups;

// loop over rectangles
for( int r1 = 0; r1 < rectangles.size(); r1++ )
{
// check if rectngle already in group
auto g_it = groups.end();
for( auto group = groups.begin();
group != groups.end(); group++ )
{
auto group_r1_it = group->find( r1 );
if( group_r1_it != group->end() )
{
g_it = group;
break;
}
}
if( g_it == groups.end() )
{
// not already in group, so create new group
set<int> s;
s.insert( r1 );
groups.push_back( s );
g_it = groups.end()-1;
}

// loop over remaining rectangles
for( int r2 = r1+1; r2 < rectangles.size(); r2++ )
{
// check for intersection
if( rectangles[r1].Intersect( rectangles[r2] ))
{
//report intersection
cout << r1+1 <<" " <<r2+1 << endl;

// add to group
g_it->insert( r2 );

}
}

}
// Display results
for ( auto group : groups )
{
cout << "{ ";
for( auto r : group )
{
cout << r+1 << " ";
}
cout << "} ";
}
cout << endl;

Afin d'écrire du code plus propre, je vous suggère de mettre à jour votre rectangle pour qu'il soit bien joué avec la STL ...

class Rectangle
{
public:
double centerX;
double centerY;
double width;
double height;
int myID;
static int lastID;

Rectangle(double x, double y, double w, double h)
:centerX(x),centerY(y),width(w),height(h),
myID( ++lastID )
{        }

bool Intersect( const Rectangle& other ) const
{
...
}
bool operator ==(const Rectangle& other ) const
{
return myID == other.myID;
}
bool operator <(const Rectangle& other ) const
{
return myID < other.myID;
}
};

int Rectangle::lastID = 0;

... ajout d'une classe pour gérer le vecteur d'ensembles ...

class RectangleGroups
{
public:
typedef std::set< Rectangle > group_t;
typedef std::vector< group_t >::iterator iter;

iter begin()
{
return groups.begin();
}
iter end()
{
return groups.end();
}
/**  Build the groups of intersecting trinagles

@param[in] rectangles  vector of rectangles
@param[in] intersections vector of pairs of intersecting rectangles
*/
void Make(
std::vector< Rectangle > rectangles,
std::vector< std::pair< Rectangle&, Rectangle& > >& intesections )
{
// loop over intersecting triangles
for( auto rp : intesections )
{
iter g_it = Find( rp.first );
if( g_it != groups.end() )
{
g_it->insert( rp.second );
continue;
}
g_it = Find( rp.second );
if( g_it != groups.end() )
{
g_it->insert( rp.first );
continue;
}
// neither rectangle is already in group, so add new group
g_it = Add( rp.first );
g_it->insert( rp.second );

}
// Add orphans
for(  auto& r : rectangles )
{
if ( Find( r ) == groups.end() )
{
Add( r );
}
}
}
/// Display rectangle IDs in groups marked off with curly braces
void Display()
{
for ( auto group : groups )
{
cout << "{ ";
for( auto r : group )
{
cout << r.myID << " ";
}
cout << "} ";
}
cout << endl;
}

private:
std::vector< group_t > groups;

///  Add new group containing a copy of a rectangle, return iterator pointing to new group
iter Add( const Rectangle& r )
{
group_t s;
s.insert( r );
groups.push_back( s );
return groups.end()-1;

}
///  Find group containing rectangle, return iterator pointing to found group or to end
iter Find( const Rectangle& r )
{
for( iter it = groups.begin(); it != groups.end(); it++  )
{
auto group_it = it->find( r );
if( group_it != it->end() )
{
return it;
}
}
return groups.end();
}
};

... afin que nous puissions écrire ...

 // vector of intesections
// you can build this using various algorithms, even a sweepline
// here I will use a simple pair of nested for loops
std::vector< std::pair< Rectangle&, Rectangle& > > intersections;
// loop over rectangles
for( auto& r1 : rectangles )
{
// loop over remaining rectangles
for( auto& r2 : rectangles )
{
if( r2 < r1 || r1 == r2 )
continue;

// check for intersection
if( r1.Intersect( r2 ))
{
intersections.push_back( std::pair<Rectangle&, Rectangle& >( r1, r2 ) );
}
}
}

// Construct a vector of rectangle groups
// The groups will contain interesecting rectangles.
RectangleGroups groups;

groups.Make(
rectangles,
intersections );

// Display results
groups.Display();

---

1 pour la réponse № 2

Je travaille sur un problème où la question du PO est une solution intermédiaire. Le processus pour l’ensemble donné de rectangles (ou pour tout ensemble de rectangles) est le suivant:

1. Faites une liste des rectangles qui se croisent avec chaque rectangle. Donc, pour les 6 rectangles de l'échantillon, nous aurons 6 listes. Le résultat de l'étape 1 est le suivant:

   [[1,2], [2,1,4], [4,2], [3], [5,6], [6,5]]

2. Ensuite, nous parcourons cette liste de listes etfusionner les listes si l’un des rectangles figure dans la liste suivante. Pour par exemple. Le rectangle 1 de la liste 1 existe dans la liste 2. Par conséquent, la liste fusionnée formée à partir des listes list1 et list2 serait [1,2,4]. Videz la liste1 afin que nous ne puissions "pas l'utiliser à la prochaine itération. Le résultat de chaque itération est présenté ci-dessous:

   [[], [2,1,4], [4,2], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [5,6], [6,5]] [[], [], [4,2,1], [3], [], [6,5]]

3. Supprimer les listes vides de la liste. Le résultat est un groupe de droits qui se croisent.

   [[4,2,1], [3], [6,5]]

J'espère que cela t'aides. Je ne parle pas C ++ couramment. Cependant, si cela peut aider, je peux partager avec vous le code Director Lingo que j'ai écrit. La raison pour laquelle je n'ai pas posté le code Lingo est que rarement, plus personne ne travaille dans Director.

---