Алгоритм поиска многоугольника, окружающего точку — определены только линии

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

Алгоритм:

1. Sort the line segments in order of how close they are to the target point.
   • Henceforth whenever you need to loop over the lines, loop over them in this sorted order
   • Рассматривайте сегменты линий как бесконечные линии при расчете их расстояния от целевой точки.
2. Perform Step 3 with the closest line segment, using the 2nd intersection point along the line in the "counter-clockwise" direction
   • Take "counter-clockwise" to mean the direction that puts the target point on the left side of the line.
   • ПРИМЕЧАНИЕ: мы надеемся, что 1-я точка пересечения — это место, где мы закончим, как только обойдем целевую точку.

3. На новообретенной линии...

   A. Переберите все остальные линии, которые еще не являются частью фигуры, которую вы строите, и найдите их точки пересечения с этой линией
   B. Отсортируйте точки пересечения против часовой стрелки относительно целевой точки.
   

4. Найдите следующую точку пересечения против часовой стрелки на текущей линии. Если это первая точка, которую мы проверяем на этой линии, то «следующая» точка — это точка после точки пересечения, которая привела нас к этой линии.

   О. Если такой точки нет (это может означать, что мы уже проверили все точки на текущей строке), то текущее решение-кандидат недопустимо...

   • Backtrack to the previous line and repeat Step 4 with the next point on that line.
   • Если предыдущей строки нет (т. е. вы находитесь на линии, с которой вы начали рисовать фигуру), Назад и выполните Шаг 2 со следующей ближайшей строкой, начиная новая форма.

   B. Если линия, образующая точку пересечения, не имеет целевой точки с левой стороны (против часовой стрелки), то многоугольник, который она образует, не охватывает целевую точку. Повторите шаг 4 для текущей линии со следующей точкой.
   C. Если линия, образующая точку пересечения, — это линия, с которой вы начали, то мы нашли решение
   Г. Если ничего из вышеперечисленного не верно, выполните Шаг 3 для линии, образующей точку пересечения.

Оптимизация:

1. Если строк меньше 3, решения нет. Не делай никакой работы.
2. You may want to cache the intersection points when you find them so that you don't have to recalculate them
   • If you choose to do this, I recommend using a 2D array
3. I recommend throwing out lines when you know that they aren't part of the solution.
   • Example: if you already tried the line closest to the target point, but it didn't lead to a solution, it doesn't make sense to include that line when finding intersection points on other lines.

Примечания:

• Этот алгоритм проще всего реализовать рекурсивно.
• Вам придется решить, что делать, если целевая точка находится на одной из линий.

Я считаю, что следующий алгоритм будет работать:

1. Если строк меньше 3, выйти. Нет решения.
2. Определите линию, ближайшую к целевой точке. Эта строка гарантированно будет частью решения.
3. Пусть P1 будет перпендикулярной проекцией целевой точки на L1.
4. Find the two intersection points of the other lines with L1 that are nearest to P1 and on opposite sides of it. These two points are guaranteed to be part of the solution.
   • Lets call these points P2 & P3, and call the lines L2 and L3
   • Если таких точек нет, решения нет.
5. Найдите ближайшую точку на каждой из L2 и L3, которые находятся ближе всего к P2 и P3 соответственно и находятся на той же стороне L1, что и целевая точка.
6. Repeat steps 4 and 5 until:
   • The line found coming from both directions is the same line
   • Найденная точка пересечения, идущая с обоих направлений, является одной и той же точкой
   • Точки, соответствующие критериям, не найдены. Это означает, что решения нет.