Связанные точки в сетке

Небольшая мысль: если вы разделите сетку на патчи 50x50 и разместите начальные точки, вы также запишете, к какому патчу они принадлежат. Теперь, когда вы хотите проверить, находится ли новая точка в пределах 100 пикселей от других, вы можете просто проверить патч плюс 8 окружающих его и посмотреть, совпадают ли подсчеты точек.

Например, вы знаете, что у вас есть 100 случайных точек, и каждый патч содержит количество точек, которые они содержат, вы можете просто просуммировать и посмотреть, действительно ли оно 100 - что означает, что все точки достижимы.

Я уверен, что есть и другие способы, трудные.

Обновлено: расстояние от верхней левой точки до нижнего правого угла патча 50x50 составляет sqrt (50 ^ 2 + 50 ^ 2) = 70 точек, поэтому вам, вероятно, придется выбрать меньший размер патча. Может быть, 35 или 36 (50 ^ 2 = sqrt (x ^ 2 + x ^ 2) => x = 35.355 ...).

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

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

1. Произвольно разместите начальную точку.

2. Повторите эти действия для оставшегося количества точек (например, 99):

   2.1. Произвольно выберите координату x в некотором диапазоне (например, 90) от предыдущей точки.

   2.2. Вычислите допустимый диапазон для координаты y, который будет в пределах 100 единиц от предыдущей точки.

   2.3. Произвольно выберите координату Y в этом диапазоне.

3. Если вы хотите полностью скрыть начало координат, отсортируйте точки по их координатной паре.

Это не потребует больших накладных расходов по сравнению с чистой случайностью, но гарантирует, что каждая точка находится в пределах 100 единиц от хотя бы одной другой точки (фактически, за исключением первой и последней, каждая точка будет в пределах 100 единиц от других точек два).

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

Мне нравится подход к строительству @ joel.neely, но если вы хотите обеспечить более однородную плотность, это с большей вероятностью сработает (хотя это, вероятно, даст больше кластера, чем общую однородную плотность):

1. Случайным образом разместите начальную точку P_0, выбрав x, y из равномерного распределения в допустимой сетке.
2. Для i = 1: N-1
   1. Выберите случайный j = равномерно распределенный от 0 до i-1, определите точку P_j, которая была размещена ранее
   2. Выберите случайную точку P_i, где расстояние (P_i, P_j) <100, повторяя следующее до тех пор, пока действительный P_i не будет выбран в подшаге 4 ниже:
      1. Выберите (dx, dy), каждый из которых равномерно распределен от -100 до +100
      2. Если dx ^ 2 + dy ^ 2> 100 ^ 2, расстояние слишком велико (сбой в 21,5% случаев), вернитесь к предыдущему шагу.
      3. Рассчитайте кандидатные координаты (P_i) = координаты (P_j) + (dx, dy).
      4. P_i действителен, если он находится внутри общей действующей сетки.

Что касается оценки существующих наборов точек, это похоже на проблему типа Евклидово минимальное остовное дерево. На странице википедии указано, что это подграф Триангуляция Делоне; поэтому я думаю, что было бы достаточно вычислить триангуляцию Делоне (см. предыдущую ссылку или "вычислительную геометрию" Google), а затем минимальное остовное дерево и убедиться, что все ребра имеют длину меньше 100.

Из чтения ссылок видно, что это O (N log N), возможно, есть более быстрый способ, но этого достаточно.

Более простой (но, вероятно, менее эффективный) алгоритм будет примерно таким:

