Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Принадлежность точки контуру - где найти теорию?

Fishka © (2002-12-05 15:44:00)
Поиск по ключевым словам ничего не дает.
Где они: теорема Жордена для четного/нечетного количества пересечений, алгоритм Брезенхема?
Помогите ссылками или текстами........

Andrey007 (2002-12-05 17:26:00) [1]
Fishka, я тебе хотел ответ сюда скинуть, а форум написал, что длиннее 5000 символов он сообщения не принимает. Поэтому послал тебе ответ по e-mail.

Digitman (2002-12-05 17:14:00) [2]
А нахрена тебе оная в дан.случае ?) Моря, они "пересекаются" что ли у тебя ?

Fishka (2002-12-05 17:01:00) [3]
А теория о количестве пересечений для всех многоугольников.
Где ее взять?

Digitman (2002-12-05 16:20:00) [4]
да, пардон ..
сие только для выпуклых полигонов

но - что мешает представить любой полигон множеством выпуклых субполигонов за вычетом исключающего множества ?

Tundra (2002-12-05 16:17:00) [5]
Система ур-ний наподобие симплекс метода - проще всего, и нагляднее.
Просто провер на все условия.
ai*xi+...ai*xi<=bi i=1..n
поставь свои коор-ты в уравнения - если всем уд-ет значит внутри
главное здесь описать систему.

Fishka (2002-12-05 16:17:00) [6]
Andrey007 (05.12.02 16:11)
Мысль понятно. А где взять теорию?

Digitman (2002-12-05 16:16:00) [7]
так тогда уж - не контуру )
а - полигону, образованному контуром из N ребер)

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

В этом случае (для "против час.стрелки") для каждого полигона делай то же самое по всем его ребрам :
- если скал.произведение векторов < 0, точка - "слева" от линии ребра полигона
- если скал.произведение векторов = 0, точка - на линии ребра полигона
- если скал.произведение векторов > 0, точка - "справа" от линии ребра полигона

необходимое и достаточное условие определения нахождения точки внутри полигона : все скал.произведения < 0

необходимое и достаточное определения нахождения точки на одном из ребер полигона : все скал.произведения <= 0

необходимое и достаточное определения нахождения точки вне полигога : хотя бы одно из скал.произведений > 0

Andrey007 (2002-12-05 16:11:00) [8]
Там ещё можно сумму углов считать. Если точка внутри, то один случай, если вне, то другой.
А с пересечениями в случае невыпуклого многоугольника, каковыми и являются моря, можно намучаться - прямая, проведённая для поиска пересечений может пройти через точку, являющейся вершиной многоугольника, и при этом в этой вершине происходит смена направления обхода контура. Может я и не очень удачно выразил свою мысль, но надеюсь, что Fishka поймёт.

Fishka (2002-12-05 16:02:00) [9]
Я не помню этого.........
Задача: есть точка с географ. координатами. Есть описание морей по координатам. Определить, в каком море она находится.
И хотелось бы по четному/нечетному количеству пересечений.

Digitman (2002-12-05 15:51:00) [10]
а школьный учебник геометрии уже не катит ?) Это ж - планиметрия как бы ?

каждое ребро контура представь вектором
вектором же представь отрезок, соединяющий одну из вершин ребра и точку

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

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »