Попадает ли точка в замкнутый многоугольник

← →
Дмитрий Белькевич (2010-04-25 00:18) [40]

Мне, например, не для хиттеста нужна. Забираю алгоритмом выделенный массив точек (векторный редактор). Если несколько потеряется по краям - то не критично, даже и не знал, что проблема существует.

← →
Sha © (2010-04-25 00:27) [41]

> Дмитрий Белькевич (25.04.10 00:18) [40]
> даже и не знал, что проблема существует.

Существует. PtInRegion теряет точки на правой и нижней границе.

Это не проблема, если регионы прямоугольные и имеют общие границы, параллельные осям.

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

← →
Ins © (2010-04-25 00:43) [42]

> Не скажет.

А, ну да, он лишнего не включает, насколько я вижу, скорее теряет недостающее. Да в любом случае никакой геометрической точности тут нет и быть не может в силу природы регионов - они "ступенчатые", растровые, а не векторные.

← →
Игорь Шевченко © (2010-04-25 00:51) [43]

Ins © (25.04.10 00:43) [42]

В компьютере все дискретно...

← →
Ins © (2010-04-25 00:56) [44]

> В компьютере все дискретно...

Это понятно, вопрос только насколько эта дискретность грубая. Так есть ли повод утверждать, что именно PtInRegion на границе считает правильно, и равнять под него алгоритм с меньшей степенью грубости?

← →
Sha © (2010-04-25 01:18) [45]

Нормально, вроде, он считает.
Более того, никак не удается построить пример выпадения точек у регионов с общими границами.
Похоже, в [41] я заблуждался насчет выпадения.

← →
Игорь Шевченко © (2010-04-25 01:33) [46]

Ins © (25.04.10 00:56) [44]

> Это понятно, вопрос только насколько эта дискретность грубая.
> Так есть ли повод утверждать, что именно PtInRegion на
> границе считает правильно, и равнять под него алгоритм с
> меньшей степенью грубости?

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

← →
Sha © (2010-04-25 02:10) [47]

Допустим, на плоскости заданы 4 точки с целочисленными координатами,
являющиеся вершинами горизонтально расположенного прямоугольника.

Добавим к этому множеству точек произвольное количество новых точек,
лежащих внутри или на границах прямоугольника и также имеющих
целочисленные координаты.
> Игорь Шевченко © (25.04.10 01:33) [46]

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

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

Вопрос в том, является ли PtInRegion такой функцией?
Все говорит за то, что является.

← →
Sha © (2010-04-25 02:14) [48]

Окошко для редактирования текста маловато.
В результате так фигово пост [47] оформлен, но смысл должен быть понятен.

← →
Германн © (2010-04-25 02:19) [49]

> В результате так фигово пост [47] оформлен

А в чём собственно "фиговость"? Читается нормально.

← →
Sha © (2010-04-25 02:21) [50]

В [47] подразумевается, что общая площадь многоугольников равна площади исходного прямоугольника, т.е. он разрезан на многоугольники.

← →
Sha © (2010-04-25 02:31) [51]

> Германн © (25.04.10 02:19) [49]
> А в чём собственно "фиговость"?

Лесенка строк режет глаз. От цитаты остался заголовок, который затесался в середину текста.

> Ins © (25.04.10 00:43) [42]
> он лишнего не включает, насколько я вижу, скорее теряет

Это псевдо-потеря. Граничная точка, как и любая другая, должна входить только в один регион. Вот она и входит в соседний регион, даже если он воображаемый.

← →
Германн © (2010-04-25 02:34) [52]

> Sha © (25.04.10 02:21) [50]
>
> В [47] подразумевается, что общая площадь многоугольников
> равна площади исходного прямоугольника, т.е. он разрезан
> на многоугольники.

Так ты про суть или про оформление?

← →
Sha © (2010-04-25 02:42) [53]

> Германн © (25.04.10 02:34) [52]
> Так ты про суть или про оформление?

В [47] коряво оформлено корявое изложение совершенно очевидной вещи :)

