Даны координаты последовательно идущих вершин четырехугольника (х1 у1) (х2 у2)... и координаты одной точки... Надо определить внутри точка или нет. Для выпуклого четырех угольника я кое как сделал, но со впуклым у меня тормоз...

Делим четырехугольник на 2 треугольника...
Дальше, надеюсь, решение очевидно.

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

WhPh точно:) гениально просто:) как же я сам не додумался,
спасибо всем

А это какой такой???

Ray Adams Который невыпуклый, но все еще четырехугольник
NF7 вот только проблема все равно может остаться. Предположим, есть такие точки: (0,0),(2,3),(4,0),(2,2). Получается "впуклый" четырехугольник. Берем точку (2,1). Если делить на треугольники с первой точки из четырех, она будет содержаться в большем треугольнике. Если же начинать делить со второй точки, (2,1) выпадет из обоих, что и нужно.

Asteroid угу, прикинул на листике, точно не подходит.

stargaz0r для выпуклого да, но для остального - не всегда

вот здесь например это свойство не подходит.[/quote]

Добавлено спустя 24 минуты, 41 секунду:
http://algolist.manual.ru/maths/geom/belong/poly2d.php
вот здесь есть примерчик:) если кому интересно...

Asteroid

У тебя изначально известно, накая вершина этого невыпуклого четырехугольника невыпукла?
Черт, во загнул

вы меня поражаете))
1)есть решение для треугольника
2)как определить впуклый или выпуклый? берем 3 любые вершины,а 4 считаем точкой и определяем,выходит эта точка за пределы треугольника или нет.
такую проверку выполняем для каждой из 4 вершин. если все вершины находятся вне образовавшихся треугольников-многогранник выпуклый..а если какая вершина оказалась внутри-вот она-то и впуклая...

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

Добавлено спустя 2 минуты, 13 секунд:
ЗЫ: интересно,я вывел чью-то теорему или новую придумал...

предлагаю след решение:
Берем, проводим из точки линии к вершинам, если точка принадлежит четырехугольнику, значи образуется 4 треугольника, сумма площадей которых равна площади данного четырехугольника, однако могут быть проблемы округления, нужно учитывать погрешность при оперировании с данными типа float

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

мой метод эффективнее.

Smoke Хорошо, а если проверить 5-уголник?

Smoke сори, да я воспользовался твоим решением.
Народ, мне надо было в 1 секудну уложится в проверке 1к точек, так что насчет сложности вычисления особого ограничения нету:)

Меня, кстати, тоже


А вот мои пять копеек в копилку человеческих знаний

Дан четырехугольник ABCD и точка:
Допустим, точка не лежит ни на ребрах, ни на диагоналях четырехугольника.
#77
Куда проще взять и проверить принадлежность точки:

• двум треугольникам, образованным сначала одной диагональю (AC: ACB & ACD)
• затем принадлежность двум треугольникам, образованным другой диагональю (BD: BDC & BDA)

1. Если в каждой паре точка принадлежит только одному из треугольников, то эта точка принадлежит четырехугольнику. (см. рисунок 1 -- вЫпуклый четырехугольник)
2. Если точка не принадлежит в одной паре ни одному треугольнику, а во второй паре сразу двум, то тогда эта точка не принадлежит четырехугольнику. (см. рисунок 2 -- впуклый четырехугольник)
3. Если точка не принадлежит вообще ни одному треугольнику в обеих парах, то тут все и так очевидно

Как вам такое решение ?
Итог: требуется всего лишь 4 сравнения (если повезет, то вообще всего лишь 2) против 6-ти у Smoke.

Добавлено спустя 53 минуты, 15 секунд:

Решение интересное, но, возможно, не самое оптимальное.

Пока домой с работы добирался (тоже, кстати, полчаса ) у меня сформировался свой похожий вариант:

На вершинах четырехугольника можно построить 4 разных треугольника.

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

* либо одновременно в двух из них (это максимум);

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

2. На втором этапе рассматриваем те два треугольника, которым точка принадлежит. У них обязательно будет одно общее ребро: AD для первого рисунка (треугольники ADB & ADC) и BD -- для второго (BDA & BDC).

*Если окажется, что не принадлежащая этому ребру вершина одного из треугольников принадлежит другому треугольнику, то это значит, что треугольник "впуклый" и рассматриваемая точка не принадлежит заданному в условии четырехугольнику (для рисунка 2: вершина C принадлежит треугольнику BDA ).

* В противном случае (т.е. если "свободная" вершина каждого из двух треугольников не принадлежат другому треугольнику) можно сказать, что четырехугольник вЫпуклый и интересующая точка ему принадлежит. (для рисунка 1: ни точка C не принадлежит треугольнику ADB, ни точка B не принадлежит треугольнику ADC).

Таким образом поиск решения может закончиться после 3-5-6-ти сравнений -- как повезет

Естественно, самый первый вариант (с диагоналями) мне нравится гораздо больше

xKVtor
все это вроде круто..только на словах... а на деле одно сравнеие не просто сравнеие...
тут надо написать программу на основе обоих алгоритмов и посмотреть какой из них
а)быстрее
б)быстрее и удобнее писать
в)я нифига не догнал как это вообще работает..твой метод...фсе,типа допрограммился.. башка кипит)))

Есть какя-то теорема. Луч выходящий из замкнутого многоугольника (из точки лежащей внутри замкнутого многоугольника) пересекает нечётное количество ГРНАНИЦ оного многоугольника.