Алгоритм поиска набора областей, содержащих ячейку

Question

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

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

Answer 1

Основываясь на некоторых результатах поиска в Google, это пример проблемы поиска в двухмерном точечном корпусе или «проблема колоть». См:

http://www.cs.nthu.edu.tw/~wkhon/ds/ds10/tutorial/tutorial6.pdf

отсюда (начиная с стр.21/52):

http://www.cs.brown.edu/courses/cs252/misc/slides/orthsearch.pdf

Ключевая структура данных участвуют в дерево сегмент:

http://en.wikipedia.org/wiki/Segment_tree

Для 2-D случая, похоже, вы можете построить дерево сегментов, содержащее деревья сегментов, и g et O (log^2 (n)) сложности запросов. (Я думаю, что ваше текущее решение - O (n), поскольку в среднем вы просто исключаете половину ваших регионов с помощью бинарного поиска.)

Однако вы сказали «электронная таблица», что означает, что вы, вероятно, небольшая область для работы. Что еще более важно, у вас есть целые координаты. И вы сказали «быстрее», что означает, что вы, вероятно, готовы торговать пространством и настроить время для более быстрого запроса.

Вы не сказали, какая таблица, но код ниже - это дико неэффективная, но простая в использовании, грубая силовая реализация Excel/VBA двухмерной таблицы поиска, которая после установки имеет O (1) сложность запроса:

Public Sub brutishButShort() 
    Dim posns(1 To 65536, 1 To 256) As Collection 

    Dim regions As Collection 
    Set regions = New Collection 

    Call regions.Add([q42:z99]) 
    Call regions.Add([a1:s100]) 
    Call regions.Add([r45]) 

    Dim rng As Range 
    Dim cell As Range 
    Dim r As Long 
    Dim c As Long 

    For Each rng In regions 
     For Each cell In rng 
      r = cell.Row 
      c = cell.Column 

      If posns(r, c) Is Nothing Then 
       Set posns(r, c) = New Collection 
      End If 

      Call posns(r, c).Add(rng) 
     Next cell 
    Next rng 

    Dim query As Range 
    Set query = [r45] 

    If Not posns(query.Row, query.Column) Is Nothing Then 
     Dim result As Range 
     For Each result In posns(query.Row, query.Column) 
      Debug.Print result.address 
     Next result 
    End If 
End Sub 

Если у вас есть большие сетки, чтобы беспокоиться о том или регионах, которые являются большими по отношению к сетке, вы можете сэкономить массу пространства и установки времени с помощью двух поисковых таблиц 1-D вместо , Тем не менее, тогда у вас есть два подхода, а также необходимость пересечения двух результирующих множеств.

Answer 2

Я думаю, что вы хотите, чтобы определить, является ли Intersect клетки и область не является Ничто

Sub RegionsContainingCell(rCell As Range, ParamArray vRegions() As Variant) 

    Dim i As Long 

    For i = LBound(vRegions) To UBound(vRegions) 
     If TypeName(vRegions(i)) = "Range" Then 
      If Not Intersect(rCell, vRegions(i)) Is Nothing Then 
       Debug.Print vRegions(i).Address 
      End If 
     End If 
    Next i 

End Sub 

Sub test() 

    RegionsContainingCell Range("B50"), Range("A1:Z100"), Range("C2:C10"), Range("B1:B70"), Range("A1:C30") 

End Sub