Определите, находится ли точка в объединении прямоугольников.

Question

У меня есть набор параллельных параллельных двухугольников, расположенных по их верхним левым и нижним углам правой руки (все в целых координатах). Учитывая точечный запрос, как вы можете эффективно определить, находится ли он в одном из прямоугольников? Мне просто нужен ответ «да/нет» и не нужно беспокоиться о том, в каком прямоугольнике он находится.

Я могу проверить, есть ли (x, y) ((x1, y1), (x2, y2)) если x находится между x1 и x2, а y находится между y1 и y2. Я могу сделать это отдельно для каждого прямоугольника, который работает в линейном времени по числу прямоугольников. Но поскольку у меня много прямоугольников, и я сделаю много точечных запросов, я бы хотел что-то быстрее.

Answer 1

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

found = false 
for each r in rectangles: 
    if point.x > r.x1 && point.x < r.x2: 
    if point.y > r.y1 && point.y < r.y2 
     found = true 
     break 

Вы можете получить более эффективным путем сортировки прямоугольников в регионах, и, глядя на «ограничивающими прямоугольниками». Затем вы выполняете двоичный поиск через дерево постоянно уменьшающихся ограничивающих прямоугольников. Это занимает немного больше работы, но делает поиск O (ln (n)), а не O (n) - для больших наборов прямоугольников и многих поисков, улучшение производительности будет значительным. Вы можете увидеть версию этого (которая смотрит на пересечение прямоугольника с набором прямоугольников - но вы легко адаптируетесь к «точке внутри») в this earlier answer. В более общем плане, посмотрите на тему quad trees, которые являются именно такой структурой данных, которая вам понадобится для двумерной задачи.

Немного менее эффективный (но более быстрый) метод сортирует прямоугольники в нижнем левом углу (например) - вам тогда нужно искать только подмножество прямоугольников.

Если координаты являются целыми числами, вы можете сделать двоичную маску - тогда поиск является одной операцией (в вашем случае для этого потребуется таблица поиска 512 МБ). Если ваше пространство относительно малонаселено (т. Е. Вероятность «промаха» достаточно велика), вы могли бы рассмотреть возможность использования недокадровой битовой карты (например, используя координаты/8), - тогда размер карты уменьшится до 8 М, а если у вас есть «нет» хит ", вы сэкономите себя на счет более пристального изучения. Конечно, вы должны округлить левый/нижний и округлить верхние/правые координаты, чтобы сделать эту работу правильной.

Расширение немного с примером:

