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

Question

[Kooper_pro]

Есть картинка, на ней есть n кол-во полигонов (в основном 4-угольные), они не пересекаются. Так вот как узнать какому полигону принадлежит произвольно введенная тока?

Какой математический алгоритм использовать нужно?

Answer 1

[xmoonlight]

Вот я и говорю, что способы решения задачи, работают быстрее инструментов.
Предлагаю простой способ: использовать заливку цветом многоугольника в памяти и проверить цвет точки в нужных координатах)
И быстро (нативно - ВЕЗДЕ!) и точно будет работать!)

Если нужно быстро и периодически проверять (mouse-move, к примеру) - делаем карту: изображение с заливками областей разным цветом (где-то в памяти).
Затем, берём по нужным координатам (текущие координаты курсора "мыши", например) цвет пикселя изображения-карты (из памяти) и смотрим по созданному списку на основе кол-ва нужных (для мониторинга) зон: какой зоне/сегменту он (пиксель с нужными координатами) принадлежит.

Comments

[Руслан .]

Тут есть небольшая вероятность попасть в границу области, а все границы одного цвета. Для этого случая алгоритм работать не будет.

[xmoonlight]

LaRN, ничего личного, но: умные люди, в отличие от Вас, понимают, что границ как таковых - нет, есть только соприкасающиеся зоны с заливкой разным цветом.
Чёрные линии на этом (и рисунке автора с прозрачными зонами) рисунке - только для наглядности понимания.
Думайте, когда пишите коммент...

[Руслан .]

Алгоритм заливки области требует указания границы области, например цветом. Как вы предлагаете делать заливку не указав контуров? Особенно это касается стыков областей, т.е. внутренних рёбер, которые как бы принадлежат нескольким областям.

[xmoonlight]

LaRN, обводим (или отсекаем) неразмеченную область контуром нужного цвета и этим же цветом заливаем эту область.

[Руслан .]

Тут тоже есть нюанс. При таком подходе граница включается в ту область, которая выводится раньше. Т.е. порядок вывода областей в буфер меняться не должен иначе немного изменят границы объектов. Например если 6 область выводить последней ее северная граница будет на 1-2 пикселя смещена вниз, но если выводит области в обратном порядке, то южная граница области 1 будет смещена вверх на те же 1-2 пикселя.

Кроме этого, если исходная картинка имеет размер больше чем размер экрана, т.е. есть скролл или зум, то закрашенные области не всегда будут точно решать задачу из-за погрешностей вычисления координат в цветовом буфере по координатам исходной картинки. И тут придётся заново перестроитраивать цветовой буфер как только картинка поменяет масштаб.

[xmoonlight]

LaRN,
Блин, бред хватит может уже писать...
Вы хотя бы раз сами делали то, что пишите ?!

[Kooper_pro]

xmoonlight, данный метод нормально работает, только заметил один нюанс, что уменьшении размера цвета изменяются, это касается на мобильных устройствах ( может быть, что при клике пальцем область больше захватывается, чем один пиксель?) Но в целом погрешность малая если оригинал RGB(0,0,0,), то на мобильном она у меня почему то составляет RGB(1,0,1), чем связно не знаю.

[Руслан .]

Конечно делал(я таким образом определял грань на 3D модели, которую выбрали мышью. Т.е. строил проекции всех видимых граней, которые попадали во viewport, на плоскость экрана, и у каждой грани делал заливку цветом соответсвующим номеру грани, а дальше по координатам мыши определял грань), поэтому и пишу. Вы нарисовали у каждой области свою границу, но по условию задачи это не так. Граница задается отрезком соединяющим две точки - это одна линия, а у вас по факту две рядом идущие границы.

Я в общем то и не критикую это решение, просто Вы его упомянули как универсальное и всегда работающее, а по факту тут есть границы применимости и нужно о них знать чтобы понимать можно использовать метод для решения задачи или нет.

[xmoonlight]

LaRN,

Вы нарисовали у каждой области свою границу, но по условию задачи это не так.

Это по какому такому условию и какой задачи?
Если по этому:

Есть картинка, на ней есть n кол-во полигонов (в основном 4-угольные), они не пересекаются. Так вот как узнать какому полигону принадлежит произвольно введенная тока?

то всё так... Или ещё есть какое-то условие?
--------------------
2.

Граница задается отрезком соединяющим две точки - это одна линия, а у вас по факту две рядом идущие границы.

Ну Вы же сами пишите правильно, но не понимаете смысла до конца.
Границы бывают разные:

1. Граница полигона (цветные квадраты на рисунке) - линия внутри полигона, проходящая по его краю, за граню которой происходит переход цвета с одного на другой (т.е. расположен уже другой полигон).
   
2. Разделительный полигон (сетка) - это полигон в виде сетки, форма ячеек которой имеет форму пограничных полигонов, находящихся внутри этой сетки.
   

-----------------------
3.

просто Вы его упомянули как универсальное и всегда работающее, а по факту тут есть границы применимости

- это какие, например? В любом из случаев, мой предложенный метод карт будет корректно срабатывать.

[xmoonlight]

Kooper_pro, карта строится на устройстве (через canvas) или скачивается с сервера готовая? Скорее всего проблема как раз в разнице границ (почитайте мой ответ выше...).

[Руслан .]

Kooper_pro, это может быть связано с особенностями растеризации при отрисовке линий. Так делается чтобы линии казались более гладкими без ступенек.
Подробнее вот в этой статье почитать.
https://habrahabr.ru/post/343876/
Либо с интерполяцией цветом при масштабировании.
compgraph.tpu.ru/scale.htm

[Kooper_pro]

xmoonlight, картинка скачивается с сервера но прорисовывается на канвасе, клик происходит по середине блока, та границ нету.

[Kooper_pro]

LaRN, клик происходит не на стыке границ, причем тут края блока?

[Руслан .]

Так вторая же ссылка, про масштабирование изображений. При использовании интерполяции и для случая уменьшения исходного изображения каждому пикселю уменьшенного изображения соответствует несколько пикселей исходного и чтобы определить результирующий цвет берут квадратичную или кубическую функцию от исходных цветов пикселей. В итоге от границы к центру области происходит небольшое отклонение от исходного цвета. Вот здесь про resize на canvas хорошо написано.

[Руслан .]

https://habrahabr.ru/post/252175/

[Kooper_pro]

LaRN, согласен, но размытие актуально для градиентных цветов, но не в этом случае. Только сейчас проверил, не искажает. И не в этом дело. Суть в том, что на дестопных экранах при уменьшении размера все норм определяет цвет в цвет, а вот на мобильных нет.

[xmoonlight]

Kooper_pro,

картинка скачивается с сервера но прорисовывается на канвасе, клик происходит по середине блока, та границ нету.

Прорисовывается в памяти или на холсте?
Используйте createImageBitmap и не рендерите на холст! Все проверки - делайте в памяти!

Answer 2

[twobomb]

Алгоритм определения попадания точки в контур на о...
Вот переделал функцию на javascript можно посмотреть визуально.

Comments

[Kooper_pro]

А если масштабируемая картинка, т.е можно будет сделать тоже самое только без привязки к пикселям?

[twobomb]

Kooper_pro, Всмысле привязки к пикселям? Можете привязывать к любым координатам. Не совсем понял вопрос. Часть отрисовки тут никак не привязана можете скейлить.

Answer 3

[Stalker_RED]

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

Answer 4

[Руслан .]

Вот тут подробно расписаны алгоритмы
https://habrahabr.ru/post/301102/