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

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

Для двумерного случая это выглядит так, как будто вы можете построить дерево сегментов, содержащее деревья сегментов, и получить сложность запроса 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

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

Answer 2

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

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