Сообщение Re: Найти количество точек лежащих внутри 2D фигуры от 17.11.2014 11:21
Изменено 17.11.2014 14:17 watchmaker
Здравствуйте, m1st, Вы писали:
M>Подскажите, куда копать?
Наивное решение — floodfill.
Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Если линейный размер исходного многоугольника принять равным D, то временная сложность floodfill (и прочих модификаций, уже предложенные в этой теме) будет Ω(ND+D²), а временная сложность с использованием теоремы Пика — O(NlogD).
M>Подскажите, куда копать?
Наивное решение — floodfill.
Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Если линейный размер исходного многоугольника принять равным D, то временная сложность floodfill (и прочих модификаций, уже предложенные в этой теме) будет Ω(ND+D²), а временная сложность с использованием теоремы Пика — O(NlogD).
Re: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, m1st, Вы писали:
M>Подскажите, куда копать?
Наивное решение — floodfill.
Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Если линейный размер исходного многоугольника принять равным D, то временная сложность floodfill (и прочих модификаций, уже предложенные в этой теме) будет Ω(ND+D²), а сложность с использованием теоремы Пика — O(NlogD) времени и O(1) памяти.
M>Подскажите, куда копать?
Наивное решение — floodfill.
Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Если линейный размер исходного многоугольника принять равным D, то временная сложность floodfill (и прочих модификаций, уже предложенные в этой теме) будет Ω(ND+D²), а сложность с использованием теоремы Пика — O(NlogD) времени и O(1) памяти.