Как определить, что точка лежит на многоугольнике?

Я решал вопрос, который требует выяснить, лежит ли точка строго внутри многоугольника или нет

Ну, я знаю о пакете java awt, поэтому я мог бы использовать это

polygon.contains(pointToCheck)

Но проблема в том, что согласно официальной документации определение внутренней принадлежности дается как

Точка считается лежащей внутри Shape тогда и только тогда, когда:

  • он полностью лежит внутри границы формы или
  • он лежит точно на границе Shape, а пространство, непосредственно примыкающее к точке по возрастанию X, полностью находится внутри границы или
  • он лежит точно на горизонтальном отрезке границы, а пространство, непосредственно примыкающее к точке по возрастанию Y, находится внутри границы

Итак, как мне удалить количество точек, лежащих на многоугольнике?

Если бы кто-нибудь мог предложить лучший алгоритм для проверки того, лежит ли точка строго внутри многоугольника, это также было бы полезно.


java awt computational-geometry polygon convex-hull
person coder_a    schedule 10.06.2020    source источник
comment
Прежде чем заняться этой проблемой, я предлагаю вам подумать над двумя вопросами. 1) Действительно ли в вашем наборе данных есть точка на границе? 2) Если предположить, что да, действительно ли имеет значение, если они иногда ошибочно классифицируются как внешние, а не как внешние?   -  person Yves Daoust    schedule 10.06.2020
comment
Да, на самом деле есть много точек, которые лежат на многоугольнике, я должен исключить эти точки и вернуть количество точек, которые лежат строго внутри него.   -  person coder_a    schedule 10.06.2020
comment
Не могли бы вы объяснить, почему? (На многоугольнике — сложная концепция.)   -  person Yves Daoust    schedule 10.06.2020

Ответы (2)


arrow_upward
1
arrow_downward

Алгоритм Хао для точки в многоугольнике включает проверку того, лежит ли точка на границе. бумага включает в себя довольно понятный псевдокод, если вы хотите написать его самостоятельно. Я написал реализацию javascript здесь.

В мире Java другим вариантом может быть просмотр Java Topological Suite. метод PointLocator, вероятно, делает то, что вам нужно. .

person rowanwins    schedule 12.06.2020

arrow_upward
-1
arrow_downward

Простой обходной путь — проверить, лежит ли ваша точка на контуре. Один из способов сделать это — взять все ребра по очереди, переместить одну из конечных точек в начало координат и повернуть, чтобы переместить другую точку на ось X, скажем, в (0, L). Тогда ваша точка находится на грани, если Y = 0 и 0 ≤ X ≤ L.

Затем вы можете совместить этот тест с тестом на внутреннюю сторону.

Предупреждение: в зависимости от вашего приложения и способа представления координат в числовом виде определение «на ребре» может иметь разные определения.

person Yves Daoust    schedule 10.06.2020
comment
Извините, но это трудно понять без псевдокода. Кроме того, это вопросы кодирования, где все координаты указаны как целые числа. - person coder_a; 10.06.2020
comment
Нет, но дело в том, что я решаю концепцию, связанную с очисткой лукового слоя или более известной как выпуклые слои. Мне нужен эффективный метод, чтобы проверить, находится ли точка внутри моего динамического корпуса или нет, поэтому может быть легко проверить это, используя вашу концепцию но это будет неэффективно, так как мне нужно проверять каждое ребро, и для него может быть большой набор данных. - person coder_a; 10.06.2020
comment
@coder_a: хорошо, похоже на вопрос XY. Вы не предоставили важную информацию. Когда вы тщательно реализуете алгоритм выпуклой оболочки, точки на ребрах автоматически отбрасываются! Кроме того, вы упомянули функцию polygon.contains, которая, безусловно, имеет поведение O (N), что вводит меня в заблуждение, полагая, что разрешена исчерпывающая проверка краев. - person Yves Daoust; 10.06.2020
comment
Простите за неудобства - person coder_a; 11.06.2020