... а при нем задача...

← →
Snake2000 (2001-12-24 12:22) [0]

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

(Интересно, додумается ли кто-нибудь из вас до самого оригинального решения - я додумался:) Наверняка и вы!

← →
Внук (2001-12-24 13:27) [1]

Не знаю как насчет оригинального, но приходилось мне однажды писать программу триангуляции. Точка лежит внутри треугольника, если она лежит по одну сторону от каждой прямой, содержащей сторону треугольника, что и противоположная вершина. Решается через анализ знаков векторного произведения соответствующих векторов. Если на стороне - векторное произведение равно нулю (внутри стороны - сравнить длины вектров).

← →
Anatoly Podgoretsky (2001-12-24 14:12) [2]

Ты чего тест на интелектуальность проводишь?

← →
Владислав (2001-12-24 14:58) [3]

Ага. Приз - банка пива "Виртуальное" :)

← →
Digitman (2001-12-24 15:04) [4]

>Snake2000
Ай, молодца !) Ну сам себя не похвалишь - ведь никто тебя не похвалит)
Куда уж там той же конторе под названием Kinetix с ее 3DMax"ом - бедняги стереометрии-то отродясь не знали, им до "самого оригинального решения" твоей задачи - как до луны). Все по старинке, бедолаги, скрывают невидимые грани 3D-объектов...

← →
Digitman (2001-12-24 15:13) [5]

>Snake2000
И еще (позволь уж полюбопытствовать, коль в "Потрепаться" встретились)

Вот этот твой вопрос в "Сетях"

IP (Snake2000 13.12.01 22:54)
[D5, Win95/98] » Как программно сконструировать и отослать IP-пакет???

как-то тоже вяжется с "оригинальными" решениями в векторной 2D-геометрии ?

← →
Digitman (2001-12-24 15:30) [6]

>Внук
А никакие там "длины" сравнивать не надо. При определении принадлежности точки мн-ву точек, лежащих внутри любого замкн.полигона достаточно :
1) Выбрать направление обхода вершин полигона (как правило, выбирается направление "против час.стрелки");
2) В цикле по числу вершин для каждого вектора, образованного ребром полигона, с учетом его направления (соответствующего напр-ю обхода вершин) вычисляется произведение вектора-ребра и вектора, концом которого явл-ся анализируемая точка, а началом - начало вектора-ребра;
3) Если точка лежит внутри полигона, то при заданном направлении обхода вершин все вект.произведения, полученные при каждой итерации цикла, должны иметь один и тот же знак ("+" в случае AntiClockWise-обхода)
4) Если точка лежит вне полигона, то при заданном направлении обхода вершин все вект.произведения, полученные при каждой итерации цикла, должны иметь один и тот же - противоположный - знак ("-" в случае AntiClockWise-обхода)
4) Если точка принадлежит одному из ребер полигона, то при любом направлении обхода вершин одно из вект.произведений, полученных при некоторой итерации цикла, должно иметь значение "0" (это ты верно сказал)

← →
Digitman (2001-12-24 16:21) [7]

>Snake2000
А вот еще твой вопрос:

Здадержка [D5, Win95/98]
Snake2000 © (21.12.01 17:28)
Как реализовать задержку, что бы при выполнении цикла можно было свободно работать с моим приложением? Конструкция типа...

Продвигаешь "оригинальные решения" в векторной 2D-геометрии, а в базовых принципах функц-я Win32-механизма при этом "плаваешь" ... да еще при этом низкоуровневые сетевые протоколы (далеко не тривиальный сабж !) хочешь задействовать.

Как все это у тебя увязывается в единую рабочую схему - совершенно непонятно))

← →
Vitaly (2001-12-24 16:22) [8]

Сумма площадей маленьких треугольников = площади большого.

← →
Внук (2001-12-24 16:23) [9]

>>Digitman ©
Способ мне известен :-) Как вариант (или общий случай для произвольной области). Только там другая трудность (не скажу, что неразрешимая, но все-таки) - находить следующую по часовой стрелке (или против) вершину. Конкретно для треугольника мой способ проще IMHO. Хотя, кажется, мы об одном и том же :) Только еще раз отмечу, для случая выпуклых областей (к коим относится и треугольник), проще пользоваться именно этим свойством - вся фигура лежит в одной стороны от прямой, содержащей любое ее ребро. И векторное произведение - это, собственно, самое простое - вот что я пытался сказать вопрошающему.
>>All
Просто к слову - часто думают, чтобы программировать, не обязательно знать математику. Отсюда такие открытия, как у автора :) (без обид). Аналитическая геометрия и теория выпуклых множеств - учите мат. часть. :)

← →
Внук (2001-12-24 16:28) [10]

>>Digitman ©
Да, а собственно длины считать нужно, чтобы убедиться, что точка лежит на ребре, а не на прямой, содержащей это ребро - в обоих случаях.
Ну совсем забили Snake2000 - а за что? Может я чего пропустил?

