Определение нескольких ближайших пар в плоскости

Можно ли при определении ближайшей пары вершин на плоскости с помощью описанного ниже алгоритма развертки определить несколько пар без дополнительных прогонов?

  1. Сортировка точек по их x-координатам.
  2. Разделите набор точек на два подмножества одинакового размера вертикальной линией x=xmid. Решить задачу рекурсивно в левом и правом подмножествах. Это дает левосторонние и правосторонние минимальные расстояния dLmin и dRmin соответственно.
  3. Найти минимальное расстояние dLRmin среди множества пар точек, у которых одна точка лежит слева от разделяющей вертикали, а другая — справа.
  4. Окончательный ответ — это минимум среди dLmin, dRmin и dLRmin.

algorithm geometry plane closest-points proof
person jbenett    schedule 13.11.2017    source источник
comment
Пожалуйста, добавьте несколько фрагментов кода, которые вы пробовали.   -  person Adhikari Bishwash    schedule 13.11.2017

Ответы (2)


arrow_upward
0
arrow_downward

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

AllPairsMinDist(points[1...n])
    sort points according to x coordinate
    return AllPairsMinDistInternal(points[1...n])

AllPairsMinDistInternal(points[1...n])
    if n = 1 then
        return (+infinity, [])
    else if n = 2 then
        d = distance(points[1], points[2])
        c = (points[1], points[2])
        return (d, c)
    else then
        (dL, cL) = AllPairsMinDistInternal(points[1...floor(n/2)])
        (dR, cR) = AllPairsMinDistInternal(points[floor(n/2)+1...n])
        (dM, cM) = PairsMinDistMiddle(points[1...n], dL, dR)
        dMin = min(dL, dR, dM)
        cMin = []
        if dL = dMin then cMin = cMin union cL
        if dR = dMin then cMin = cMin union cR
        if dM = dMin then cMin = cMin union cM
        return (dMin, cMin)

AllPairsMinDistMiddle(points[1...n], dL, dR)
    if n = 1 then
        return (+infinity, [])
    else if n = 2 then
        d = distance(points[1], points[2])
        c = (points[1], points[2])
        return (d, c)
    else then
        xV = (points[floor(n/2)].x + points[floor(n/2)+1].x) / 2

        minD = min(dL, dR)
        minC = []

        ll = binary search for index of point with smallest
             x coordinate satisfying xV - x <= minD

        rr = binary search for index of point with largest
             x coordinate satisfying x - xV <= minD

        for i = ll to floor(n/2) do
            for j = floor(n/2) + 1 to rr do
                d = distance(points[i], points[j])
                if d = minD then
                    minC = minC union [(points[i], points[j])]
                else if d < minD then
                    minD = d
                    minC = [(points[i], points[j])]

        alternative to for loop:
            (dMin, cMin) = AllPairsMinDistInternal(points[ll...rr])

        return (dMin, cMin)

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

person Patrick87    schedule 13.11.2017

arrow_upward
0
arrow_downward

Вам нужно сохранить одинаковые ближайшие пары в отдельном списке.

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

Если короче, очистите список.

Если они равны, добавьте к списку (возможно, обе пары).

Использование хранилища с постоянным временем не ухудшит сложность алгоритма.

person Yves Daoust    schedule 13.11.2017