suppose que j'ai un tas de rectangles, dont certains se croisent, certains isolent. E. g. rect A, B intersect les uns avec les autres, C, D avoir un même point, e, f avoir deux mêmes points, X, y sont isolés. P> J'ai deux questions: p>
bool intersectRect(const Rect& rect1, const Rect& rect2) {
/* if rect1 and rect2 intersect return true
else return false
*/
}
Rect mergeIntersectRects(const set<Rect>& rects) {
// suppose rects are all intersected. This function only return a smallest Rect that cover all rects.
}
set<Rect> mergeRectToRects(const set<Rect>& rectset, const Rect& rect) {
set<Rect> _intersect_rects;
set<Rect> _unintersect_rects;
for(set<Rect>::const_iterator it = rectset.begin();
it != rectset.end();
++it) {
if(intersectRect(*it, rect))
_intersect_rects.insert(*it);
else
_unintersect_rects.insert(*it);
}
if(!_intersect_rects.empty()) {
_intersect_rects.insert(rect);
return mergeRectToRects(_unintersect_rects,
mergeIntersectRects(_intersect_rects));
}
else {
_unintersect_rects.insert(rect);
return _unintersect_rects;
}
}
4 Réponses :
J'utiliserais la méthode suggérée par @damon, mais accélère la recherche rectangle voisine avec une structure d'indexation spatiale, par exemple un quadtree ou une grille. Vous auriez besoin de deux d'entre eux, d'abord construits sur l'ensemble des rectangles d'entrée, pour rechercher des rectangles intersectifs à scinder et deuxième construit sur l'ensemble des rectangles fractionnés obtenus en première étape, pour rechercher des rectangles adjacents à fusionner. Cela devrait accélérer considérablement les choses comparées à l'approche naïve.
Premièrement, je suppose que vos rectangles sont tous axes-alignés.
pour Q1, une option serait de Par exemple, disons que votre ligne de balayage se déplace à gauche À droite: P>
Current
Interior
|
+---------+-|--- + +-------- + *
| | | | | | |
| | | | | | |
| | | | | C | |
| | |-------------- + | | |
| | | | | +---------+-------- + |
| | | | | | | |
+---------+ |--- + B | | D | |
| | | | | |
| | | +------------------ + |
+-|-------------- + *
|
+-----------|------ + +-------- + *
| | | | | |
| | | | X | |
| |-------+ | | |
| | | +-------- + |
| | | +------------ + |
| | | | | |
| | | | | |
| | | | Y | |
| | | | | |
+-----------|-------+ +------------ + *
|
Voici l'algorithme: http://goo.gl/awdjo
Vous pouvez lire sur la recherche des algorithmes de coque convexe: http: // ralph.cs.cf.ac.uk/papers/geometry/boxing.pdf
Q1: Ceci s'appelle la partition de polygone rectiligne. Réponse de Rob's Commentaire a une très bonne description. J'ai trouvé papier mentionné dans le answer utile.
Q2: i Supposons que vous ne vouliez pas que deux couvertures de régions non intersectives soient intersect. Like Cover pour 3 rectangle, 2 rectangle produisant L et rectangle rectangle couvercle de L mais pas de l rectangle.
Si c'est comme ça, il est possible de créer progressivement des couvertures. Voici un algorithme simple pour cela. Ce code n'est pas efficace sous forme standard. Avec une bonne structure pour couvre structure, il peut être efficace.
Cela n'a pas l'air terriblement difficile, qu'avez-vous eu jusqu'à présent? Comme votre question se trouve, il semble que vous attendiez de manière à faire tout le travail!
Avez-vous des conseils pour calculer les rectangles? Peut être un algorithme? Question A et B sont deux questions réellement
Ce que je ferais, c'est diviser un rectangle dans 4 quand un autre touche ou intersecte, accumulant de nombreux sous-rectangles. Ensuite, itérez sur la liste et pour chaque article, trouvez le plus grand adjacent, le cas échéant. Réduisez-les dans un plus grand rectangle. Malheureusement, c'est O (n ^ 2) et donc probablement pas l'algorithme le plus efficace, mais donc quoi. N et n ^ 2 sont une sorte de même si n est un nombre raisonnable (c'est-à-dire non dans les milliers ou dix mille). Il est mort simple à mettre en œuvre et presque impossible de se tromper.
Oui, votre méthode est assez simple mais le nombre de rectangles est énorme. Le pire des cas peut être 50000000 actuellement
Dupliqué possible de algorithme pour trouver le moins de rectangles pour couvrir un ensemble de rectangles