Сообщение Re[5]: Найти количество точек лежащих внутри 2D фигуры от 19.11.2014 12:58
Изменено 19.11.2014 17:41 watchmaker
Здравствуйте, m1st, Вы писали:
M>Как я понимаю, "Число точек на границе" можно не вычислять, т.к. нам уже даны все координаты, которые полностью описывают границы фигуры.
Ах, точно, я невнимательно прочитал условие. Предыдущее решение основывалось на предположении, что выходные точки являются вершинами многоугольника, очерчивающего контур интересующей области. Соответственно в этом случае между двумя вершинами может лежать более нуля целочисленных точек.
Впрочем в варианте где даны сразу точки контура их всё равно нужно как-то отфильтровать, например чтобы исключить из них точки не принадлежащие периметру ограниченной области (если во входных данных не запрещён случай толстой границы). В общем в такой постановке задача получается чуть сложнее, так как если входные точки неупорядочены, то сначала нужно сделать ещё один шаг, который соберёт из них какой-то контур. Хотя всё равно этот шаг можно сделать быстрее чем в floodfill, ограничившись исследованиями только периметра, а не всей площади внутренней области. Ну а далее можно либо сразу свести задачу к предыдущей, либо пообъединять алгоритмы чтобы выкинуть всякие проверки невозможных теперь случаев.
M>Как я понимаю, "Число точек на границе" можно не вычислять, т.к. нам уже даны все координаты, которые полностью описывают границы фигуры.
Ах, точно, я невнимательно прочитал условие. Предыдущее решение основывалось на предположении, что выходные точки являются вершинами многоугольника, очерчивающего контур интересующей области. Соответственно в этом случае между двумя вершинами может лежать более нуля целочисленных точек.
Впрочем в варианте где даны сразу точки контура их всё равно нужно как-то отфильтровать, например чтобы исключить из них точки не принадлежащие периметру ограниченной области (если во входных данных не запрещён случай толстой границы). В общем в такой постановке задача получается чуть сложнее, так как если входные точки неупорядочены, то сначала нужно сделать ещё один шаг, который соберёт из них какой-то контур. Хотя всё равно этот шаг можно сделать быстрее чем в floodfill, ограничившись исследованиями только периметра, а не всей площади внутренней области. Ну а далее можно либо сразу свести задачу к предыдущей, либо пообъединять алгоритмы чтобы выкинуть всякие проверки невозможных теперь случаев.
Re[5]: Найти количество точек лежащих внутри 2D фигуры
Здравствуйте, m1st, Вы писали:
M>Как я понимаю, "Число точек на границе" можно не вычислять, т.к. нам уже даны все координаты, которые полностью описывают границы фигуры.
Ах, точно, я невнимательно прочитал условие. Предыдущее решение основывалось на предположении, что входные точки являются вершинами многоугольника, очерчивающего контур интересующей области. Соответственно в этом случае между двумя вершинами может лежать более нуля целочисленных точек.
Впрочем в варианте где даны сразу точки контура их всё равно нужно как-то отфильтровать, например чтобы исключить из них точки не принадлежащие периметру ограниченной области (если во входных данных не запрещён случай толстой границы). В общем в такой постановке задача получается чуть сложнее, так как если входные точки неупорядочены, то сначала нужно сделать ещё один шаг, который соберёт из них какой-то контур. Хотя всё равно этот шаг можно сделать быстрее чем в floodfill, ограничившись исследованиями только периметра, а не всей площади внутренней области. Ну а далее можно либо сразу свести задачу к предыдущей, либо пообъединять алгоритмы чтобы выкинуть всякие проверки невозможных теперь случаев.
M>Как я понимаю, "Число точек на границе" можно не вычислять, т.к. нам уже даны все координаты, которые полностью описывают границы фигуры.
Ах, точно, я невнимательно прочитал условие. Предыдущее решение основывалось на предположении, что входные точки являются вершинами многоугольника, очерчивающего контур интересующей области. Соответственно в этом случае между двумя вершинами может лежать более нуля целочисленных точек.
Впрочем в варианте где даны сразу точки контура их всё равно нужно как-то отфильтровать, например чтобы исключить из них точки не принадлежащие периметру ограниченной области (если во входных данных не запрещён случай толстой границы). В общем в такой постановке задача получается чуть сложнее, так как если входные точки неупорядочены, то сначала нужно сделать ещё один шаг, который соберёт из них какой-то контур. Хотя всё равно этот шаг можно сделать быстрее чем в floodfill, ограничившись исследованиями только периметра, а не всей площади внутренней области. Ну а далее можно либо сразу свести задачу к предыдущей, либо пообъединять алгоритмы чтобы выкинуть всякие проверки невозможных теперь случаев.