Imagine координаты могут быть только 0 - 15 х, и 0 - 7 у. Есть три прямоугольника (все [x1 y1 x2 y2]:. [2 3 4 5], [3 4 6 7] и [7 1 10 5] Мы можем сделать это в матрице (я отмечаю нижний левый угол с номером прямоугольника - обратите внимание, что 1 и 2 перекрытия):

...xxxx......... 
...xxxx......... 
..xxxxx......... 
..x2xxxxxxx..... 
..1xx..xxxx..... 
.......xxxx..... 
.......3xxx..... 
................ 

Вы можете превратить это в массив нулей и единиц - так что «есть ли прямоугольник в этой точке» - это то же самое, что «этот бит установлен». Один поиск даст вам ответ. Чтобы сэкономить место, вы можете уменьшить размер массив - если по-прежнему нет удара, у вас есть свой ответ, но если есть удар, вам нужно будет проверить «это реально» - поэтому он экономит меньше времени, а экономия зависит от разреженности вашей матрицы (sparser = faster). Подвыборный массив будет выглядеть следующим образом (2x понижающая дискретизация):

.oxx.... 
.xxooo.. 
.oooxo.. 
...ooo.. 

Я использую x, чтобы отметить «если вы нажмете эту точку, вы уверены, что в прямоугольнике», и o сказать «некоторые из них прямоугольник». Многие из пунктов теперь «возможно», и меньше времени сохраняется. Если вы сделали более серьезную понижающую дискретизацию, вы можете подумать о наличии двухбитовой маски: это позволит вам сказать, что «весь этот блок заполнен прямоугольниками» (т.- дальнейшая обработка не требуется: x выше) или «дополнительная обработка необходима» (например, o выше). Это скоро начинает усложняться, чем подход Q-дерева ...

Нижняя линия: чем больше сортировка/организация прямоугольников вы делаете спереди, тем быстрее вы можете выполнять поиск.

Answer 2

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

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

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

Следующий подход в C# и нуждается в адаптации к предпочитаемому языку:

public class RectangleUnion 
{ 
    private readonly Dictionary<int, Dictionary<int, Dictionary<int, HashSet<int>>>> coordinates = 
     new Dictionary<int, Dictionary<int, Dictionary<int, HashSet<int>>>>(); 

    public void Add(Rectangle rect) 
    { 
     Dictionary<int, Dictionary<int, HashSet<int>>> verticalMap; 

     if (coordinates.TryGetValue(rect.Left, out verticalMap)) 
      AddVertical(rect, verticalMap); 
     else 
      coordinates.Add(rect.Left, CreateVerticalMap(rect)); 
    } 

    public bool IsInUnion(Point point) 
    { 
     foreach (var left in coordinates) 
     { 
      if (point.X < left.Key) continue; 

      foreach (var right in left.Value) 
      { 
       if (right.Key < point.X) continue; 

       foreach (var top in right.Value) 
       { 
        if (point.Y < top.Key) continue; 

        foreach (var bottom in top.Value) 
        { 
         if (point.Y > bottom) continue; 

         return true; 
        } 
       } 
      } 
     } 

     return false; 
    } 

    private static void AddVertical(Rectangle rect, 
     IDictionary<int, Dictionary<int, HashSet<int>>> verticalMap) 
    { 
     Dictionary<int, HashSet<int>> bottomMap; 
     if (verticalMap.TryGetValue(rect.Right, out bottomMap)) 
      AddBottom(rect, bottomMap); 
     else 
      verticalMap.Add(rect.Right, CreateBottomMap(rect)); 
    } 

    private static void AddBottom(
     Rectangle rect, 
     IDictionary<int, HashSet<int>> bottomMap) 
    { 
     HashSet<int> bottomList; 
     if (bottomMap.TryGetValue(rect.Top, out bottomList)) 
      bottomList.Add(rect.Bottom); 
     else 
      bottomMap.Add(rect.Top, new HashSet<int> { rect.Bottom }); 
    } 

    private static Dictionary<int, Dictionary<int, HashSet<int>>> CreateVerticalMap(
     Rectangle rect) 
    { 
     var bottomMap = CreateBottomMap(rect); 
     return new Dictionary<int, Dictionary<int, HashSet<int>>> 
        { 
         { rect.Right, bottomMap } 
        }; 
    } 

    private static Dictionary<int, HashSet<int>> CreateBottomMap(Rectangle rect) 
    { 
     var bottomList = new HashSet<int> { rect.Bottom }; 
     return new Dictionary<int, HashSet<int>> 
        { 
         { rect.Top, bottomList } 
        }; 
    } 
} 

Это не красиво, но должен направить вас в правильном направлении.

Answer 3

Моей любимой для различных 2D-геометрийных запросов является Sweep Line Algorithm. Он широко используется в программном обеспечении САПР, что было бы моей дикой догадкой для вашей программы.

В принципе, вы упорядочиваете все точки и все вершины многоугольников (все 4 прямоугольника в вашем случае) вдоль оси X и продвигаетесь по оси X от одной точки к другой. В случае не-манхэттенских геометрий вы также вводите промежуточные точки, пересечения сегментов.

Структура данных представляет собой сбалансированное дерево точек и многоугольных (прямоугольных) кросс-пересечений с вертикальной линией в текущем X-положении, упорядоченное по Y-направлению. Если структура должным образом поддерживается, очень легко определить, находится ли точка в текущей X-позиции в прямоугольнике или нет: просто изучите Y-ориентацию вертикально смежных с пересечениями ребер точки. Если прямоугольники могут перекрываться или иметь прямоугольные отверстия, это немного сложнее, но все же очень быстро.

Общая сложность для N точек и M прямоугольников - O ((N + M) * log (N + M)). На самом деле можно доказать, что это асимптотически оптимально.