Если мы при помощи PtInRegion возьмемся красить точки каждого многоугольника в свой цвет,
то у нас не останется неокрашенных и не придется перекрашивать.

← →
Германн © (2010-04-25 03:18) [54]

Лучше я уж промолчу.

← →
Ins © (2010-04-25 11:45) [55]

> Sha © (25.04.10 02:31) [51]

Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется

← →
Ins © (2010-04-25 11:51) [56]

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

Брр... Нисколько в этом не сомневаюсь, я и не о том вообще... Тут выше была попытка адаптировать алгоритм с другой логикой так, чтобы он работал именно как PtInRegion. А зачем? Если этот алгоритм работает вполне правильно (я считаю, что точнее), то какая разница как работает PtInRegion, у которого свои причуды? Или эти причуды во что бы то ни стало должны быть одинаковыми?

> Граничная точка, как и любая другая, должна входить только
> в один регион.

Кому это она должна? :) Это смотря в какой задаче

← →
Игорь Шевченко © (2010-04-25 12:45) [57]

Ins © (25.04.10 11:51) [56]

> А зачем? Если этот алгоритм работает вполне правильно (я
> считаю, что точнее), то какая разница как работает PtInRegion,
> у которого свои причуды? Или эти причуды во что бы то ни
> стало должны быть одинаковыми?

Я сильно извиняюсь, а какие причуды у PtInRegion ?

> Ins © (25.04.10 11:45) [55]
> Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется

Если работать только с прямоугольными регионами, то можно подумать, что Windows исключает правую и нижнюю границу по одной и той же причине.
На самом деле это не так.
Обычно лучевой алгоритм проверки вхождения точки в регион проверяет, что точка находится строго левее линии. Поэтому вся левая граница не принадлежит региону. Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет правая граница.
С нижней границей дело обстоит иначе. Очевидно, алгоритм не должен считать дважды перечение луча с границей многоугольника в случае когда луч проходит точно через его вершину. Поэтому алгоритм не учитывает концы отрезков, имеющих бОльшую ординату. Это выглядит как срезание локальных выступов снизу региона, а не как полное исключение нижней границы.
Поэтому, например, невозможно создать такой регион, в который входили бы точки, помеченные буквой "о" на рисунке
..o... .ooo.. ooooo. .ooo.. ..o...
из-за среза правой границы получим
...... .oo... oooo.. .oo... ......
а если сдублировать границу вот так
..oo.. .oooo. oooooo .oooo. ..oo..
то будет еще хуже
..o... .ooo.. ooooo. .ooo.. ......

> Или эти причуды во что бы то ни стало должны быть одинаковыми?

Одинаковость причуд говорит о возможной одинаковости алгоритмов.

>> Граничная точка, как и любая другая, должна входить только в один регион.
> Кому это она должна? Это смотря в какой задаче.

Это да.

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

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

> Sha © (25.04.10 13:01) [58]

Написано:

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

Читать так:

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

> Sha (25.04.2010 13:09:59) [59]

Насколько я знаю, правая координата не указывается, а то что кажется координатой, на самом деле является длиной.
Поеэтому прямоугольник на 0, 32 - это не прямоугольник на 33 пикселя. Это обсуждали в Борландовских конференциях лет 10 назад.

> Одинаковость причуд говорит о возможной одинаковости алгоритмов.

Едва ли... Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных, в данном случае - о том, что это многоугольник с такими-то вершинами. Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников, которые являются приближением к этому полигону. А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.

> Ins © (25.04.10 19:17) [62]
> Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных...

Нет, не необходимо.

> Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников...

Эти самые прямоугольники вполне могли быть построены по лучевому алгоритму.

> А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.

Интересно, какими особенностями работы с прямоугольниками можно объяснить различия (о которых я писал) в выпадении правой и нижней границы?
Лучевой алгоритм их прекрасно объясняет.

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

Попадает ли точка в замкнутый многоугольник Найти похожие ветки