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

всегда приятно найти способ обойтись без системы, а потом обойтись одной системной функцией!
CrystalIC

а чем не нравится этот способ. найти все ее точки - путем анализа прилежащих пикселей ищем minX, minY, maxX, maxY. все точки фигуры будут в области от minX, minY, до maxX, maxY или мне перечислить?

 

del. блин. баги с нетом

 

max7C4
А по тому, что этот алгоритм требует для определения принадлежности точки сектору получение большого числа точек, например если затравка находится в одном конце сектора, а необходимая точка в другом конце(макс. удалены друг от друга), то придётся залить весь сектор(перечислить все точки его). Разумеется число точек которые находятся в нутри сектора обычно больше чем состовляющих его контур. Так что слишком уж не эффективно.
[Все точки искать ради того, чтобы определить принадлежит ли нужная точка сектору )))]

 

ну можно пойти по другому пути - векторное произведение и поиск методом тыка контурных точек

 

Поподробнее можно ?

 

да все просто. если известны вершины многоугольника, то можно их упорядочить и выбрать направление обхода рассматривая векторы из искомой точки к текущей паре вершин. при векторном произведение будут получаться векторы, при правильном выборе обхода если все векторы имеют одно направление (положительное) то точка внутри многоугольника, но многоугольник должен быть выпуклым или придется вогнутый разбить на выпуклые. разница углов arctg(y1/x1)-arctg(y2/x2) (если я не путаю, то все хорошо, иначе поменяйте местами x и y и есессно при x0=0, y0=0)

 

max7C4
Ерунда. Почему ты споришь со мной ?
Я предложил лучший вариант, как всегда, кому нужно тот возьмёт.

 

CrystalIC

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

 

l_inc
Как же так, вопрос в названии топика.

А этот ответ имеет отношение к задаче
murder написал ответ:

Автора топика данный ответ удовлетворил, следствие - работа с пикселями.

 

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

 

max7C4
Ерунда не ерунда, но уже давно работает.

Я думол это ты уже понял. Контур описывает сектор за счёт меньшего числа пиксель, подобно как обьект 'регион'.

Способ я дал.

Фигура не может его не иметь.

Определение условия принадлежности пиксель сектору/фону это уже совсем другая задача.

Повиснуть не может.
Твои замечания не относятся к теме..

 

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

0111
0 11
0
000000
0
0

скорее всего она заблудится в 1-ках

 

max7C4
Учите матчасть. Удачи!

 

[redundant]

 

CrystalIC

Ещё увидим.

Может автор ещё не понял, чем удовлетворился.
Я так понял, что "создание многоугольника по координатам точек, и произвольной точки" - это одна задача. И здесь как раз GDI рулит. А "определение лежит ли точка в многоугольнике или находится за его пределами" - это другая задача, в которой пиксельной (целой) точности не хватит. Может сам гоню.

 

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

Метод же луча, во-первых, одинаково хорошо работает и для выпуклых, и невыпуклых и даже для многосвязных многоугольников (без разницы с дырками или с несколькими несвязными областями). Во-вторых, при достаточно большом числе сторон позволяет повысить скорость обработки за счет быстрой отбраковки сторон, заведомо не пересекающих луч (если обе точки стороны лежат в одной полуплоскости от луча или обе "левее" центра луча). Причем если требуется проверить попадание не одной, а множества точек в один многоугольник, то можно построить индекс для еще более быстрой отбраковки заведомо непересекаемых сторон (разбиваем поле на полоски определенной ширины и для каждой полоски формируем массивы\списки номеров точек\сторон потенциально пересекающих данную полоску - затем при анализе попадания точки берем соответсвующую полоску и проверяем только проходящие через нее стороны).
Что касается обработки особых случаев, когда луч проходит через вершину или сторону многоугольника, то во-первых это достаточно просто решается (алгоритмически), во-вторых, практически не сказывается на быстродействии, т.к. эти случаи явлются достаточно редкими. Алгоритм - простой. Догавариваемся, что будем анализировать совпадение только одной точки стороны, например, первой. Когда встречаем совпадение, то первым делом проверяем не лежит ли искомая точка на стороне - если лежит, то ОК, значит точка принадлежит границе - идем на выход с песнями. Иначе ищем ближайшие предыдущую и последующую точку многоугольника, которые не лежат на луче. Если эти точки лежат по разные стороны от луча - считаем, что пересечение есть, иначе - нет. Дальнейший анализ пересечений продолжаем с найденной несовпадающей точки. Как говорится - элементарно, Ватсон

 

leo
Ну наконец-то. Давно Вас тут не было.

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

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

 

l_inc

Дык, я вроде уж сказал как. Алгоритмически - элементарно, реализовать на ЯВУ тоже
Отличать "входит\не входит" не нужно, нужно отличать "пересекает\не пересекает\пофиг" Считаем, что пересекает - когда ближайшие две вершины (до и после анализируемой), не лежащие на луче, лежат по разные стороны от луча. Слева\справа определяется элементарно по знаку того же векторного произведения (dy1*dx2-dx1*dy2). Если же они лежат по одну сторону, то нам "пофиг" внутри идет луч или снаружи - считаем, что пересечения нет (если конечно искомая точка не совпадает с этой вершиной - это нужно проверяь особо). На картинках пояснить ?

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

 

CrystalIC,

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

Согласен задача не трудная, но я asm только изучаю и поэтому на практике что то сделать для меня пока что проблематично.

 

leo

Ну случаев на самом деле довольно много. Например, проверяемая точка лежит на стороне, а луч содержит эту сторону, или на луче лежит более двух подряд идущих вершин или вообще весь "многоугольник". В результате на быстродействии это почти не скажется, но код превратится в нагромождение if'ов. Некрасиво. А для алгоритма с векторными произведениями и обходом многоугольника на получение 360° единственный дополнительный случай - это проверка, не лежит ли весь многоугольник на одной прямой.
Хотя, разумеется, более важна нагрузка пользователя (скорость работы, объём занимаемой памяти), а не программиста (число строк кода, читабельность программы).
CrystalIC

Похоже, я был прав.