Как узнать, находится ли точка внутри многоугольника?

← →
dera (2006-03-11 17:56) [0]

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

← →
API © (2006-03-11 18:04) [1]

1. Нарисуйте на листке бумаги совершенно произвольный многоугольник.
2. Поставьте произвольно точку.
3. Проведите горизонтальную (вертикальную, под любым углом) линию через этут точку.
4. Посчитайте количество пересеченией линий многоугольника с этой линией с одной стороны от точки и с другой стороны от точки.
5. Пока не поняли в чем дело - переходите к п. 2 (можно и к п. 1).
6. Напишите алгоритм.
7. Реализуйте алгоритм в виде готового кода. Если на этом этапе возникнут трудности - пишите письма в "Начинающим".

← →
begin...end © (2006-03-11 18:08) [2]

CreatePolygonRgn + PtInRegion. Оно рульно будет.

← →
Desdechado © (2006-03-11 19:08) [3]

особенно весело для самопересекающихся многоугольных областей

← →
antonn © (2006-03-11 19:26) [4]

нарисовать на битмапе полигоном с заливкой, посмотреть цвет пикселя по координатам:)

← →
begin...end © (2006-03-11 19:30) [5]

> Desdechado © (11.03.06 19:08) [3]

Просьба пояснить, к чему относится этот комментарий. Пока не совсем ясно.

← →
Alarm © (2006-03-11 19:44) [6]

>begin...end © (11.03.06 19:30) [5]
Комментарий к тому, что не задана последовательность соединения Координаты всех точек известны:)

← →
Гаврила © (2006-03-11 19:47) [7]

> не задана последовательность соединения

Судя по всему, все таки задана.
Через регион проще всего, короче

← →
palva © (2006-03-11 22:35) [8]

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

← →
Sergey Masloff (2006-03-11 23:47) [9]

palva © (11.03.06 22:35) [8]
ptInRegion с самопересечением работает без проблем. Сложности задачи по прежнему не вижу.

← →
Ricks © (2006-03-11 23:53) [10]

Если допустить, что область правильная, то если точка принадлежит области, сумма углов от i-ой вершины к (i+1)-ой вершине равна 2*пи.
То есть находишь углы между векторами, соединяющими проверяемую точку с i и i+1 вершиной а затем складываешь их. Сумма должна быть приблизительно 2*пи
Вроде бы так.

← →
Sergey Masloff (2006-03-12 09:27) [11]

Да, сколько интересных алгоритмов можно восстановить не зная стандартных и отлаженых функций. Просто зависть берет сколько у людей задора и свободного времени.

← →
grisme © (2006-03-12 10:23) [12]

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

[11] Sergey Masloff (12.03.06 09:27)
Да, сколько интересных алгоритмов можно восстановить не зная стандартных и отлаженых функций. Просто зависть берет сколько у людей задора и свободного времени.

HRGN и функции работы с ним - один из возможных способов обработки областей размера порядка размеров экрана и немного выше. Все что еще выше - уже сложней. При использовании координат с плавающей точкой - они уже неприменимы. При использовании непрямоугольной системы координат - тоже. Заметьте - в вопросе ни слова не сказано об используемых координатах и координатной системе. Поэтому регионы, в данном случае, - совершенно частное, узкое и потому - некорректное решение. При использовании декартовой системы координат - я предложил в [1]. А если система координат полярная - Ricks © [10]. Причем, что характерно, и [1], и [10] - гораздо более универсальные и математически обоснованные решения, чем применение регионов.

Хотя, может, я и ошибаюсь, и существуют "стандартные и отлаженные функции" для решения этих задач? Просвятите...

[12] grisme © (12.03.06 10:23)

Мощь! Хотя, если пространство неевклидово - тогда очень даже хороший метод. Причем - даже в обычной картографии - для пересеченной местности - имеет место для применения. Хотя - очень частного применения. :)

← →
Sergey Masloff (2006-03-12 11:33) [14]

API © (12.03.06 11:20) [13]
> совершенно частное, узкое и потому - некорректное решение.
Странная логическая цепочка ;-)
Все же считал и буду считать что начинать следует с простых решений. Если бы аффтар написал - проблема, задача следующая: .... пробовал ... не подошло по причине ... тогда можно привлекать всяческие алгоритмы и развивать вокруг теории и прочее. А пока я уверен на 99.9% что "некорректное" решение с ptInRegion решит поставленую задачу.

← →
Sergey Masloff (2006-03-12 11:37) [15]

Кстати было уже обсуждение этой проблемы тут и приводимый вами алгоритм звучал, посту на 40 я предложил любимый ptInRegion и все закончилось ;-)

Странная логическая цепочка

Ну вот такой вот я странный. :)

Кстати было уже обсуждение этой проблемы тут и приводимый вами алгоритм звучал, посту на 40 я предложил любимый ptInRegion и все закончилось

Я более чем уверен, что автору данной ветки региона - вполне достаточно, особенно учитывая прочие его вопросы на форуме.
Но вопрос им был поставлен более широко.
Поэтому, в общем случае,- все предложенные варианты, в зависимости от более уточненных (уже самим автором, в процессе "фильтрации" ответов) условий, без сомнения, имеют право на реализацию. Хотя, все они являются частными, то есть не дают однозначного точного ответа на поставленный вопрос, т.е. - не совсем корректны (с точки зрения правильности, точности). И опять же: вместе они составляют неполное множество возможных решений - ибо единого решения поставленной задаче нет. :)

проблема приведенного мной алгоритма - число вершин. не знаю, с треугольником решилось нормально.:)

Как узнать, находится ли точка внутри многоугольника? Найти похожие ветки