1. Дано: точки находятся в массиве от индекса 0 до N-1.
2. Отсортируйте точки в порядке x-координат, который равен O (N log N) для эффективной сортировки.
3. Инициализировать i = 0.
4. Приращение i. Если i == N, остановись с успехом. (все точки могут быть достигнуты из другой с радиусом R)
5. Инициализировать j = i.
6. Уменьшение j.
7. Если j<0 или P[i].x - P[j].x > R, Остановитесь на неудаче. (есть разрыв и все точки не могут быть достигнуты друг от друга с радиусом R)
8. В противном случае мы попадаем сюда, если P [i] .x и P [j] .x находятся в пределах R друг от друга. Проверьте, находится ли точка P [j] достаточно близко к P [i]: если (P[i].x-P[j].x)^2 + (P[i].y-P[j].y)^2 < R ^ 2`, то точка P [i] достижима одной из предыдущих точек в пределах радиуса R, и вернитесь к шагу 4.
9. Продолжайте попытки: вернитесь к шагу 6.

Обновлено: это можно изменить на что-то, что должен будет O (N log N), но я не уверен:

1. Дано: точки находятся в массиве от индекса 0 до N-1.
2. Отсортируйте точки в порядке x-координат, который равен O (N log N) для эффективной сортировки.
3. Поддерживайте отсортированный набор YLIST точек в порядке координат y, инициализируя YLIST набором {P [0]}. Мы будем перемещать координату x слева направо, добавляя точки одну за другой в YLIST и удаляя точки, у которых координата x находится слишком далеко от вновь добавленной точки.
4. Инициализировать i = 0, j = 0.
5. Инвариант цикла всегда истинен в этой точке: все точки P [k], где k <= i, образуют сеть, в которой они могут быть достигнуты друг от друга с радиусом R. Все точки в YLIST имеют координаты x, которые находятся между P [i]. xR и P [i] .x
6. Приращение i. Если i == N, остановись с успехом.
7. Если P [i] .x-P [j] .x <= R, перейдите к шагу 10. (это автоматически верно, если i == j)
8. Точка P [j] недостижима из точки P [i] с радиусом R. Удалите P [j] из YLIST (это O (log N)).
9. Приращение j, переходите к шагу 6.
10. В этот момент все точки P [j] с j<i и координатами x между P [i] .x-R и P [i] .x находятся в наборе YLIST.
11. Добавьте P [i] в ​​YLIST (это O (log N)) и запомните индекс k в YLIST, где YLIST [k] == P [i].
12. Точки YLIST [k-1] и YLIST [k + 1] (если они существуют; P [i] может быть единственным элементом в YLIST или может быть на крайнем конце) являются ближайшими точками в YLIST к P [i] .
13. Если точка YLIST [k-1] существует и находится в пределах радиуса R от P [i], то P [i] достижима с радиусом R по крайней мере из одной из предыдущих точек. Переходите к шагу 5.
14. Если точка YLIST [k + 1] существует и находится в пределах радиуса R от P [i], то P [i] достижима с радиусом R по крайней мере из одной из предыдущих точек. Переходите к шагу 5.
15. P [i] недоступен ни из одной из предыдущих точек. Остановитесь на неудаче.

Новый и улучшенный ;-)

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

Гийом заметил, что ранее опубликованная мною стратегия потеряла бы равномерную плотность. Конечно, он прав, потому что это, по сути, «прогулка пьяницы», которая имеет тенденцию вращаться вокруг исходной точки. Однако равномерное случайное размещение точек дает значительную вероятность невыполнения требования «пути» (все точки могут быть соединены путем с шагом не более 100). Проверка на это состояние стоит дорого; генерирование чисто случайных решений до тех пор, пока не будет пройдено, тем более.

Джейсон С. предложил вариант, но статистическое тестирование на большом количестве симуляций привело меня к выводу, что его вариант дает модели, которые так же сгруппированы, как и те, что были в моем первом предложении (на основе изучения среднего и стандартного отклонения значений координат).

Пересмотренный алгоритм ниже создает наборы точек, характеристики которых очень похожи на характеристики чисто (равномерного) случайного размещения, но которые гарантируются конструкцией, чтобы удовлетворить требованию пути. К сожалению, это немного легче визуализировать, чем объяснять устно. Фактически, для этого требуется, чтобы точки случайным образом колебались в неопределенно согласованном направлении (северо-восток, юго-восток, юго-запад, северо-запад), изменяя направление только при "отскоке от стены".

Вот общий обзор:

1. Выберите случайным образом начальную точку, установите горизонтальное перемещение ВПРАВО и вертикальное перемещение ВНИЗ.

2. Повторите эти действия для оставшегося количества точек (например, 99 в исходной спецификации):

   2.1. Случайным образом выберите dx и dy, расстояние между которыми составляет от 50 до 100. (Я предположил, что евклидово расстояние - квадратный корень из сумм квадратов - в моей пробной реализации, но расстояние «такси» - сумма абсолютных значений - было бы еще проще. кодировать.)

   2.2. Примените dx и dy к предыдущей точке на основе горизонтального и вертикального перемещения (ВПРАВО / ВНИЗ -> добавить, ВЛЕВО / ВВЕРХ -> вычесть).

   2.3. Если какая-либо координата выходит за границы (менее 0 или не менее 1000), отразите эту координату вокруг нарушенной границы и замените ее перемещение на противоположное направление. Это означает четыре случая (2 координаты x 2 границы):

   2.3.1. if x < 0, then x = -x and reverse LEFT/RIGHT horizontal travel.
   2.3.2. if 1000 <= x, then x = 1999 - x and reverse LEFT/RIGHT horizontal travel.
   2.3.3. if y < 0, then y = -y and reverse UP/DOWN vertical travel.
   2.3.4. if 1000 <= y, then y = 1999 - y and reverse UP/DOWN vertical travel.
   

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

Если я правильно понимаю вашу проблему, учитывая набор сайтов, вы хотите проверить, находится ли ближайший сосед (для расстояния L1, то есть расстояния по сетке) каждого сайта на расстоянии меньше значения K.

Это легко получить для евклидова расстояния путем вычисления триангуляции Делоне множества точек: ближайший сосед сайта является одним из его соседей в триангуляции Делоне. Интересно, что расстояние L1 больше, чем евклидово расстояние (в пределах коэффициента sqrt (2)).

Отсюда следует, что способ проверки вашего состояния заключается в следующем:

1. вычислить триангуляцию Делоне сайтов
2. для каждого сайта s начните поиск в ширину с s в триангуляции, чтобы вы обнаружили все вершины на евклидовом расстоянии меньше K от s (триангуляция Делоне обладает тем свойством, что набор вершин на расстоянии меньше K от данный сайт связан в триангуляции)
3. для каждого узла s среди этих вершин на расстоянии меньше K от s проверьте, не находится ли какая-либо из них на расстоянии L1 меньше K от s. В противном случае свойство не устраивает.

Этот алгоритм можно улучшить несколькими способами:

1. поиск в ширину на шаге 2, конечно, должен быть остановлен, как только будет обнаружен сайт на расстоянии L1 меньше K.
2. во время поиска допустимого соседа s, если обнаруживается, что узел s 'находится на расстоянии L1 меньше K от s, нет необходимости искать допустимого соседа для s': s, очевидно, является одним из них.
3. полный поиск в ширину не требуется: после посещения всех треугольников, инцидентных s, если ни один из соседей s в триангуляции не является допустимым соседом (то есть сайт на расстоянии L1 меньше K), обозначьте (v₁ ,. .., v_n) соседи. Существует не более четырех ребер (v_i, v_i+1), которые пересекают горизонтальную и вертикальную оси. Поиск следует продолжать только через эти четыре (или менее) ребра. [Это следует из формы сферы L1]