Уточнения: Фигура может начинаться из любой точки (не обязательно из x = 1 и y = 1).
Вид фигур (треугольник, прямоугольник и тд.) неизвестен.
Фигуры не имеют самопересечений/дыр, только 1 внутренняя область.
Положительные целые числа координат могут использоваться чтобы заключить, что входные данные неверны.
4/8-соединение — на Ваше усмотрение (описать выбор в ту или иную пользу).
Строгих ограничений по времени и памяти нет.
Cоставить уравнение прямой проходящей через две точки.
ax + by + c = 0
и если подставишь координаты точек лежащих по обе стороны этой прямой, то
выражение будет для одной точки отрицательным для другой положительным (или наоборот), или ноль.
Здравствуйте, Mr WeL, Вы писали:
MW>для точек лежащих внутри 2д фигуры, значение всех выражение pi (i=1..4) будет одного знака
Только для выпуклых многоугольников. И только при "правильном" выборе направлений прямых (направлений ортогональных векторов внутрь).
Для невыпуклых фигур так не получится.
Re: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, m1st, Вы писали:
M>Подскажите, куда копать?
В общих чертах:
0. Представить, что ты работаешь с чёрным изображением. То есть значение всех точек равно 0.
1. Значению всех точек контура присвоить 1.
2. Любым методом найти хотя бы одну точку, лежащую внутри контура. Пометить её 2.
3. Рекурсивно помечать 2 все лежащие рядом точки, которые не являются контуром.
4. Посчитать количество двоек на изображении.
Можно обратный метод, который, возможно, будет быстрей. Пометить двойкой любую НЕ лежащую внутри контура точку и произвести рекурсивную закраску двойками внешней области. После считать число нулевых точек.
M>Подскажите, куда копать?
1. Берешь две соседние точки на контуре.
2. Выбираешь произвольное направление.
3. Определяешь справа или слева (в соотв. с выбранным направлением) лежит заданная внутренняя точка относительно прямой, соединяющей эти две точки на контуре.
4. Идешь по контуру в выбранном направлении и считаешь-помечаешь точки с той стороны, с которой лежит заданная внутренняя точка.
5. Повторяешь пп. 1 и 4 для нового контура из только что помеченных точек пока не останется точек внутри контура.
Наивное решение — floodfill.
Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Если линейный размер исходного многоугольника принять равным D, то временная сложность floodfill (и прочих модификаций, уже предложенные в этой теме) будет Ω(ND+D²), а сложность с использованием теоремы Пика — O(NlogD) времени и O(1) памяти.
Судя по всему, эта задача — по мотивам древних ДОС'овских времён, когда все полигоны рисовались только на растрах. На это указывает наличие внутренней точки в задании.
В данном случае логично будет взять любой метод заливки растрового полигона, ограниченного пикселами заданного цвета, начиная от указанной точки. Попадёт точка снаружи полигона — зальётся всё окружающее пространство, кроме полигона, попадёт внутрь — зальётся внутренняя полость. Отслеживать уже залитые пикселы (их число), думаю, особых трудностей не представит. Найти алгоритм заливки растрового полигона по внутренней точке — тоже.
P.S. Лет 30 назад этим бредили по ночам серьёзные разработчики важных машин с дисплейными процессорами, обрабатывавшими полный телевизионный кадр за 1 такт видеопотока :o)
Re: Найти количество точек лежащих внутри 2D фигуры
Фигура может начинаться из любой точки (не обязательно из x = 1 и y = 1).
Вид фигур (треугольник, прямоугольник и тд.) неизвестен.
Фигуры не имеют самопересечений/дыр, только 1 внутренняя область.
Положительные целые числа координат могут использоваться чтобы заключить, что входные данные неверны.
4/8-соединение — на Ваше усмотрение (описать выбор в ту или иную пользу).
Строгих ограничений по времени и памяти нет.
Re[2]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, andyp, Вы писали: A>PS Не понял, что функция возвращать должна.
Функция должна возвращать кол-во пикселей(точек), которые лежат внутри 2D фигуры.
A>собственно, вот и решение на Java A>http://grafika.me/node/175
Это решение на "HTML + JavaScript"
Re[2]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, Nuzhny, Вы писали: N>2. Любым методом найти хотя бы одну точку, лежащую внутри контура. Пометить её 2.
В условии нам дается точка, которая лежит внутри контура.
N>Можно обратный метод, который, возможно, будет быстрей. Пометить двойкой любую НЕ лежащую внутри контура точку и произвести рекурсивную закраску двойками внешней области. После считать число нулевых точек.
Для 2х приведенных примеров фигур такой метод явно будет не быстрее.
Re[2]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, Muxa, Вы писали: M>1. Берешь две соседние точки на контуре. M>2. Выбираешь произвольное направление. M>3. Определяешь справа или слева (в соотв. с выбранным направлением) лежит заданная внутренняя точка относительно прямой, соединяющей эти две точки на контуре. M>4. Идешь по контуру в выбранном направлении и считаешь-помечаешь точки с той стороны, с которой лежит заданная внутренняя точка. M>5. Повторяешь пп. 1 и 4 для нового контура из только что помеченных точек пока не останется точек внутри контура.
Спасибо. Проще говоря — "Flood fill".
Здравствуйте, watchmaker, Вы писали: W>Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Можно подробнее?
Формула Пика (или теорема Пика) — классический результат комбинаторной геометрии и геометрии чисел.
Площадь многоугольника с целочисленными вершинами[1] равна
В + Г/2 − 1,
где В есть количество целочисленных точек внутри многоугольника, а Г — количество целочисленных точек на границе многоугольника.
1. Точка координатной плоскости называется целочисленной, если обе её координаты целые.
Здравствуйте, Географ, Вы писали: Г>P.S. Лет 30 назад этим бредили по ночам серьёзные разработчики важных машин с дисплейными процессорами, обрабатывавшими полный телевизионный кадр за 1 такт видеопотока :o)
Как раз отметим? 30 лет первой Mac OS — которая хранит координаты во float. ж)
Re[3]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, m1st, Вы писали:
M>Здравствуйте, watchmaker, Вы писали: W>>Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика. M>Можно подробнее?
А что именно не ясно?
Есть равенство В + Г/2 − 1 = П. В нём В — это что тебе по условию задачи требуется найти. Если перенести слагаемые из одной части уравнения в другую, то получится В = -Г/2 + 1 + П — собственно всё, осталось только сложить три числа :)
Ориентированная площадь считается за один проход по точкам. Обычная площадь — её модуль.
Число точек на границе считается для каждого отрезка, коих N, например, алгоритмом Евклида. Что, если сильно не повезёт, в худшем случае будет работать за логарифмическое время от его длины.
Re[4]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, watchmaker, Вы писали: W>Есть равенство В + Г/2 − 1 = П. В нём В — это что тебе по условию задачи требуется найти. Если перенести слагаемые из одной части уравнения в другую, то получится В = -Г/2 + 1 + П — собственно всё, осталось только сложить три числа W>Ориентированная площадь считается за один проход по точкам. Обычная площадь — её модуль. W>Число точек на границе считается для каждого отрезка, коих N, например, алгоритмом Евклида. Что, если сильно не повезёт, в худшем случае будет работать за логарифмическое время от его длины.
Спасибо!
Как я понимаю, "Число точек на границе" можно не вычислять, т.к. нам уже даны все координаты, которые полностью описывают границы фигуры.
Re[3]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, m1st, Вы писали:
M>Как я понимаю, "Число точек на границе" можно не вычислять, т.к. нам уже даны все координаты, которые полностью описывают границы фигуры.
Ах, точно, я невнимательно прочитал условие. Предыдущее решение основывалось на предположении, что входные точки являются вершинами многоугольника, очерчивающего контур интересующей области. Соответственно в этом случае между двумя вершинами может лежать более нуля целочисленных точек.
Впрочем в варианте где даны сразу точки контура их всё равно нужно как-то отфильтровать, например чтобы исключить из них точки не принадлежащие периметру ограниченной области (если во входных данных не запрещён случай толстой границы). В общем в такой постановке задача получается чуть сложнее, так как если входные точки неупорядочены, то сначала нужно сделать ещё один шаг, который соберёт из них какой-то контур. Хотя всё равно этот шаг можно сделать быстрее чем в floodfill, ограничившись исследованиями только периметра, а не всей площади внутренней области. Ну а далее можно либо сразу свести задачу к предыдущей, либо пообъединять алгоритмы чтобы выкинуть всякие проверки невозможных теперь случаев.
