| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Попадает ли точка в замкнутый многоугольник
kudatsky © (2010-04-22 11:54:00)На экране находится не выпуклый многоугольник, заданный координатами X1,Y1,X2,Y2,X3,Y3 и т.д. Задана точка X,Y. Как определить, находится ли точка внутри фигуры ? Нет ли для этого системной функции ?
Sha (2010-04-26 00:25:00) [1]Хотя, наверно, и другие алгоритмы могут приводить к тем же особенностям.
Ну, это только к лучшему.
Sha (2010-04-25 22:28:00) [2]> Ins © (25.04.10 19:17) [62]
> Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных...
Нет, не необходимо.
> Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников...
Эти самые прямоугольники вполне могли быть построены по лучевому алгоритму.
> А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.
Интересно, какими особенностями работы с прямоугольниками можно объяснить различия (о которых я писал) в выпадении правой и нижней границы?
Лучевой алгоритм их прекрасно объясняет.
Ins (2010-04-25 19:17:00) [3]
> Одинаковость причуд говорит о возможной одинаковости алгоритмов.
Едва ли... Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных, в данном случае - о том, что это многоугольник с такими-то вершинами. Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников, которые являются приближением к этому полигону. А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.
Sha (2010-04-25 13:40:00) [4]> Anatoly Podgoretsky © (25.04.10 13:19) [60]
Да, конечно.
Anatoly Podgoretsky (2010-04-25 13:19:00) [5]> Sha (25.04.2010 13:09:59) [59]
Насколько я знаю, правая координата не указывается, а то что кажется координатой, на самом деле является длиной.
Поеэтому прямоугольник на 0, 32 - это не прямоугольник на 33 пикселя. Это обсуждали в Борландовских конференциях лет 10 назад.
Sha (2010-04-25 13:09:00) [6]> Sha © (25.04.10 13:01) [58]
Написано:
> Обычно лучевой алгоритм проверки вхождения точки в регион проверяет,
> что точка находится строго левее линии.
> Поэтому вся левая граница не принадлежит региону.
> Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет правая граница.
Читать так:
Обычно лучевой алгоритм проверки вхождения точки в регион проверяет,
что точка находится строго левее линии.
Поэтому вся праваяграница не принадлежит региону.
Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет леваяграница.
Sha (2010-04-25 13:01:00) [7]> 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.
А если мы показываем на однотонном фоне какой-нибудь геометрический объект, например, пирамиду, то имеет смысл отрисовать его четкие границы.
Приведенный алгоритм может быть легко модифицирован для этой задачи
Игорь Шевченко (2010-04-25 12:45:00) [8]Ins © (25.04.10 11:51) [56]
> А зачем? Если этот алгоритм работает вполне правильно (я
> считаю, что точнее), то какая разница как работает PtInRegion,
> у которого свои причуды? Или эти причуды во что бы то ни
> стало должны быть одинаковыми?
Я сильно извиняюсь, а какие причуды у PtInRegion ?
Ins (2010-04-25 11:51:00) [9]
> Не совсем понимаю, в чем проблема - внутренняя структура
> региона тайны не представляет, определить, принадлежит ли
> точка всем прямоугольникам из этой структуры задача вполне
> однозначно осуществимая.
Брр... Нисколько в этом не сомневаюсь, я и не о том вообще... Тут выше была попытка адаптировать алгоритм с другой логикой так, чтобы он работал именно как PtInRegion. А зачем? Если этот алгоритм работает вполне правильно (я считаю, что точнее), то какая разница как работает PtInRegion, у которого свои причуды? Или эти причуды во что бы то ни стало должны быть одинаковыми?
> Граничная точка, как и любая другая, должна входить только
> в один регион.
Кому это она должна? :) Это смотря в какой задаче
Ins (2010-04-25 11:45:00) [10]
> Sha © (25.04.10 02:31) [51]
Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется
Германн (2010-04-25 03:18:00) [11]Лучше я уж промолчу.
Sha (2010-04-25 02:42:00) [12]> Германн © (25.04.10 02:34) [52]
> Так ты про суть или про оформление?
В [47] коряво оформлено корявое изложение совершенно очевидной вещи :)
Если мы при помощи PtInRegion возьмемся красить точки каждого многоугольника в свой цвет,
то у нас не останется неокрашенных и не придется перекрашивать.
Германн (2010-04-25 02:34:00) [13]
> Sha © (25.04.10 02:21) [50]
>
> В [47] подразумевается, что общая площадь многоугольников
> равна площади исходного прямоугольника, т.е. он разрезан
> на многоугольники.
Так ты про суть или про оформление?
Sha (2010-04-25 02:31:00) [14]> Германн © (25.04.10 02:19) [49]
> А в чём собственно "фиговость"?
Лесенка строк режет глаз. От цитаты остался заголовок, который затесался в середину текста.
> Ins © (25.04.10 00:43) [42]
> он лишнего не включает, насколько я вижу, скорее теряет
Это псевдо-потеря. Граничная точка, как и любая другая, должна входить только в один регион. Вот она и входит в соседний регион, даже если он воображаемый.
Sha (2010-04-25 02:21:00) [15]В [47] подразумевается, что общая площадь многоугольников равна площади исходного прямоугольника, т.е. он разрезан на многоугольники.
Германн (2010-04-25 02:19:00) [16]
> В результате так фигово пост [47] оформлен
А в чём собственно "фиговость"? Читается нормально.
Sha (2010-04-25 02:14:00) [17]Окошко для редактирования текста маловато.
В результате так фигово пост [47] оформлен, но смысл должен быть понятен.
Sha (2010-04-25 02:10:00) [18]Допустим, на плоскости заданы 4 точки с целочисленными координатами,
являющиеся вершинами горизонтально расположенного прямоугольника.
Добавим к этому множеству точек произвольное количество новых точек,
лежащих внутри или на границах прямоугольника и также имеющих
целочисленные координаты.
> Игорь Шевченко © (25.04.10 01:33) [46]
Затем создадим множество непересекающихся многоугольников произвольной формы, используя в качестве их вершин наше множество точек.
Нам хотелось бы, чтобы функция, определяющая принадлежность точек
многоугольникам, относила каждую внутреннюю точку исходного прямоугольника,
а также точки, лежащие на его верхней и левой сторонах,
в точности к одному многоугольнику
и считала, что точки, лежащие на правой и нижней сторонах,
не входят ни в один многоугольник.
Вопрос в том, является ли PtInRegion такой функцией?
Все говорит за то, что является.
Игорь Шевченко (2010-04-25 01:33:00) [19]Ins © (25.04.10 00:56) [44]
> Это понятно, вопрос только насколько эта дискретность грубая.
> Так есть ли повод утверждать, что именно PtInRegion на
> границе считает правильно, и равнять под него алгоритм с
> меньшей степенью грубости?
Не совсем понимаю, в чем проблема - внутренняя структура региона тайны не представляет, определить, принадлежит ли точка всем прямоугольникам из этой структуры задача вполне однозначно осуществимая.
Sha (2010-04-25 01:18:00) [20]Нормально, вроде, он считает.
Более того, никак не удается построить пример выпадения точек у регионов с общими границами.
Похоже, в [41] я заблуждался насчет выпадения.
| |
Страницы: 