Принадлежность точки контуру

← →
Fishka (2002-12-05 15:44) [0]

Поиск по ключевым словам ничего не дает.
Где они: теорема Жордена для четного/нечетного количества пересечений, алгоритм Брезенхема?
Помогите ссылками или текстами........

← →
Digitman © (2002-12-05 15:51) [1]

а школьный учебник геометрии уже не катит ?) Это ж - планиметрия как бы ?

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

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

← →
Fishka (2002-12-05 16:02) [2]

Я не помню этого.........
Задача: есть точка с географ. координатами. Есть описание морей по координатам. Определить, в каком море она находится.
И хотелось бы по четному/нечетному количеству пересечений.

← →
Andrey007 (2002-12-05 16:11) [3]

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

← →
Digitman © (2002-12-05 16:16) [4]

так тогда уж - не контуру )
а - полигону, образованному контуром из N ребер)

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

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

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

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

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

← →
Tundra (2002-12-05 16:17) [5]

Система ур-ний наподобие симплекс метода - проще всего, и нагляднее.
Просто провер на все условия.
ai*xi+...ai*xi<=bi i=1..n
поставь свои коор-ты в уравнения - если всем уд-ет значит внутри
главное здесь описать систему.

← →
Fishka (2002-12-05 16:17) [6]

Andrey007 (05.12.02 16:11)
Мысль понятно. А где взять теорию?

← →
Digitman © (2002-12-05 16:20) [7]

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

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

← →
Fishka (2002-12-05 17:01) [8]

А теория о количестве пересечений для всех многоугольников.
Где ее взять?

А нахрена тебе оная в дан.случае ?) Моря, они "пересекаются" что ли у тебя ?

← →
Andrey007 (2002-12-05 17:26) [10]

Fishka, я тебе хотел ответ сюда скинуть, а форум написал, что длиннее 5000 символов он сообщения не принимает. Поэтому послал тебе ответ по e-mail.

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