Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

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

 
Дмитрий Белькевич   (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 ?


 
Sha ©   (2010-04-25 13:01) [58]

> 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 ©   (2010-04-25 13:09) [59]

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

Написано:

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

Читать так:

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


 
Anatoly Podgoretsky ©   (2010-04-25 13:19) [60]

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

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


 
Sha ©   (2010-04-25 13:40) [61]

> Anatoly Podgoretsky ©   (25.04.10 13:19) [60]

Да, конечно.


 
Ins ©   (2010-04-25 19:17) [62]


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


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


 
Sha ©   (2010-04-25 22:28) [63]

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

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

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

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

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

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


 
Sha ©   (2010-04-26 00:25) [64]

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



Страницы: 1 2 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.61 MB
Время: 0.116 c
2-1273511164
Andrewtitoff
2010-05-10 21:06
2010.08.27
Как обозначаются бвоичные данные?


15-1268602203
Юрий
2010-03-15 00:30
2010.08.27
С днем рождения ! 15 марта 2010 понедельник


4-1233845602
niro
2009-02-05 17:53
2010.08.27
Эмулирование действий пользователя в MSIE


15-1268947805
Юрий
2010-03-19 00:30
2010.08.27
С днем рождения ! 19 марта 2010 пятница


15-1266769968
TUser
2010-02-21 19:32
2010.08.27
Суворов о деле Пеньковского