Znajdź grupę przecinających się prostokątów - c ++, algorytm, przecięcie

Mam listę prostokątów (nie mogą się obracać):

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

Chcę obliczyć grupę prostokątów, które mają co najmniej jedno przecięcie z właściwością przechodniości. tj. jeśli r1 przecinają r2 i r2 przecinają r3, r1, r2, r3 są częścią tej samej grupy.

W tym przykładzie grupa będzie

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

Kolejność grup i kolejność elementów w grupie nie jest ważna.

Jak mogę obliczyć te grupy? W razie potrzeby mogę zmienić strukturę danych.

Na przykład mogę zmienić std::vector do std::set i uporządkuj prostokąty według lewej współrzędnej X wierzchołka. W ten sposób mogę użyć algorytmu linii przeciągnięcia. Ale nie jestem w stanie znaleźć próbki, którą można by zastosować do mojego problemu.

Jak mogę uzyskać przecinające się grupy?

Odpowiedzi:

3 dla odpowiedzi № 1

Myślę, że wektor zestawów by zadziałał.

Lubię to:

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;

Aby napisać czystszy kod, sugeruję uaktualnienie prostokąta, aby działał ładnie z 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;

... dodając klasę do obsługi wektora zestawów ...

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

... abyśmy mogli pisać ...

 // 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 dla odpowiedzi nr 2

Pracowałem nad problemem, w którym pytanie OP jest rozwiązaniem pośrednim. Proces dla danego zestawu prostokątów (lub dowolnego zestawu prostokątów) wygląda następująco:

1. Zrób listę prostokątów, które przecinają się z każdym prostokątem. Tak więc dla 6 prostokątów w próbce będziemy mieli 6 list. Wynik kroku 1 przedstawia się następująco:

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

2. Następnie iterujemy tę listę list iscal listy, jeśli jeden z prostokątów istnieje na następnej liście. Na przykład prostokąt 1 z listy 1 istnieje na liście 2. Dlatego połączona lista utworzona z list1 i list2 będzie wynosić [1,2,4]. Opróżnij listę 1, abyśmy nie mogli jej użyć ponownie w następnej iteracji. Wynik każdej iteracji pokazano poniżej:

   [[], [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. Usuń puste listy z listy. Rezultatem jest grupa przecinających się prostokątów.

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

Mam nadzieję że to pomoże. Nie mówię płynnie w C ++. Jeśli jednak to pomoże, mogę udostępnić Ci kod dyrektora Lingo, który napisałem. Powodem, dla którego nie opublikowałem kodu Lingo, jest to, że rzadko ktoś już pracuje w Director.

---