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

Question

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

Чтобы уточнить далее: если у вас есть сетка 1000 x 1000 и случайным образом размещены в ней 100 точек, как вы можете доказать, что любая одна точка находится в пределах 100 единиц от соседа, и что все точки доступны при переходе от одной точки к другой?

Я написал некоторый код и столкнулся с интересной проблемой: очень редко (только один раз) он создает остров точек, который превышает максимальный диапазон от остальных точек. Мне нужно решить эту проблему, но грубая сила не является ответом.

Это написано на Java, но я хорош как с псевдокодом, так и с C ++.

Answer 1

Мне нравится конструкторский подход @ 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, повторяя следующее, пока действительный <code>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 действительно, если оно находится внутри общей действительной сетки.

Answer 2

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

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

Из этого следует, что вы можете проверить ваше состояние следующим образом:

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

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

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

Answer 3

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

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

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

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

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

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

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 единиц от предыдущей точки, поэтому требование пути сохраняется. Однако ограничения по горизонтальному и вертикальному перемещению вынуждают генерацию точек случайным образом «проходить» по всему пространству, создавая более полную дисперсию, чем исходный алгоритм чистого «обхода пьяницы».

Answer 4

Что касается оценки существующих наборов точек, то это похоже на проблему евклидова минимального остовного дерева . На странице википедии говорится, что это подграф триангуляции Делоне ; поэтому я думаю, что было бы достаточно вычислить триангуляцию Делоне (см. предыдущую ссылку или 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. Decrement 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 </li>
6. Инкремент i. Если я == N, остановка с успехом .
7. Если P [i] .x-P [j] .x <= R, перейти к шагу 10. (это автоматически выполняется, если i == j) </li>
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 [я].
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] недоступен ни по одному из предыдущих пунктов. Останов с ошибкой.

Answer 5

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

Answer 6

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

Например, вы знаете, что у вас есть 100 случайных точек, и каждый патч содержит количество содержащихся в них точек, вы можете просто подвести итог и посмотреть, действительно ли это 100 & mdash; что означает, что все точки достижимы.

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

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

Answer 7

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

1. Случайно расположите начальную точку.

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

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

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

   2,3. Произвольно выберите y-координату в этом диапазоне.

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

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

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