← →
panov (2001-12-24 16:30) [11]

Да уж - за что?
Ну хочет человек трояна и Flood"ера написать.
Ну помогите же!

← →
Digitman (2001-12-24 16:38) [12]

>Внук
Да шут с ним, с <Snake2000>. Просто амбиции у него через край бьют...))
А по поводу вычисления модуля ребра - так ведь, если точка не принадлежит ребру, но лежит на прямой, отрезком которой явл-ся это ребро, то для других-то ребер полигона знак вект.произв-я будет ненулевой ! Это ты не принимаешь во внимание разве ? Что и позволит однозначно определить указанную тобой ситуацию с положением точки

← →
Внук (2001-12-24 16:43) [13]

>>Digitman ©
Согласен, этот момент упустил. Зато теперь запомню :)

← →
Юрий Зотов (2001-12-24 17:49) [14]

Ребра, векторы, произведения какие-то... Не знаю такого :о)

type
TTriangle: array[0..2] of TPoint;

function PointInTriangle(T: TTriangle; P: TPoint): boolean;
var
R: HRGN;
begin
R := CreatePolygonRgn(@T, 3, ALTERNATE);
Result := PtInRegion(R, P.X, P.Y);
DeleteObject(R)
end;

← →
Владислав (2001-12-24 17:56) [15]

> Snake2000 © (24.12.01 12:22)

У Юрий Зотов © (24.12.01 17:49) есть все шансы на "Виртуальное" пиво.

Сдаешься?

:-)))

← →
Digitman (2001-12-24 18:11) [16]

>Юрий Зотов
PtInRegion(), к сож., не дает ответа на вопрос, принадлежит ли точка границе региона либо лежит внутри региона (т.е., не лежит на его границе). В любом из этих случаев, судя по описанию вызова, результат будет True

← →
McSimm (2001-12-24 18:18) [17]

>Digitman © (24.12.01 18:11)
>принадлежит ли точка границе региона
Боюсь, что на этот вопрос точного ответа в общем случае не даст ни один машинный метод. Можно говорить только о точке, лежащей достаточно близко к ребру, чтобы считать ее принадлежащей

Могу и ошибаться, буду рад если вы меня переубедите.

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

← →
Digitman (2001-12-24 18:24) [18]

>McSimm
1. Разумеется, погрешность расчетов принимается во внимание.
2. Где ты видишь какие-то там "наезды" ?

← →
Юрий Зотов (2001-12-24 18:59) [19]

> Digitman

Думаю, для виртуального пива сойдет и так. За реальное можно было бы доработать.

← →
McSimm (2001-12-24 19:54) [20]

>Юрий Зотов © (24.12.01 18:59)
От меня лично 3 кружки.
c(~) c(~) c(~)

← →
Юрий Зотов (2001-12-24 20:45) [21]

> McSimm © (24.12.01 19:54)

Спасибо. За Ваше здоровье! Буль... буль... буль...

← →
Владислав (2001-12-25 06:32) [22]

Ну вот.
Началась виртуальная пьянка.

:-)))

А что здесь в 31 декабря твориться будет?
Одумайтесь!

:-)))

← →
McSimm (2001-12-25 12:02) [23]

Боюсь, что 31 здесь как раз будет полный штиль. :)

← →
Voron (2001-12-25 12:17) [24]

2 Snake2000 ©
Оригинальность - понятие субъективное. Что одному кажется оригинальным, другому может показаться заурядным.
Раз ни одно предложенное решение оригинальным Вам не кажется - предложу еще одно, может быть понравится.
Итак, у нас треугольник ABC и точка T.
Берем и считаем углы ATB, ATC, BTC.
Далее:
-если один из углов равен 0 - точка лежит в вершине треугольника,
-если один из углов равен 180 градусам - точка лежит на стороне треугольника,
-если сумма углов менее 360 градусов - точка лежит за пределами треугольника,
-точка лежит внутри треугольника и сумма вышеозначенных углов равна 360 градусов.
Все.

← →
Digitman (2001-12-25 12:47) [25]

>Voron
К сожалению, автор, достопочтенный <Snake2000> до сих пор не удосужился прокомментировать ни одно из своих смелых и не по эпохе прогрессивных заявлений). Поэтому остается только догадываться, в чем суть оригинальности ИМЕННО МАШИННОГО решения задачи по-Snake2000"вски)

А твое решение с углами, хоть и математически верно, все же предполагает программное вычисление углов с задействованием FPU-инструкций, что явно проигрывает по эффективности CPU-инструкциям целочисленной арифметики (а их вполне достаточно для реализации алгоритма расчета вект.произведения, когда координаты вектора - целочисленные), особенно - в приложениях с анимированной векторной графикой.

← →
McSimm (2001-12-25 13:01) [26]

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

Вообще-то, когда я увидел вопрос, я понадеялся что здесь появится что-то в этом роде.

