Координаты в asm и функции для работы с ними

MasterKenny
Ну тогда совсем просто. Значит у тебя есть массив точек, юзаем CreatePolygonRgn(), затем для нужного пикселя юзаем PtInRegion ().

 

Блин, ну народ, ну вы тут загнули. Задача решается элементарно.
Есть видимый буфер и бэк-буфер. На бэк-буфере каждая фигура имеет свой ID и рисуется соответственно "цветом" с номером ID, а на видимом буфере - так, как мы хотим (хоть градиентом, хоть радугой - да как угодно). После чего определение, входит ли точка в некую фигуру, очень просто: getpixel(x,y) на бэкбуфере, получаете вместо цвета id фигуры.

 

SadKo, сори я ещё нуб, ничё не понял, как на asm это реализовывается? можно более простым языком обьяснить?

 

l_inc

Мда, без картинок ты похоже не въезжаешь Случаев может и много, но их обработка сводится к одному достаточно простому алгоритму, который я уже дважды разжевывал. Чего не понятного то ? Если встречаем точку на луче, то смотрим все последующие точки, пока не найдем не принадлежащую лучу - тут хоть одна, хоть 10, хоть весь многоугольник - какая разница ? Да чем их больше, тем лучше, тем быстрее все обработается - шутка

Sadko

Кстати в исходной постановке ничего не говориться о том, что задача ограничивается рисованием "фигнюшек" на экране. Посмотрим как ты будешь создавать битмапы для эл.карт размером в десятки километров и требуемым разрешением в 1 см

 

leo
Похоже таки не въезжаю. Например, не въезжаю, как Ваш алгоритм различит два этих случая без введения дополнительных условий:
1) Точка не принадлежит "многоугольнику", лежащему на одной прямой:

x o---o------o-o---------o

2)Точка принадлежит "многоугольнику", лежащему на одной прямой:

o---o--x---o-o---------o

Где x - проверяемая точка, о - вершина многоугольника, а луч проводится вправо.

 

l_inc
Начнем с того, что методы площадей и знаков векторных произведений в этом случае вообще отдыхают, а угол поворота скачет на pi и тоже требует особой обработки
А в методе луча этот случай ничем не отличается от других вариантов, например такого:
о о
\ /
о--х--о
т.к. в любом случае, если анализируемая вершина лежит на луче, то должна проверяться принадлежность точки стороне.
В обоих случаях, наткнувшись на первую же вершину на луче, начинается поиск предыдущей (или последующей) вершины, не лежащей на луче. Если пред.вершина также принадлежит лучу (a[i-1].y = p.y), то проверяется принадлежность точки стороне (a[i-1].x <= p.x <= a.x) - если принадлежит, то конец всей обработки (точка лежит на границе многоугольника). Если не принадлежит, то смотрим следующую вершину (по кольцу с переходом от 0 к N-2) пока не найдем или не вернемся к исходной вершине. Если вернулись к исходной - значит вырожденный многоугольник, пересечений нет, на выход с песнЯми.

PS: Ну допустим, да, if тут не один и не два. Ну и что из этого, если это редкие случаи не влияющие на среднее быстродействие. Написал один раз функцию и забыл, чего в ней наворочено. MasterKenny вон виндовым CreatePolygonRgn и PtInRegion обрадовался, не думая о том насколько они наворочены, да еще и тормозят не хило

 

leo

Вообще я указал на это в посте 40.

Я об этом уже написал, напишу ещё раз: "Разумеется, более важна нагрузка пользователя (скорость работы, объём занимаемой памяти), а не программиста (число строк кода, читабельность программы)". НО! Если я пишу подобную безделушку для себя, то отдам предпочтение более красивому алгоритму, чем нагромождению if'ов, даже если if'ы будут работать втрое быстрее (это ж сколько вершин у многоугольника должно быть, чтобы была заметна разница в производительности). Хотя зависит от интереса... на интерес можно и произведение двух чисел под профайлером гонять.
Кстати, я даже не уверен, что вариант со знаками векторных произведений будет содержать меньше if'ов, но так показалось, когда CyberManiac предложил метод луча ещё в пятом посте.

 

l_inc

Во-первых, для безделушки можно и PtInRegion юзать Во-вторых, красивый алгоритм не всегда простото реализуется, особенно на асме

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

Для целых чисел смену знака можно проверять xor-ом, но нужен доп. if для анализа попадания точки на границу многоугольника. Сравнение площадей вообще без if-ов работает, зато нужно всегда просчитывать все вершины

 

leo

Ну так не дзенно же. Зачем же безделушка нужна, если и не на интерес, и без практической пользы.

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

Про пост 45 не забываем.

 

leo

Подумаешь - будет ещё одна карта такого же размера с глубиной цвета 32бит (или 4294967295 объектов не хватит?) )) А если задача ограничивается определением по выбранной точке только объекта видимого в данный момент на экране, то какая бы вся карта огромная ни была нужно всего навсего ещё один экран забитмапить

 

SadKo

Тоесть сектор должен быть закрашен одним цветом насколько я понял. Твой принцип в том, что есть массив(пусть даже в памяти), это и есть сектор, а доступ к каждому пикселю его просто вычисляется. Но в том и проблема, как закрасить сектор, имея только координаты пиксель, которые состовляют его контур. Винда не умеет это делоть с битовыми массивами(с памятью) напрямую. Можно извращаться с разделяемой памятью в таком случае.
Задача в том, насколько я понял, на входе массив точек, которые составляют контур(для вас это некоторые точки, ибо 'многоугольник') и координата проверяемой точки, на выходе признак того, находится ли тестируемая точка в этом секторе.

 

CrystalIC

FloodFill. В качестве "битового массива" - битмап с контуром в указанном контексте устройства. Способ - не меньший "боян", чем метод луча, метод подсчёта площадей или метод векторных произведений.

 

FloodFill() требует не указатель на массив, как в CreatePolygonRgn(), а хэндл контекста устройства, ога что боян.
Я хотел сегодня сделоть свою CreatePolygonRgn(), но есть проблемы в реализации. Кодес NtUserPolyPolyDraw в ReactOs слишком уж замудрёный. Например, если две точки соеденить линией, то как вычислять её пиксели хз..
Такое на z80 было, вот нашёл:

&

Как оно работает ?

 

Y_Mur

Не такого же. Речь идет о векторной карте, занимающей в памяти единицы-десятки Мб. Теперь посчитай какого размера должен быть битмап, если размер карты скажем 10х10 км, а определять принадлежность точки полигону нужно с точностью 1 см

Значит это не "задача", а "упражнение" )

 

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