Проверьте, проходит ли Круг через лабиринт в не квантованном 2-мерном пространстве. - PullRequest
Новая
       67

Проверьте, проходит ли Круг через лабиринт в не квантованном 2-мерном пространстве.

2 голосов
/ 14 апреля 2020

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

Учитывая лабиринт, заключенный в область 100x100, определите, есть ли круг с заданным радиусом может пройти через лабиринт с учетом расположения всех стен. Стены будут определены как линии, соединяющие две точки в пространстве, и вам будут даны начальная и конечная точки круга. Круг должен начинаться с его центра в начальной точке и касаться конечной точки, чтобы он успешно прошел через лабиринт. Там будет максимум 20 стен. Радиус круга и расположение стенок могут быть «произвольно» точными. («произвольно» для этого случая означает просто в дальних пределах - скажем, максимум до 10 цифр после десятичной дроби).

Вот пример. Если бы это был ввод: 

Radius = 2.8
Start = (5,5), Destination = (95,95)
Walls (a wall connects each pair of points):
(20,0) to (27.5,22.6)
(27.5,22.6) to (55.1,35.5)
(55.1,35.5) to (80.3,80,4)
(80.3,80,4) to (95,63.9)
(1.7,25.8) to (17.5,53.2)
(17.5,53.2) to (56.4,69)
(56.4,69) to (67.9,90.6)
(85.6,98.94512) to (87.3,92.5)

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

this

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

Как бы я go о решении этого? Может ли кто-нибудь указать мне алгоритм, ссылку, какой-нибудь псевдокод или просто интуицию, которая поможет мне понять, как я могу решить эту проблему? Любая помощь приветствуется. Спасибо!

Ответы [ 2 ]

2 голосов
/ 14 апреля 2020

Утолщение / перемещение стен на r с каждой стороны, как и в другом ответе (+1 между прочим), звучит просто, но закодировать это не тривиально. Для получения дополнительной информации см.

Направление нормали в 2D легко, если dx,dy является направлением линии, то (-dy,dx) и (dy,-dx) являются нормальными для него ...

Однако я бы посоветовал сделать более медленный, но безопасный и более легкий подход, вычисляя ближайшее расстояние от стены для каждой вершины лабиринта и близкие пути, которые являются ближе чем 2r ...

Примерно так:

preview

Итак:

  1. для каждой вершины
  2. отметьте все линии, которые не принадлежат пути вершины

  3. вычислите перпендикулярное и минимальное расстояние d до линии, и ее вершины используют наименьшее d расстояние, которое может можно легко вычислить:

    просто посмотрите на Perpendicular distance of any point P to AB так: 

    d = min
      (
      perpendicular_distance(line,vertex), 
      |line_vertex1-vertex|, 
      |line_vertex2-vertex| 
      )

    если d<2r закрыть путь. Например, добавив линию, которая присоединяется к стене, она слишком близко к проверенной вершине

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

    split

Как вы можете видеть, это O(n^2) вместо O(n), как в другом ответе, но его грязное доказательство ... расширение полигонов - нет, и в действительности это одна из самых сложных вещей в 2D-геометрии для кодирования (IIR C даже все еще открытая проблема) ...

2 голосов
/ 14 апреля 2020

Это довольно сложная задача, и ее нелегко кодировать, но вот способ, который работает:

Пусть r - радиус круга. Это означает, что центр круга не может пройти в пределах r любого препятствия.

Переместите стены своей области лабиринта на r с каждой стороны.

Заменить каждую конечную точку стены окружностью радиуса r .

Заменить каждую стену прямоугольником ширины 2r .

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

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

Вырежьте сцену по горизонтали на каждом пересечении и по максимуму или минимуму по вертикали, чтобы создать полосы, с каждой полосой, разделенной на области линией или кругом ar c, который проходит через весь путь Это. Регион не соединяет направление с регионами слева и справа, но может соединяться с нулем или несколькими регионами в полосах над и под ним. Связи между регионами образуют график.

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

...