Принадлежность точки многоугольнику

  • 20
  • Недоступна
Дан многоугольник, заданный координатами своих вершин. Ребра многоугольника не пересекаются. Необходимо реализовать метод isPointInPolygon(Point point, List<Point> polygon), который проверит, принадлежит ли переданная точка многоугольнику. Метод main не изменяй.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (37)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Андрей
Уровень 41, Москва, Россия
9 января, 23:23
Решал через пересечение 4х лучей из точки вверх, вниз, влево, вправо. Если количество пересекаемых отрезков полигона чётное хотя бы одним лучом - значит точка не лежит в полигоне. В остальных случаях - лежит. Но валик что-то артачится. Пока не понял почему. С этим примером работает верно: polygon.add(new Point(0, 0)); polygon.add(new Point(0, 10)); polygon.add(new Point(5, 4)); polygon.add(new Point(10, 10)); polygon.add(new Point(10, 0));
Vladimir
Уровень 19, Нижний Новгород, Россия
29 октября 2021, 07:53
Друзья, а как внести подобную проверку в конструктор при создание выпуклого прямоугольника??
Flexo Bending Unit #3370318
28 июня 2021, 09:43
пробовал самое простое решение - через площади треугольников, потом обнаружил, что: многоугольник невыпуклый рассмотрите, например, такой:
polygon.add(new Point(0, 0));
polygon.add(new Point(0, 10));
polygon.add(new Point(5, 4));
polygon.add(new Point(10, 10));
polygon.add(new Point(10, 0));
попытался решить через попарное векторное произведение векторов граней с вектором точки, (пользуясь свойством некоммутативности векторного произведения), суть в том, чтобы убедиться, все ли результаты произведения одного знака (или 0) - это будет означать, что для всех граней точка находится с одной (внутренней) стороны. такое решение тоже не принимается. опять же, этот метод подходит только для выпуклых многоугольников плюнул и использовал класс Полигон в "правильном" решении задача решена через подсчёт пересечений с лучом из точки, параллельным OX
Anonymous #2491313
Уровень 35
1 апреля 2021, 19:46
Потратил пару часов, чтобы реализовать алгоритм сортировки точек по порядку и принадлежности точки. А оказалось, что он подходит только для выпуклых многоугольников, а задача решается вообще одной строчкой.
Олег
Уровень 43, Москва, Россия
29 апреля 2021, 06:30
можешь мне в лс отправить алгоритм?
Anonymous #2491313
Уровень 35
3 мая 2021, 14:27
Который одной строчкой или который я сначала реализовал?
Олег
Уровень 43, Москва, Россия
4 мая 2021, 09:08
можно и то и то
Олег
Уровень 43, Москва, Россия
4 мая 2021, 09:09
но если речь идёт о классе Polygon, то такой код можешь не кидать) заранее спасибо
Anonymous #2491313
Уровень 35
4 мая 2021, 15:54
Руководствовался вот этой статьёй: https://habr.com/ru/post/144571/ Правда пришлось ещё дописать сортировку точек, чтобы обход был правильный, ибо в задании они могут даваться в разнобой.
Flexo Bending Unit #3370318
28 июня 2021, 08:46
они не могут даваться вразнобой, иначе построим разные многоугольники (см. комментарий Leftover
Андрей Овчаренко
Уровень 41, Москва
3 августа 2021, 08:35
Для выпуклых написал примитивный алгоритм за десять минут, в цикле по всем точкам проверил есть ли точка левей выше, левей ниже, правей выше и правей ниже, и если 4 условия соблюдены - искомая точка внтутри.
Dark_Side Senior Android Developer в ЯRUS
10 февраля 2021, 15:54
Через класс Polygon и метод contains решается в пару строк https://programm.ws/page.php?id=343
Leftover
Уровень 39, Москва, Россия
27 ноября 2020, 15:10
Вероятно порядок вершин в списке определяет ребра, в противном случае нет единственного решения :)
Leftover
Уровень 39, Москва, Россия
30 ноября 2020, 11:25
Flexo Bending Unit #3370318
28 июня 2021, 09:25
в чём рисуют подобные диаграммы?
Хорс
Уровень 41, Харьков
17 октября 2020, 18:07
Ну как обычно, вначале изобрёл велосипед, валидатор не пропустил по одному пункту; зашел сюда, узнал про класс Polygon, переписал решение в одну строку, юзая стримы и обрёл счастье.
Александр Full Stack Developer
23 августа 2020, 07:47
Поскольку когда-то очень давно уже думал над этой задачей, решал через пересечение ребер многоугольника с прямой параллельной оси X и проведенной через данную точку. Если слева от точки нечетное количество пересечений, то точка попала в многоугольник.
Евгений Ведущий инженер в ПАО Сбербанк Expert
4 августа 2020, 18:59
Небольшая поправочка. Нашёл алгоритм, который позволяет сделать всё красиво (не буду его реализовывать, мне уже лень). 1. Находим площадь многоугольника (я посмотрел, это вполне реально и не сложно) ссылка 2. Суммируем площади треугольников, полученных при соединении двух ближайших точек многоугольника и искомой точки. 3. Если полученная сумма равна площади многоугольника - true. Иначе false.
Александр Full Stack Developer
23 августа 2020, 07:49
Будет ли работать такая логика для вогнутых многоугольников?
Flexo Bending Unit #3370318
28 июня 2021, 10:11
конечно, нет) и валидатор не примет
Евгений Ведущий инженер в ПАО Сбербанк Expert
4 августа 2020, 18:50
Написал (украл и переписал с JavaScript) алгоритм выявления принадлежности. Алгоритм самый простой - который проводит линию и считает пересечения. Сам бы вряд ли такое придумал, да и разобраться не смог. Кому интересно разобраться с этим алгоритмом - пишите, я его привёл в удобоваримый вид.