Encontrar grupo de rectángulos que se cruzan - c ++, algoritmo, intersección

Tengo una lista de rectángulos (no pueden rotar):

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);

Quiero calcular el grupo de rectángulos que tienen al menos una intersección, con propiedad de transitividad. es decir, si r1 se cruzan r2 y r2 se cruzan r3, r1, r2, r3 son parte del mismo grupo.

En esta muestra, el grupo será

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

El orden de grupo y el orden de elementos dentro del grupo no es importante.

¿Cómo puedo calcular estos grupos? Puedo cambiar la estructura de datos si es necesario.

Por ejemplo, puedo cambiar std::vector a std::set y ordenar rectángulos por la coordenada X del vértice izquierdo. De esta manera puedo usar un algoritmo de línea de barrido. Pero no puedo encontrar ninguna muestra que pueda aplicarse a mi problema.

¿Cómo puedo obtener grupos que se cruzan?

Respuestas

3 para la respuesta № 1

Creo que un vector de conjuntos haría el trabajo.

Me gusta esto:

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;

Para escribir un código más limpio, sugeriría actualizar su rectángulo para que funcione bien con el 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;

... agregando una clase para manejar el vector de conjuntos ...

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();
}
};

... para que podamos escribir ...

 // 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 para la respuesta № 2

He estado trabajando en un problema donde la pregunta del OP es una solución intermedia. El proceso para el conjunto dado de rectángulos (o para cualquier conjunto de rectángulos) es el siguiente:

1. Haz una lista de rectángulos que se crucen con cada rectángulo. Entonces, para los 6 rectángulos en la muestra, tendremos 6 listas. El resultado del paso 1 es el que se muestra a continuación:

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

2. A continuación, iteramos a través de esta lista de listas yfusionar las listas si alguno de los rectángulos existe en la siguiente lista. Por ej. el rectángulo 1 de la lista 1 existe en la lista 2. Por lo tanto, la lista fusionada formada por la lista1 y la lista2 sería [1,2,4]. Vacíe la lista1 para que no podamos usarla nuevamente en la próxima iteración. El resultado de cada iteración se muestra a continuación:

   [[], [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. Eliminar las listas vacías de la lista. El resultado es un grupo de rectas que se cruzan.

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

Espero que esto ayude. No hablo C ++ con fluidez. Sin embargo, si ayuda, puedo compartir con ustedes el código de Director Lingo que he escrito. La razón por la que no publiqué el código de Lingo es porque ya casi nadie trabaja en el Director.

---