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

Question

Мне нужен алгоритм (желательно на c ++, хотя псевдокод тоже подходит), чтобы найти группу среди групп пикселей, которые имеют минимальное расстояние до одного конкретного пикселя.

Расстояние определяется как сумма расстояний каждогопиксель группы к определенному пикселю, в то время как каждое расстояние равно | x | + | y ​​|координаты.

Если это не достаточно ясно, я постараюсь уточнить вас

Спасибо

Answer 1

Похоже, вы уже знаете, как рассчитать расстояние.

Слишком медленный цикл for?Будет ли ваш цикл N ^ 2?

Если это так, вы можете использовать BSP или Quadtree .Единственная проблема, которую я вижу, это то, что вы пытаетесь провести тест на близость, где они в основном предназначены для тестов на столкновение.Это может все же позволить вам быстрее удалять группы групп.

Что-то, что определенно сработало бы (хотя его эффективность в уменьшении количества ваших вычислений сильно зависит от распределения ваших групп), это просто разделитьмир в равномерно распределенной, малонаселенной сетке.Если группа попадает в несколько разделов вашей сетки, просто добавьте ее в обе записи сетки.Когда вы проводите сравнение, вы выбираете ближайшую запись в сетке и запускаете алгоритм «точка-группа» только для групп в этой записи в сетке.

Answer 2

Обновлено

В первом проекте этого решения вычисляются геометрические (евклидовы) расстояния, когда квестиан ссылается на Манхэттенские расстояния

.проще оптимизировать.

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

2. Для каждого другого пикселя в группе вычислите его смещение (x и y) от основного пикселя.В отличие от манхэттенского расстояния, держите знак этого смещения.

3. Суммируйте все смещения (смещения x и y) в один номер, назовите этот total_offsets.

4. Когда вам нужно расстояниеиз указанного пикселя вычислите расстояние (Манхэттен) для основного пикселя.Умножьте это на количество пикселей и добавьте total_offsets, чтобы получить общее расстояние до Манхэттена.

Шаги 1 - 3 необходимо выполнить только один раз для каждой группы, а затем шаг 4 можно выполнить по мере необходимости.

например,

  Area A consists of 4 pixels: (8, 8), (8, 9), (9, 8) and (9, 9).  

  Declare (8, 9) as primary pixel.  Offsets are   
      (8, 9) --> (8, 8) = (0, -1)  
      (8, 9) --> (9, 8) = (1, -1)  
      (8, 9) --> (9, 9) = (1, 0)  
  total_offset = 0 + -1 + 1 + -1 + 1 + 0   
               = 0  
  num_pixels = 4  

To compute Manhattan distance from pixel (2, 4)

  distance to primary pixel  
  (2, 4) --> (8, 9) = (6, 5)   
                    = 11  
  dist * num_pixels + total_offsets = 11 * 4 + 0
                                    = 44

Чтобы проверить это, мы можем рассчитать длинный путь:

      (2, 4) --> (8, 8) = (6, 4)   
      (2, 4) --> (8, 9) = (6, 5)   
      (2, 4) --> (9, 8) = (7, 4)   
      (2, 4) --> (9, 9) = (7, 5)   

  distance = 6 + 4 + 6 + 5 + 7 + 4 + 7 + 5 
           = 44

Answer 3

Ниже приведен упрощенный пример. Вам понадобится функция «int distance (Точка p1, Точка p2)», чтобы вычислить расстояние (используя любой алгоритм).

Point pxTest = ... // the single pixel to use for distance checking
List<Point> pxGroup = ... // the group of pixels to check

Point pxMin = null; // the pixel with the minimum distance
int iMin = int.MAX; // the minimum distance so far

foreach(Point pxOther in pxGroup)
    if(iMin > distance(pxTest, pxOther))
    {
        iMin = distance(pxTest, pxOther); // this could be cached in the line before as well to save this call
        pxMin = pxOther;
    }

// now pxMin will include the closest point, iMin the distance