Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Начинающим";
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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


 
API ©   (2006-03-12 11:20) [13]

[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 и все закончилось ;-)


 
API ©   (2006-03-12 11:58) [16]

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

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

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

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


 
grisme ©   (2006-03-12 12:14) [17]

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



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

Форум: "Начинающим";
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.49 MB
Время: 0.042 c
4-1135935445
oleggar
2005-12-30 12:37
2006.03.26
file monitoring


15-1141392869
Alarm
2006-03-03 16:34
2006.03.26
Возможно это и глупо, но ...


15-1141100242
paza
2006-02-28 07:17
2006.03.26
Нестандартные шрифты


1-1140595655
Zhekson
2006-02-22 11:07
2006.03.26
Как считать содержимое ячейки DBGrid?


2-1142244119
Fenix
2006-03-13 13:01
2006.03.26
Проблема со String





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский