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

Question

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

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

Как я могу определить, создает ли кривая пользователей какую-либо замкнутую фигуру? Например, если вы размыли глаза и посмотрите на рисунки ниже («.» Обозначает точки на кривой, «0» обозначает точки не на кривой), первый создает замкнутое пространство, второй не .

0000000000000000
0000..0000000000
000.00.000000000
00.000.000000000
00.00.0000000000
000...0000000000
0000000000000000

000.000000000000
0000.00000000000
00000.0000000000
00000...00000000
0000000.00000000
00000000.0000000
0000000000000000

Дополнительно , учитывая некоторую точку (x1, y1), как я могу определить, находится ли эта точка внутри или снаружи замкнутого пространства?

Answer 1

На ваш второй вопрос:

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

Answer 2

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

Answer 3

1) Чтобы определить, образует ли путь петлю, вы можете преобразовать ваши точки в график. Вам необходимо определить собственную эвристику, чтобы определить, какие точки связаны ребром (например, все смежные точки могут быть определены как соединенные ребром. Или, если ваши точки генерируются в определенном порядке, то последовательные точки может быть соединен ребром). Как только у вас будет свой график, вы можете поискать алгоритм обнаружения циклов в Google.

2) Чтобы определить, какие точки заключены, вы можете взять точки, составляющие петлю, и использовать их для определения многоугольника. Затем найдите в Google алгоритм «точка в многоугольнике» и протестируйте все точки в определенном диапазоне.