История изменений
Исправление
no-dashi,
(текущая версия)
:
Простейший способ определить находится ли точка внутри полигона - определить входит ли точка хотя бы в один треугольник, из которых сложен полигон. Детская задача разложения полигона на треугольники, пишется за вечер, аричметическая сложность в среднем O(N) где N - количество отрезков в контуре.
Ещё более простой вариант - построить из точки произвольный луч, и решить задачу пересечения луча и отрезков, из которых складывается контур (решить N систем линейных уравнений, где N - количество отрезков в контуре). Если пересекается четное количество отрезков - вне полигона, если нечетное - в полигоне.
Второй вариант легко адаптируется к случаю, когда вместо отрезков используются уравнения кривых, только решать придется не систему линейных, чуть более сложных уравнений.
Исправление
no-dashi,
:
Простейший способ определить находится ли точка внутри полигона - определить входит ли точка хотя бы в один треугольник, из которых сложен полигон. Детская задача разложения полигона на треугольники, пишется за вечер, аричметическая сложность в среднем O(N) где N - количество отрезков в контуре.
Ещё более простой вариант - построить из точки произвольный луч, и решить задачу пересечения луча и отрезков, из которых складывается контур (решить N систем линейных уравнений, где N - количество отрезков в контуре).
Второй вариант легко адаптируется к случаю, когда вместо отрезков используются уравнения кривых, только решать придется не систему линейных, чуть более сложных уравнений.
Исходная версия
no-dashi,
:
Простейший способ определить находится ли точка внутри полигона - определить входит ли точка хотя бы в один треугольник, из которых сложен полигон. Детская задача разложения полигона на контуры, пишется за вечер, аричметическая сложность в среднем O(N) где N - количество отрезков в контуре.
Ещё более простой вариант - построить из точки произвольный луч, и решить задачу пересечения луча и отрезков, из которых складывается контур (решить N систем линейных уравнений, где N - количество отрезков в контуре).
Второй вариант легко адаптируется к случаю, когда вместо отрезков используются уравнения кривых, только решать придется не систему линейных, чуть более сложных уравнений.