Как я могу извлечь прямоугольники из пересечения прямоугольника - PullRequest
0 голосов
/ 01 февраля 2010

Имея прямоугольник (A) и пересекая его с другим прямоугольником (B), как я могу извлечь другие прямоугольники, созданные через это пересечение (C, D, E & F)?

AAAAAAAAAAAAAA    CCCFFFFDDDDDDD
AAABBBBAAAAAAA    CCCBBBBDDDDDDD
AAABBBBAAAAAAA -> CCCBBBBDDDDDDD
AAAAAAAAAAAAAA    CCCEEEEDDDDDDD
AAAAAAAAAAAAAA    CCCEEEEDDDDDDD

И может ли это быть расширено для извлечения прямоугольников из нескольких пересечений, таких как этот пример, который пересекает A с B & C и извлекает D, E, F & G?

BBBBAAAAAAAAAA    BBBBDDDDDDDDDD
BBBBAAAAAAAAAA    BBBBDDDDDDDDDD
AAAAAACCCCCAAA -> EEEEEECCCCCFFF
AAAAAACCCCCAAA    EEEEEECCCCCFFF
AAAAAAAAAAAAAA    EEEEEEGGGGGFFF

Ответы [ 7 ]

1 голос
/ 01 февраля 2010

Если ответ на вопрос TJB - да, тогда они:

(слева, сверху, справа, снизу) нотация

C = (A.left, A.top, B.left, A.bottom)

D = (B.right, A.top, A.right, A.bottom)

E = (B.left, B.bottom, B.right, A.bottom)

E = (B.left, A.top, B.right, B.top)

0 голосов
/ 08 декабря 2010

Для общего решения этой проблемы (вторая половина вашего вопроса) вам следует использовать структуру данных с угловыми сшиваниями , которая делает именно это (и даже больше).

0 голосов
/ 01 февраля 2010

Учитывая большой прямоугольник с любым количеством меньших прямоугольников, вырезанных из него, вы можете использовать жадный алгоритм, чтобы разбить оставшуюся область большого прямоугольника на меньшие прямоугольники.

  • Выберите самую левую, самую верхнюю точку, которая еще не была покрыта.
  • Начните там прямоугольник.
  • Вытяните его вниз насколько возможно.
  • Затем вытяните его вправо до упора.
  • Добавьте этот прямоугольник в свою коллекцию и повторите.

Это не гарантирует получение минимального количества прямоугольников.

Первый шаг - самый сложный. Если вы не возражаете против небольшой случайности, проще будет выбрать случайные точки, пока вы не найдете ту, которая еще не охвачена; затем идите налево, пока не дойдете до края; затем поднимайтесь, пока не дойдете до края.

0 голосов
/ 01 февраля 2010
for all rectangles A
   for all corners C of A
      for all other rectangles B
         if C is inside B
            for all corners D of B
               if D is inside A
                  got rectangle C-D
               endif
            endfor
         endif
      endfor
   endfor
endfor
0 голосов
/ 01 февраля 2010

для более произвольных форм будет работать алгоритм сканирования.вы получите разные результаты в зависимости от того, сканируете ли вы по горизонтали или по вертикали (ваш пример соответствует сканированию по вертикали)

по сути, вы сканируете вдоль каждого столбца или строки и разбиваете его на интервалы между каждой формой, интервалы в следующем столбце илистроки с одинаковым началом и концом могут быть объединены.

0 голосов
/ 01 февраля 2010

Если A полностью содержит B:

Rectange C = new Rectangle(A.X,A.Y,B.X-A.X,A.Height);
Rectange D = new Rectangle(B.Right,A.Y,A.Right-B.Right,A.Height);
Rectange E = new Rectangle(B.X,B.Bottom,B.Width,A.Bottom-A.Bottom);
Rectange F = new Rectangle(B.X,A.Y,B.Width,B.Y-A.Y);

, это .NET, я не уверен насчет языка вашего кода, но я думаю, что большинство структур выглядят симулированными на разных языках.NET конструктор System.Drawing.Rectangle is (X, Y, Ширина, Высота)

0 голосов
/ 01 февраля 2010

Предполагая, что B полностью содержится в A, это будет что-то вроде:

Rectangle[] GetSurrounding( Rectangle outer, Rectangle inner )
{
   Rectangle left, top, right, bottom; // Initialize all of these...
   left = new Rectangle( outer.Left, outer.Top, outer.Height, inner.Left - outer.Left );
   top  = new Rectangle( inner.Left, outer.Top, inner.Top - outer.Top, inner.Width );
   // So on and so forth...

   return new Rectangle[]{ left, top, right, bottom };
}

//  This assumes:
Rectangle( x , y , height, width ); // Constructor

Кроме того, при выборе погодных условий вы растягиваете левый и правый прямоугольники на всю высоту, а верхний и нижний прямоугольники на всю ширину - произвольно, и вам нужно будет либо принять постоянное решение, либо указать параметр метода. В других случаях, когда прямоугольники частично перекрываются, потребуется больше логики, глядя на значения MAX / MIN для проверки выхода за пределы и т. Д.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...