Попробую и я заработать пивка.
Создаем TBitmap. Размер его должен быть таким, чтобы вместить все четыре точки. Рисуем треугольник, например, синим цветом. Делаем его заливку, например, желтым цветом. Осталось взять цвет пиксела по координатам искомой точки. Белый - лежит за пределами, Синий - на стороне или в вершине, Желтый - внутри.
Уничтожаем битмап. (О памяти надо заботиться)

← →
Digitman (2001-12-25 13:10) [27]

>McSimm
Гениально !!! Потрясающе оригинальное решение !!! Да сим ты просто заткнул автора за пояс !!!!))))
Осталось только стребовать законное пивко с <Владислав> - он, кажется, пиво разыгрывал))))))))))

← →
Внук (2001-12-25 13:11) [28]

>>Юрий Зотов © (24.12.01 17:49)
Удар ниже пояса :) Вызовы API-шных функций, занятие GDI-ресурсов, зачем? А если программа под DOS? Понятно, что вопрос вроде бы так не ставился, но это как из пушки по воробьям. Опять же только мое мнение. Что-то вроде того, как если нужно отсортировать строки текстового файла, а для этого советуют создать таблицу БД с нужным индексом, записать туда и прочитать обратно :) Тогда уж давайте вспомним еще и DirectDraw.
Мне не пиво жалко :))) Тенденция, однако ...

← →
Владислав (2001-12-25 13:49) [29]

> Digitman © (25.12.01 13:10)

Это без вопросов!

Все счета (за виртуальное пиво) оплачивает щедрой души Snake2000 © (ну если его кто-нибудь превзойдет).

И так! У нас уже несколько претендентов! Активнее господа! Ящик "виртуального" объемом 10 kB ждет своего победителя!

:)))

Кстати, я так понимаю, что у нас еще один разливающий! Внук © (25.12.01 13:11) "Мне не пиво жалко".

Похвально господа! Спонсоры у нас всегда в цене! Ваше место в мягком кожанном кресле в центре форума!

P.S.: Ну прямо новогоднее настроение!

← →
Digitman (2001-12-25 13:56) [30]

Н-да уж, куда уж более новогодней ему, настроению, быть ...
Всяких виртуальных дедморозов - пруд пруди в форуме ... и всяк веселит народ от души :|

← →
MC TOL (2001-12-25 14:35) [31]

Парни! ВЫ - МОЛДЦЫ!!!

Крайне приятно читать всю эту смесь тонкого юмора и глубоких знаний.
Прямо-таки "Программисты шутят"!

Браво, McSimm! Ящик виртуального от меня тебе лично!

← →
McSimm (2001-12-25 15:16) [32]

За пиво спасибо, но ящик это многовато :)
Не мой размерчик.

Так что разделим всем участникам, угощаю.

← →
Внук (2001-12-25 15:24) [33]

>>Владислав © (25.12.01 13:49) ...Кстати, я так понимаю, что у нас еще один разливающий...
Разливать еще наверное смогу, но вот пить... Сегодня машина сломалась прямо перед работой. Весь день на морозе пляски перед мотором устраиваю вместо исполнения своих прямых обязанностей. Теперь меня никаким пивом не заманите Ж:)

← →
Voron (2001-12-26 07:22) [34]

← →
Wetnose (2001-12-26 08:59) [35]

классический вариант:

type TSide = (side_p, side_m, side_0); TSides = set of TSide; function InOnTr(p, a, b, c: TPoint): TSide; var side: TSides; function Inside(d, e, f: TPoint): TSide; var r1, r2: real; begin r1 := ((p.x-d.x)*(e.y-d.y))/(e.x-d.x)+d.y-p.y; r2 := ((f.x-d.x)*(e.y-d.y))/(e.x-d.x)+d.y-f.y; if r1 * r2 < 0 then Result := side_m else if r1 * r2 > 0 then Result := side_p else Result := side_0; end; begin side := [Inside(a, b, c), Inside(b, c, a), Inside(c, a, b)]; if (side * [side_p, side_m]) = [side_p, side_m] then Result := side_m else if side_0 in side then Result := side_0 else Result := side_p; end;

пример вызова:

case InOnTr(Point(15, 20), Point(10, 30), Point(20, 10), Point(30, 30)) of side_p: ShowMessage("Точка пренадлежит треугольнику"); side_m: ShowMessage("Точка не пренадлежит треугольнику"); side_0: ShowMessage("Точка лежит на стороне треугольника"); end;

← →
McSimm (2001-12-26 10:55) [36]

>Wetnose (26.12.01 08:59)
Не знаю, может метод и классический, но реализация оригинальная. Красиво.
Любители пооптимизировать могут поспорить, но мне понравилось.

>Voron © (26.12.01 07:22)
>А все-таки мне интересно, что там за решение у Snake2000 © , и вообще
>есть ли оно?
Надо найти адреса памяти в Windows, где хранятся точки входа, координаты которых соответствуют поставленной задаче и как нибудь их подкарячить. Только не говорите что это невозможно.

... а при нем задача... Найти похожие ветки