US math :-(
Mike
Вот, нашел на anekdot.ru. Смех смехом, но неужали все так грустно ? Просьба
господам, у которых тут дети ходят в школу: оцените pls достоверность.
---------------------------------------------------------------------------
Сообщение прислано одним из участников форума русскоязычных американцев:
"... и опыт, сын ошибок трудных"
Рассказала коллега. Ее ребенку (3-й класс) дали задачу: "Растение
посадили во вторник. Каждый день площадь, занятая растением,
увеличивается в два раза. В субботу растение займет всю грядку. В какой
день растение займет половину грядки?". Ребенок посчитал дни между
вторником и субботой и сказал "Четверг". "Правильно," - сказала
учительница, - "хотя в ответе в книжке почему-то сказано пятница".
"... и гений, парадоксов друг"
Приходит ребенок из школы. Рассказывает:
- Идет урок Science (физика + немного прочих естественных наук). Учитель
дает задачу: "Машина ехала из пункта А в пункт В со скоростью 60 миль в
час, из B в C со скоростью 40 миль/час, из C в D со скоростью 20
миль/час. Требуется вычислить СРЕДНЮЮ СКОРОСТЬ В СЕКУНДАХ" (Комментарий:
при таких условиях среднюю скорость посчитать вообще невозможно, надо
знать либо расстояния, либо время движения между пунктами, потому что
средняя скорость - это совсем не то же самое, что среднее арифметическое
указанных чисел, хотя, видимо, именно это и имелось в виду. О том, что
скорость вообще в секундах не меряется, даже не говорим.) Дети не
поняли, что от них нужно. Учитель объясняет:
- Поскольку нам нужны секунды, и в одной минуте 60 секунд, в одном часе
60 минут, то сначала умножаем 60 на 60 на 60. Далее действуем ПО
АНАЛОГИИ: УМНОЖАЕМ 40 НА 40 НА 40, 20 НА 20 НА 20, ВСЕ СКЛАДЫВАЕМ И
ДЕЛИМ НА ТРИ. Получаем среднюю скорость в секундах.
Ребенок еще говорил, что потом учитель считал среднюю скорость в милях в
час, и получил 38.6 (при начальных числах 60, 40, 20).
"... случай, Бог-изобретатель"
Еще одни знакомые рассказали. Заглянули к дочери в домашнюю работу, а
там - деление на ноль. Папа в объяснения - так нельзя, а дочь говорит -
это вас в России так учили, а нас тут в Америке так учат, и на ноль
делить у нас можно, ноль получается. Папа еще раз объясняет, почему
нельзя. Дочка умом вроде поняла, сердечной склонности не поменяла - в
школе говорят "можно", значит можно. "Хорошо", - говорит папа, - "пойду
завтра в школу, устрою море крови и отучу их там делить на ноль". Наутро
дочь подходит к отцу: "Папа, я все поняла. Я НИКОГДА больше не буду
делить на ноль. ПОЖАЛУЙСТА, не ходи в школу..."
Все это было бы смешно, когда бы не было так грустно.
--
Best regards
(M)ike
Лучшее лекарство от порчи, сглаза и НЛО: http://www.skeptik.net
При ответе на e-mail убрать из адреса DEL
Dmitry Krivitsky
>
>Вот, нашел на anekdot.ru. Смех смехом, но неужали все так грустно ? Просьба
>господам, у которых тут дети ходят в школу: оцените pls достоверность.
http://nauka.relis.ru/cgi/nauka.pl?01+0012+01012002+HTML
Mike
> http://nauka.relis.ru/cgi/nauka.pl?01+0012+01012002+HTML
Спасибо, эта глупая статья уже в эхе обсуждалась и она останется на
совести "Науки и жизни". Я бы предпочел мнение очевидцев, причем
именно о "средней школе".
Max Alginin
>> Вот, нашел на anekdot.ru. Смех смехом, но неужали все так грустно ? Просьба
>> господам, у которых тут дети ходят в школу: оцените pls достоверность.
>
Это все из-за обуви.
Max
Arcady Schekochikhin
>
> Dmitry Krivitsky wrote:
> > http://nauka.relis.ru/cgi/nauka.pl?01+0012+01012002+HTML
>
> Спасибо, эта глупая статья уже в эхе обсуждалась и она останется на
> совести "Науки и жизни". Я бы предпочел мнение очевидцев, причем
> именно о "средней школе".
У меня пацан в 5th grade. Учебников у них толком нет, второй год
складывают 5+7 в разных вариантах - все в общем как описано.
У друзей дети в Пало Альто учатся - 2nd & 9th grades - у старшей
смотрел учебники по математике/геометрии - все как в СССР в лучшие
времена (для обучения) - хорошие учебники, хорошие задачи, много
дают и много спрашивают. Причем девченка ходила сразу и в middle
и в high на математику - продвинутая.
Так что - тенденция есть, но сильно зависит от школы. В общем-то
того среднего уровня который я помню в СССР (25 лет назад) тут нет,
да его и в России больше нет.
Аркадий
Alexander Murzin
news:1b8a257.01101...@posting.google.com...
> Hi!
>
> Вот, нашел на anekdot.ru. Смех смехом, но неужали все так грустно ?
Просьба
> господам, у которых тут дети ходят в школу: оцените pls достоверность.
>
> --------------------------------------------------------------------------
-
> Сообщение прислано одним из участников форума русскоязычных американцев:
>
> "... и опыт, сын ошибок трудных"
>
> Рассказала коллега. Ее ребенку (3-й класс) дали задачу: "Растение
> посадили во вторник. Каждый день площадь, занятая растением,
> увеличивается в два раза. В субботу растение займет всю грядку. В какой
> день растение займет половину грядки?". Ребенок посчитал дни между
> вторником и субботой и сказал "Четверг". "Правильно," - сказала
> учительница, - "хотя в ответе в книжке почему-то сказано пятница".
У меня под рукой не оказалось учительницы:))
Я только что задал это вопрос 10ти американцам и 10 русским.
Образование американцев - у всех выше колледжа, у русских не уверен, но
больше чем 10летка.
Возраст 30-40 лет. Среди американцев две женщины, среди русских - 3
Ответы -
американцы - 10 из 10 правильно в пределах 30 секунд
русские - 6 из 10 неправильно в пределах минуты.
Не надо кидаться по поводоу нерепрезантативности выборки:)))
--
Alexander Murzin {abm-at-coastalrecovery-com}
Если вопрос правильно поставить, он долго простоит.
------
Zion Wiseman
news:9q4nsv$1htn$1...@ddt.demos.su...
> Я только что задал это вопрос 10ти американцам и 10 русским.
> Образование американцев - у всех выше колледжа, у русских не уверен, но
> больше чем 10летка.
> Возраст 30-40 лет. Среди американцев две женщины, среди русских - 3
> Ответы -
> американцы - 10 из 10 правильно в пределах 30 секунд
> русские - 6 из 10 неправильно в пределах минуты.
Колледж - это очень существенно.
Объяснение лежит на поверхности - многие русские из
мест с суровым климатом, где марихуана не произрастает
и соответственно грядки никто не засаживает.
--
I'm NOT union and proud of it
Отправлено через сервер Talk.Ru - http://www.talk.ru
Tatiana A. Zhdanova
> "... и опыт, сын ошибок трудных"
>
> Рассказала коллега. Ее ребенку (3-й класс) дали задачу: "Растение
> посадили во вторник. Каждый день площадь, занятая растением,
> увеличивается в два раза. В субботу растение займет всю грядку. В какой
> день растение займет половину грядки?". Ребенок посчитал дни между
> вторником и субботой и сказал "Четверг". "Правильно," - сказала
> учительница, - "хотя в ответе в книжке почему-то сказано пятница".
Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
На решение у меня ушло 30 минут... У ребёнка вечером спрошу :)
Татьяна.
Konstantin Novik
"Tatiana A. Zhdanova" <anton...@home.com> wrote in message
> "Mike" <mik...@skeptik.net> wrote in message
> > "... и опыт, сын ошибок трудных"
> >
> > Рассказала коллега. Ее ребенку (3-й класс) дали задачу: "Растение
> > посадили во вторник. Каждый день площадь, занятая растением,
> > увеличивается в два раза. В субботу растение займет всю грядку. В какой
> > день растение займет половину грядки?". Ребенок посчитал дни между
> > вторником и субботой и сказал "Четверг". "Правильно," - сказала
> > учительница, - "хотя в ответе в книжке почему-то сказано пятница".
>
> Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
> На решение у меня ушло 30 минут...
Wow! Это даже не "пять" - это уже я-не-знаю-что...
K.N.
--
Max Alginin
>> Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
>> На решение у меня ушло 30 минут...
>
> Wow! Это даже не "пять" - это уже я-не-знаю-что...
Не спугни.
Max
Felix Kogan
"Tatiana A. Zhdanova" wrote:
> Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
Ну, так об том и речь, как я понимаю.
Мой сын учится в частной школе, очень неплохой по учительскому и ученическому
составу, но математика там не на самом высоком уровне. Поэтому сейчас с ним
дед занимается по русским учебникам, а как 10 лет стукнет, так он пойдет в
субботнюю школу при Брукли-Колледже, где всякие МГУшные профессора детишек
мучают.
А еще я недавно на Брайтоне набрел на ПСС Сканави. 5, что-ли, томов. И такая
меня ностальгия взяла, что я чуть было не купил.Надо будет, наверное...
--
Kogan the Barbarian <kog...@deshaw.com>
Chaos always defeats order, because it's better organized.
Terry Pratchett
Andrey Zuban
"Tatiana A. Zhdanova" <anton...@home.com> wrote in message news:9q4umo$2qqp$1...@ddt.demos.su...
Расскажи, как решала, Татьяна.
____________
Andrey Zuban
Tatiana A. Zhdanova
"Konstantin Novik" <nov...@hotmail.com> wrote in message
news:9q4uv1$brk$1...@host.talk.ru...
> > > "... и опыт, сын ошибок трудных"
> > >
> > > Рассказала коллега. Ее ребенку (3-й класс) дали задачу: "Растение
> > > посадили во вторник. Каждый день площадь, занятая растением,
> > > увеличивается в два раза. В субботу растение займет всю грядку. В
какой
> > > день растение займет половину грядки?". Ребенок посчитал дни между
> > > вторником и субботой и сказал "Четверг". "Правильно," - сказала
> > > учительница, - "хотя в ответе в книжке почему-то сказано пятница".
> >
> > Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
> > На решение у меня ушло 30 минут...
>
> Wow! Это даже не "пять" - это уже я-не-знаю-что...
try круглую грядку ala "клумба" с представлением функции раста через время
:-P
Татьяна.
Dmitry Krivitsky
Раз уж тут речь зашла о задачках.
Меня как-то озадачили такой простенькой задачкой, по программированию
(а на самом деле, по математике).
Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
считать, что без самопересечений). Задана в виде набора координат вершин.
Дана также произвольная точка на экране компьютера (координаты).
Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
Решение пока не привожу: может, кому-то будет интересно порешать. :-)
gek
мере).
> >> На решение у меня ушло 30 минут...
> >
> > Wow! Это даже не "пять" - это уже я-не-знаю-что...
>
> Не спугни.
А я допер почему в четверг. В пятницу все стараются уйти с работы пораньше.
Растению видно тоже влом расти по полной программк, а deadline в субботу.
Вот оно в четверг и выпросло до пятничного размера.
:)
Zion Wiseman
> try круглую грядку ala "клумба" с представлением функции раста через время
Эту задачу просто надо решать с конца. Как с той задачкой о прямом
наследнике Генриха Х.
--
I'm NOT union and proud of it
Alexander Murzin
"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
news:9q4vnn$30je$1...@ddt.demos.su...
> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> считать, что без самопересечений). Задана в виде набора координат вершин.
Надо полагать что набор упорядочен по номерам точек?
Т.е. можно взять две последовательные точки в наборе и провести между ними
линию?
Или набор хаотически заполнен?
Или для решение настолько элегантно что это не важно?
> Дана также произвольная точка на экране компьютера (координаты).
> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
--
Zion Wiseman
> (а на самом деле, по математике).
> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> считать, что без самопересечений). Задана в виде набора координат вершин.
> Дана также произвольная точка на экране компьютера (координаты).
> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
>
Poly(...)
GetPixel()
Эта? :-)
--
I'm NOT union and proud of it
Tatiana A. Zhdanova
"Andrey Zuban" <and...@zuban.com> wrote in message
news:9q4vld$u4h$1...@gw.liquidhome.com...
> > > "... и опыт, сын ошибок трудных"
> > >
> > > Рассказала коллега. Ее ребенку (3-й класс) дали задачу: "Растение
> > > посадили во вторник. Каждый день площадь, занятая растением,
> > > увеличивается в два раза. В субботу растение займет всю грядку. В
какой
> > > день растение займет половину грядки?". Ребенок посчитал дни между
> > > вторником и субботой и сказал "Четверг". "Правильно," - сказала
> > > учительница, - "хотя в ответе в книжке почему-то сказано пятница".
> >
> > Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
> > На решение у меня ушло 30 минут... У ребёнка вечером спрошу :)
>
> Расскажи, как решала, Татьяна.
Координаты осей (площадь занятая растением, грядка) Функция роста =
2*(площадь растения) (поскольку при данных условиях можно пренебречь более
сложной зависимостью) Дальше задача сводится к тривиальной, с ответом "на
четвёртый день" т.е. "пятница".
Татьяна.
Dmitry Krivitsky
>------
>"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
>news:9q4vnn$30je$1...@ddt.demos.su...
>> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
>> считать, что без самопересечений). Задана в виде набора координат вершин.
>
>Надо полагать что набор упорядочен по номерам точек?
Да.
>Т.е. можно взять две последовательные точки в наборе и провести между ними
>линию?
Да.
Первая точка соединена со второй, вторая - с третьей, и т.д., последняя - снова с первой.
>Или набор хаотически заполнен?
Нет.
Порядок точек известен, и его менять нельзя.
Ломаная замкнутая, без самопересечений, но не обязательно выпуклая.
Alexander Murzin
"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
news:9q4vnn$30je$1...@ddt.demos.su...
> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> считать, что без самопересечений). Задана в виде набора координат вершин.
> Дана также произвольная точка на экране компьютера (координаты).
> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
>
> Решение пока не привожу: может, кому-то будет интересно порешать. :-)
Проводим линию от точки в любом направлении до границы экрана.
Если эта линия пересечет границу фигуры четное количество раз - точка вне
фигуры и наоборот.
gek
> 2*(площадь растения) (поскольку при данных условиях можно пренебречь более
> сложной зависимостью) Дальше задача сводится к тривиальной, с ответом "на
> четвёртый день" т.е. "пятница".
стандартного решения ничего в голову не пришло :)
А кстати хорошая постановка задачи с условием на границе.
Yuriy Shalak
"Alexander Murzin" <a...@CoastalRecovery.com> wrote in message
> ------
> "Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
> news:9q4vnn$30je$1...@ddt.demos.su...
> > Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> > считать, что без самопересечений). Задана в виде набора координат
вершин.
>
> Надо полагать что набор упорядочен по номерам точек?
> Т.е. можно взять две последовательные точки в наборе и провести между ними
> линию?
> Или набор хаотически заполнен?
Если хаотически - то задача для некоторых точек не
имеет однозначного решения.
Dmitry Krivitsky
>------
>"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
>news:9q4vnn$30je$1...@ddt.demos.su...
>> (а на самом деле, по математике).
>> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
>> считать, что без самопересечений). Задана в виде набора координат вершин.
>> Дана также произвольная точка на экране компьютера (координаты).
>> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
>>
>> Решение пока не привожу: может, кому-то будет интересно порешать. :-)
>
>Проводим линию от точки в любом направлении до границы экрана.
>Если эта линия пересечет границу фигуры четное количество раз - точка вне
>фигуры и наоборот.
1. Точное определение "пересечения границы" вместе с алгоритмом его
нахождения - в студию.
2. Пересечение может быть и в одной из вершин.
(Намек: как отличать "пересечение" от "касания"?)
Sergey Kubushin
Тю! А чего там вообще решать-то? Если каждый день площадь увеличивается в
два раза, то пол-грядки будет в день, предшествовавший тому, когда стала
целая грядка... Даже считать ничего не надо...
---
Sergey Kubushin Sr. Unix Administrator
Metavante, Inc. Phone: 702-567-8857
874 American Pacific Dr, Fax: 702-567-8808
Henderson, NV 89014
Konstantin Novik
"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message...
> Alexander Murzin пишет в сообщении <9q50on$5ql$1...@ddt.demos.su> ...
> >Проводим линию от точки в любом направлении до границы экрана.
> >Если эта линия пересечет границу фигуры четное количество раз - точка вне
> >фигуры и наоборот.
>
> 1. Точное определение "пересечения границы" вместе с алгоритмом его
> нахождения - в студию.
Э? Для определенности будем рассматривать точку границы экрана всегда одну и
ту же - (0,0). Просматриваются пересечения прямой, проходящей через заданую
точку и (0,0), со всеми прямыми, задаными парами вершин фигуры. Если они
пересекаются внутри отрезка между вершинами - пересечение границы есть. Если
вне - пересечения границы нет.
> 2. Пересечение может быть и в одной из вершин.
>
> (Намек: как отличать "пересечение" от "касания"?)
Проверять на совпадение точку пересечения с одной из вершин фигуры. И
игнорировать ее в этом случае (или считать за два пересечения).
Alexander Murzin
То что я привел - это общее решение.
1.Пересечение границы - пересечение линии, соединяющей две соседние точки
( т.е. грубо говоря границы фигуры) - это достаточно точное определение?
2.Прохождение через вершину считается двойным пересечением.
дополнение - ноль пересечений - точка вне фигуры
совпадение с одной из линий ( не помню как правильно это в геометрии
называется) - надо начинать строить новую линию:))))
--
Alexander Murzin {abm-at-coastalrecovery-com}
Если вопрос правильно поставить, он долго простоит.
------
>
>
Konstantin Novik
"Sergey Kubushin" <k...@cyberbills.com> wrote...
> Tatiana A. Zhdanova <anton...@home.com> wrote:
> > Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
> > На решение у меня ушло 30 минут... У ребёнка вечером спрошу :)
>
> Тю! А чего там вообще решать-то? Если каждый день площадь увеличивается в
> два раза, то пол-грядки будет в день, предшествовавший тому, когда стала
> целая грядка... Даже считать ничего не надо...
Ну вот - спугнул :-(...
Konstantin Novik
"Anton Solovyev" <sol...@louisville.stortek.com> wrote...
> Alexander Murzin wrote:
> > Проводим линию от точки в любом направлении до границы экрана.
> > Если эта линия пересечет границу фигуры четное количество раз - точка
вне
> > фигуры и наоборот.
>
> Тебе нужна точка вне области, а не граница экрана. Наверное, можно просто
> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
> области), и уж тогда проводить линию.
Наверное, точку (0,0) легче взять, чем "отходить наружу"?
> И придется считать пересечения это линии
> с каждой прямой, образуюшей область.
Ну. А как иначе?
Alexander Murzin
Еще раз повторю - это самое общее описание алгоритма решения.
Причем правильного алгоритма.
Или если бы я написал на каком то алгоритмическом языке и сделал бы ошибку,
Вы бы тоже сказали что решение не верно потому что код нерабочий?
Felix Kogan
Anton Solovyev wrote:
> Тебе нужна точка вне области, а не граница экрана. Наверное, можно просто
> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
> области), и уж тогда проводить линию. И придется считать пересечения это линии
> с каждой прямой, образуюшей область.
Ерунда. Берем две соседствующие вершины. Рассчитываем координаты середины стороны.
Через эту и заданную точку проводим линию. И вася-кот.
Andrew Maltsev
> Раз уж тут речь зашла о задачках.
> Меня как-то озадачили такой простенькой задачкой, по программированию
> (а на самом деле, по математике). Дано: замкнутая ломаная линия
> на экране компьютера (будем для простоты считать, что без
> самопересечений). Задана в виде набора координат вершин. Дана также
> произвольная точка на экране компьютера (координаты). Найти: находится
> точка внутри области, ограниченной ломаной, или снаружи.
Чтобы народ посмешить я могу сказать как решал такую задачу в школьные
годы - во временном буфере закрашивал внутреннюю часть сей фигуры и
смотрел закрасится-ли точка :) Компутер звали "Агат". Мне тогда
оказалось легче придумать алгоритм закраски, чем придумать решение.
Alexander Murzin
news:3BC60A65...@louisville.stortek.com...
>
> Alexander Murzin wrote:
>
> >
> > Проводим линию от точки в любом направлении до границы экрана.
> > Если эта линия пересечет границу фигуры четное количество раз - точка
вне
> > фигуры и наоборот.
> >
>
> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
> области), и уж тогда проводить линию. И придется считать пересечения это
линии
> с каждой прямой, образуюшей область.
>
>
--
Alexander Murzin {abm-at-coastalrecovery-com}
Если вопрос правильно поставить, он долго простоит.
------
--
>
> Anton Solovyev
>
Alexander Murzin
news:3BC60A65...@louisville.stortek.com...
>
> Alexander Murzin wrote:
>
> >
> > Если эта линия пересечет границу фигуры четное количество раз - точка
вне
> > фигуры и наоборот.
> >
>
> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
> области), и уж тогда проводить линию. И придется считать пересечения это
линии
> с каждой прямой, образуюшей область.
Заданная фигура не залазит за экран, не так ли?
Если так, тогда любая точка на границе экрана считается вне пределов фигуры.
Если не так - можно начать строить линию до точки одна из координат которых
больше максимальной координаты точек образующих фигуру.
Еще раз - все это частные случаи, которые не противоречят общему алгоритму.
--
Alexander Murzin {abm-at-coastalrecovery-com}
Если вопрос правильно поставить, он долго простоит.
------
>
> --
>
> Anton Solovyev
>
Anton
человека незнакомого с вычислительной геометрией. В принципе находится в
начале любой книги по предмету.
"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
news:9q51gi$9mi$1...@ddt.demos.su...
gek
Alexander Murzin
1.выбираем точку явно за пределами фигуры ( по максимальным координатам
можно)
2.проводим воображему линию от исходной точки до выбранной точки
3.Считаем пересечения. причем пересечение вершины фигуры считаем за двойное.
Осень: если насчитали четное количество - точка вне фигуры, нечетное -
внутри.
Дополнение - при попадании на одну из линий, образующих фигуру, процесс
повторить с пункта 1 с выбором другой воображаемой точки и сбросом счетчика
перечислений.
Вариантов нет. Рещение правильное и обжалованию не подлежит..
Только не рассказывайте мне про случаи когда точка лежит на границе фигуры
или линий столько много, что нельзя выбрать несовпадающую.
Так же не принимаются возражения по поводу погрешности вычисления точных
координат точек линий при сравнение на совпадение.:)))
--
Alexander Murzin {abm-at-coastalrecovery-com}
Если вопрос правильно поставить, он долго простоит.
------
"Konstantin Novik" <nov...@hotmail.com> wrote in message
news:9q5277$re8$1...@host.talk.ru...
Andrey Tarasevich
> ...
> 1. Точное определение "пересечения границы" вместе с алгоритмом его
> нахождения - в студию.
Классический алгоритм:
Горизонтальные отрезки границы вообще в расчет не принимаются.
Пересечение границы - это наличие у нашей горизонтали H общей точки хотя
бы с одним отрезком границы (алгоритм нахождения пересечения не
привожу).
Особый случай: если общая точка горизонтали H совпадает с концом одного
из отрезков. Тогда существует еще ровно один отрезок, который тоже
персекается с горизонталью H в своем конце. Если эти вторые точки этих
двух отрезков лежат по одну сторону от H, то считаем, что пересечения
нет. Если по разные стороны - считаем одно пересечение.
В остальных случаях каждое пересечение H с отрезком границы - это одно
пересечение.
> 2. Пересечение может быть и в одной из вершин.
>
> (Намек: как отличать "пересечение" от "касания"?)
Охвачено.
Best regards,
Андрей.
Andrey Tarasevich
> ...
> >
> > Проводим линию от точки в любом направлении до границы экрана.
> > Если эта линия пересечет границу фигуры четное количество раз - точка вне
> > фигуры и наоборот.
> >
>
> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
> с каждой прямой, образуюшей область.
Никакая вторая точка не нужна. Считаем пересечения горизонтального луча,
выходящего из нашей точки вправо (в бесконечность), с границей области.
Для этого просто напросто считаем персечения границы области с
горизонтальной линией, проходящей через нашу точку, которые лежат справа
от этой точки.
Best regards,
Андрей.
Konstantin Novik
"Anton Solovyev" <sol...@louisville.stortek.com> wrote...
> Dmitry Krivitsky wrote:
> > 1. Точное определение "пересечения границы" вместе с алгоритмом его
> > нахождения - в студию.
> > 2. Пересечение может быть и в одной из вершин.
> >
> > (Намек: как отличать "пересечение" от "касания"?)
>
> Можно так -- начинаем обходить фигуру, и для каждой вершины проверяем, что
> точка находится во "внутреннем" секторе, образованном двумя лучами,
исходящими
> из вершины.
А как определить, какой сектор - "внутренний"? Фигура-то может быть
невыпуклой.
Konstantin Novik
"Anton Solovyev" <sol...@louisville.stortek.com> wrote...
> Konstantin Novik wrote:
> > > Тебе нужна точка вне области, а не граница экрана. Наверное, можно
просто
> > > взять вершину и отойти в сторону наружу (базируясь на направлении
обхода
> > > области), и уж тогда проводить линию.
> >
> > Наверное, точку (0,0) легче взять, чем "отходить наружу"?
>
> А если она внутри?
Фигура замкнута по условиям задачи. Значит, не налезает на границу экрана.
Vadim Zaliva
> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> считать, что без самопересечений). Задана в виде набора координат вершин.
> Дана также произвольная точка на экране компьютера (координаты).
> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
Решается очень просто. Выбирается произвольная начальная точка и от нее
проходится по кругу. Для каждой пары точек определяется с какой стороны от
прямой проходящей через эту пару находится данная точка. Если для всех
отрезков проверяемая точка находится с одной стороны (не важно с какой) то
она внутри.
Проверка с какой стороны делается вот так:
http://www-2.cs.cmu.edu/~quake/robust.html
(лень набивать формулы).
Грубо говоря если знаки всех детерминантов совпадают, то она внутри.
Вадим
--
;;----------------------------------+-----------------------------------+
;; Vadim Zaliva + Those who do not understand Unix +
;; mailto:lo...@crocodile.org + are condemned to reinvent it, +
;; http://www.crocodile.org + poorly. (H. Spencer) +
;;----------------------------------+-----------------------------------+
Andrey Tarasevich
>
> Еще раз, подробно..чтобы не было вопросов.
> 1.выбираем точку явно за пределами фигуры ( по максимальным координатам
> можно)
> 2.проводим воображему линию от исходной точки до выбранной точки
> 3.Считаем пересечения. причем пересечение вершины фигуры считаем за двойное.
> Осень: если насчитали четное количество - точка вне фигуры, нечетное -
> внутри.
> Дополнение - при попадании на одну из линий, образующих фигуру, процесс
> повторить с пункта 1 с выбором другой воображаемой точки и сбросом счетчика
> перечислений.
>
> Вариантов нет. Рещение правильное и обжалованию не подлежит..
Решение правильное, но кривое. Настоящее правильное решение приведено в
моем соседнем письме.
Best regards,
Андрей.
gek
> Меня как-то озадачили такой простенькой задачкой, по программированию
> считать, что без самопересечений). Задана в виде набора координат вершин.
> Дана также произвольная точка на экране компьютера (координаты).
> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
>
А решение - он и есть.
Andrey Tarasevich
>
> > > > Тебе нужна точка вне области, а не граница экрана. Наверное, можно
> просто
> > > > взять вершину и отойти в сторону наружу (базируясь на направлении
> обхода
> > > > области), и уж тогда проводить линию.
> > >
> > > Наверное, точку (0,0) легче взять, чем "отходить наружу"?
> >
> > А если она внутри?
>
> Фигура замкнута по условиям задачи. Значит, не налезает на границу экрана.
>
Во-первых, считать пересечения ребер с негоризонтальным отрезком
(точка)-(0,0) сложнее, чем с горизонтальной прямой.
Во-вторых, дестыительно нет гарантии, что (0, 0) - снаружи.
В-третих, не нужно все это.
Best regards,
Андрей.
Konstantin Novik
> Alexander Murzin wrote:
> > Заданная фигура не залазит за экран, не так ли?
>
> Какой к лешему "экран" ???
1) :-)). Читать умеешь?
2) Можно заменить экран прямоугольником, включающим фигуру с запасом,
построенным по максимумам и минимумам координат +/- чего-нибудь.
3) Но это не нужно :-).
Sergey Lelyushkin
>> Проводим линию от точки в любом направлении до границы экрана.
>> Если эта линия пересечет границу фигуры четное количество раз - точка
>> вне фигуры и наоборот.
>>
>
> Тебе нужна точка вне области, а не граница экрана. Наверное, можно
> просто взять вершину и отойти в сторону наружу (базируясь на
> направлении обхода области), и уж тогда проводить линию.
Область может быть не выпуклая, потому "базируясь на направлении обхода"
вряд ли получится. Точка заведомо снаружи - это любая точку у которой
каждая из координат будет меньше чем соответсвующая координата у любой из
вершин многоугольника.
> И придется
> считать пересечения это линии с каждой прямой, образуюшей область.
То есть надо просто найти в одной ли полуплоскости относительно прямой,
проходящей через нашу точку и выбранную точку снаружи, находится каждая
пара смежных вершин. Вроде как есть довольно простая формула для этого.
Ну и, как уже указали, нужно будет отдельно просчитать варианты когда
вершина попадет на проведенную нами прямую.
--
Sergey
Atascadero, CA
o...@bellatlantic.net
> "Sergey Kubushin" <k...@cyberbills.com> wrote...
>> Tatiana A. Zhdanova <anton...@home.com> wrote:
>> > Не правильно.Ответ "пятница" (в предложенном переводе, по крайней мере).
>> > На решение у меня ушло 30 минут... У ребёнка вечером спрошу :)
>>
>> Тю! А чего там вообще решать-то? Если каждый день площадь увеличивается в
>> два раза, то пол-грядки будет в день, предшествовавший тому, когда стала
>> целая грядка... Даже считать ничего не надо...
> Ну вот - спугнул :-(...
Да она стебалась.
--
Const Okrainets
Andrey Tarasevich
> ...
> > Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> > считать, что без самопересечений). Задана в виде набора координат вершин.
> > Дана также произвольная точка на экране компьютера (координаты).
> > Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
>
> Решается очень просто. Выбирается произвольная начальная точка и от нее
> проходится по кругу. Для каждой пары точек определяется с какой стороны от
> прямой проходящей через эту пару находится данная точка. Если для всех
> отрезков проверяемая точка находится с одной стороны (не важно с какой) то
> она внутри.
Слышал звон да не знал где он. Это работает только для выпуклой области.
Best regards,
Андрей.
Andrey Tarasevich
Неверно. Симплекс работает на выпуклых областях.
Best regards,
Андрей.
Yuriy Shalak
"gek" <he...@cavasoft.com> wrote in message
news:9q534l$up0$1...@gw.liquidhome.com...
> > 2.Прохождение через вершину считается двойным пересечением.
> а если я пересек вершину идя из фигуры?
Брать другое направление. Лучше всего - как Феликс
предложил - среднее между двумя ближайшими (по одной
из координат) вершинами.
Andrey Tarasevich
>
> Особый случай: если общая точка горизонтали H совпадает с концом одного
> из отрезков. Тогда существует еще ровно один отрезок, который тоже
> персекается с горизонталью H в своем конце. Если эти вторые точки этих
> двух отрезков лежат по одну сторону от H, то считаем, что пересечения
> нет. Если по разные стороны - считаем одно пересечение.
>
Уточнение: ... Тогда существует еще ровно один _соседний_ отрезок
(считаем, что горизонтальных ребер в границе нет), который тоже
пересекается с горизонталью H в своем конце ...
Best regards,
Андрей.
Vadim Zaliva
> Слышал звон да не знал где он. Это работает только для выпуклой области.
Я не внимательно прочитал условия. Когда я занимался подобными штуками все
начиналось с разбития на выпуклые подфигуры (обычно с триангуляции).
Потому что в большинстве реальных задач там и полости бывают и
самопересечения и писать алгоритмы для столь обширного класса фигур
сложно: проще разбить на выпуклые и с ними работать.
Andrey Tarasevich
> ...
> для каждой вершины:
>
> 1. считаем угол между лучом проведенным из вершины в вершину + 1 (угол1) и
> горизонтальной осью
>
> 2. считаем угол между лучом проведенным из вершины в вершину - 1 (угол2) и
> горизонтальной осью
>
> 2. считаем угол между лучом из вершины в точку под вопросом и горизонтальной
> осью (угол3)
>
> 3. Если угол1 < угол3 < угол2, движемся дальше, иначе точка лежит вне области.
>
> Интуитивно экономнее, чем считать пересечение с каждой прямой.
> ...
Очевидно, что не работает. Для любой заранее заданной тройки соседних
вершин ломаной и любого расположения тестовой точки можно достроить
ломаную до замкнутой (без пересечений) так, что тестовая точка будет
внутри.
Best regards,
Андрей.
Andrey Tarasevich
>
> Andrey Tarasevich <atara...@telocity.com> wrote:
>
> > Слышал звон да не знал где он. Это работает только для выпуклой области.
>
> Я не внимательно прочитал условия. Когда я занимался подобными штуками все
> начиналось с разбития на выпуклые подфигуры (обычно с триангуляции).
> Потому что в большинстве реальных задач там и полости бывают и
> самопересечения и писать алгоритмы для столь обширного класса фигур
> сложно: проще разбить на выпуклые и с ними работать.
Согласен. Но это чаще делают при решении массовой задачи (т.е. когнда
тестовых точек много). И разбивать можно на трапеции. Если и точек
много, и ломаных много - то тут уже рулит алгорим сканирцющей прямой.
Для единичной задачи хорошо подходит именно тест на кол-во пересечений с
горизонталью.
Best regards,
Андрей.
Nikita V. Belenki
>> Особый случай: если общая точка горизонтали H совпадает с концом одного
>> из отрезков. Тогда существует еще ровно один отрезок, который тоже
>> персекается с горизонталью H в своем конце. Если эти вторые точки этих
>> двух отрезков лежат по одну сторону от H, то считаем, что пересечения
>> нет. Если по разные стороны - считаем одно пересечение.
AT> Уточнение: ... Тогда существует еще ровно один _соседний_ отрезок
AT> (считаем, что горизонтальных ребер в границе нет), который тоже
AT> пересекается с горизонталью H в своем конце ...
Или два. А ещё точка может лежать на одном из отрезков.
Короче, после десятой итерации это решение заработает.
Kit.
PS/1. Есть ещё одно решение, тоже простое на вид и муторное (но несколько
по-иному) в исполнении. Сумма углов (со знаками), под которыми видны все
отрезки. Hоль, если снаружи.
Tatiana A. Zhdanova
> > Координаты осей (площадь занятая растением, грядка) Функция роста =
> > 2*(площадь растения) (поскольку при данных условиях можно пренебречь
более
> > сложной зависимостью) Дальше задача сводится к тривиальной, с ответом
"на
> > четвёртый день" т.е. "пятница".
> Вот в такие моменты я чуствую себя идиотом. Потому что мне кроме
> стандартного решения ничего в голову не пришло :)
Мне тоже, только вот торопилась очень, и вместо "день роста" "грядка"
написала :(
> А кстати хорошая постановка задачи с условием на границе.
Да, это самый скользкий момент в задаче - в началах координат считать первый
день как "1" или как "0". Понятно дело, что тогда другой край по этой оси
будет или "4" или "5". поэтому лучше, как дни недели :) (вот в этот раз я не
стебусь, определенный интеграл будет иметь соответственно границы
"вторник" - нижняя и "суббота" - верхняя, а "вычитание" из вторника
субботы - это не два байта пересылать :))
Татьяна.
Dmitry Krivitsky
>"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
>news:9q51gi$9mi$1...@ddt.demos.su...
>> Alexander Murzin пишет в сообщении <9q50on$5ql$1...@ddt.demos.su> ...
>> >------
>> >"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message
>> >news:9q4vnn$30je$1...@ddt.demos.su...
>> >> (а на самом деле, по математике).
>> >> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
>> >> считать, что без самопересечений). Задана в виде набора координат
>вершин.
>> >> Дана также произвольная точка на экране компьютера (координаты).
>> >> Найти: находится точка внутри области, ограниченной ломаной, или
>снаружи.
>> >>
>> >
>> >Проводим линию от точки в любом направлении до границы экрана.
>> >Если эта линия пересечет границу фигуры четное количество раз - точка вне
>> >фигуры и наоборот.
>>
>> нахождения - в студию.
>> 2. Пересечение может быть и в одной из вершин.
>>
>> (Намек: как отличать "пересечение" от "касания"?)
>
>1.Пересечение границы - пересечение линии, соединяющей две соседние точки
>( т.е. грубо говоря границы фигуры) - это достаточно точное определение?
>2.Прохождение через вершину считается двойным пересечением.
То же самое, что у Новика.
Пример.
Квадрат с вершинами:
(10, 10)
(20, 10)
(20, 20)
(10, 20)
Точка:
(15, 15)
Соединяем с (0, 0).
Прохождение через вершину считаем за два пересечения.
Результат: (15, 15) опознается как точка вне квадрата, хотя она и внутри.
Думай дальше.
Dmitry Krivitsky
>
>"Dmitry Krivitsky" <kr...@ira.kharkov.ua> wrote in message...
>> >Если эта линия пересечет границу фигуры четное количество раз - точка вне
>> >фигуры и наоборот.
>>
>> 1. Точное определение "пересечения границы" вместе с алгоритмом его
>> нахождения - в студию.
>
>ту же - (0,0). Просматриваются пересечения прямой, проходящей через заданую
>точку и (0,0), со всеми прямыми, задаными парами вершин фигуры. Если они
>пересекаются внутри отрезка между вершинами - пересечение границы есть. Если
>вне - пересечения границы нет.
>
>> 2. Пересечение может быть и в одной из вершин.
>>
>> (Намек: как отличать "пересечение" от "касания"?)
>
>игнорировать ее в этом случае (или считать за два пересечения).
Пример.
Квадрат с вершинами:
(10, 10)
(20, 10)
(20, 20)
(10, 20)
Точка:
(15, 15)
Соединяем с (0, 0) как ты предлагаешь.
Пересечение в вершине игнорируем, как ты предлагаешь.
Dmitry Krivitsky
>
>Anton Solovyev wrote:
>
>> Тебе нужна точка вне области, а не граница экрана. Наверное, можно просто
>> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
>> с каждой прямой, образуюшей область.
>
>Через эту и заданную точку проводим линию. И вася-кот.
В смысле?
Ничего не понял.
Dmitry Krivitsky
>>
>> Alexander Murzin wrote:
>>
>> >
>> > Проводим линию от точки в любом направлении до границы экрана.
>> > Если эта линия пересечет границу фигуры четное количество раз - точка
>вне
>> > фигуры и наоборот.
>> >
>>
>> взять вершину и отойти в сторону наружу (базируясь на направлении обхода
>> области), и уж тогда проводить линию. И придется считать пересечения это
>линии
>> с каждой прямой, образуюшей область.
>>
>>
Направление обхода ничего не говорит о том, где "внутри", а где "снаружи".
Dmitry Krivitsky
>
>Dmitry Krivitsky wrote:
>
>>
>> 1. Точное определение "пересечения границы" вместе с алгоритмом его
>> нахождения - в студию.
>>
>> (Намек: как отличать "пересечение" от "касания"?)
>
>точка находится во "внутреннем" секторе, образованном двумя лучами, исходящими
>из вершины.
А точка может быть внутри, но находится в "наружном" секторе некоторых
углов.
В ASCII нарисовать не могу. :-(
Могу GIF нарисовать и почтой послать.
Dmitry Krivitsky
>> 2.Прохождение через вершину считается двойным пересечением.
Во-во.
Dmitry Krivitsky
>Еще раз, подробно..чтобы не было вопросов.
>1.выбираем точку явно за пределами фигуры ( по максимальным координатам
>можно)
>2.проводим воображему линию от исходной точки до выбранной точки
>3.Считаем пересечения. причем пересечение вершины фигуры считаем за двойное.
>Осень: если насчитали четное количество - точка вне фигуры, нечетное -
>внутри.
>Дополнение - при попадании на одну из линий, образующих фигуру, процесс
>повторить с пункта 1 с выбором другой воображаемой точки и сбросом счетчика
>перечислений.
>
>Вариантов нет. Рещение правильное и обжалованию не подлежит..
Подлежит.
Уже написал в предыдущих письмах.
>Только не рассказывайте мне
Ну, можно и рассказать... :-)
>про случаи когда точка лежит на границе фигуры
>или линий столько много, что нельзя выбрать несовпадающую.
>Так же не принимаются возражения по поводу погрешности вычисления точных
>координат точек линий при сравнение на совпадение.:)))
Dmitry Krivitsky
>Dmitry Krivitsky wrote:
>> ...
>> 1. Точное определение "пересечения границы" вместе с алгоритмом его
>> нахождения - в студию.
>
>
>Горизонтальные отрезки границы вообще в расчет не принимаются.
>
>Пересечение границы - это наличие у нашей горизонтали H общей точки хотя
>бы с одним отрезком границы (алгоритм нахождения пересечения не
>привожу).
>
>Особый случай: если общая точка горизонтали H совпадает с концом одного
>из отрезков. Тогда существует еще ровно один отрезок, который тоже
>персекается с горизонталью H в своем конце. Если эти вторые точки этих
>двух отрезков лежат по одну сторону от H, то считаем, что пересечения
>нет. Если по разные стороны - считаем одно пересечение.
О! Вот это уже на что-то похоже.
Осталось добавить, что проверку того, по одну сторону или по разные лежат
точки от горизонтали, можно проводить сравнением их Y-координаты
с координатой горизонтали.
А для охвата отрезка, совпадающего с горизонталью, сравинваем Y-координаты
вторых концов СОСЕДНИХ отрезков.
>В остальных случаях каждое пересечение H с отрезком границы - это одно
>пересечение.
>
>> 2. Пересечение может быть и в одной из вершин.
>>
>> (Намек: как отличать "пересечение" от "касания"?)
>
>Охвачено.
>
>Best regards,
>Андрей.
Dmitry Krivitsky
>Dmitry Krivitsky <kr...@ira.kharkov.ua> wrote:
>
>> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
>> считать, что без самопересечений). Задана в виде набора координат вершин.
>> Дана также произвольная точка на экране компьютера (координаты).
>> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
>
>проходится по кругу. Для каждой пары точек определяется с какой стороны от
>прямой проходящей через эту пару находится данная точка. Если для всех
>отрезков проверяемая точка находится с одной стороны (не важно с какой) то
>она внутри.
А если не для всех, то она тоже запросто может быть внутри.
Фигура ведь не обязательно выпуклая.
Dmitry Krivitsky
>
>"gek" <he...@cavasoft.com> wrote in message
>news:9q534l$up0$1...@gw.liquidhome.com...
>> > 2.Прохождение через вершину считается двойным пересечением.
>> а если я пересек вершину идя из фигуры?
>
>Брать другое направление.
Гы! Тебе ж еще нужно определить как-то, что ты пересек вершину,
а не коснулся ее.
Dmitry Krivitsky
Не работает.
Но есть на самом деле и работающий метод, связанный с углами.
Говорить?
Dmitry Krivitsky
Не просто пересечений, а с детектированием "переход vs касание" при прохождении
через вершину.
Andrey Tarasevich
> ...
> >> Особый случай: если общая точка горизонтали H совпадает с концом одного
> >> из отрезков. Тогда существует еще ровно один отрезок, который тоже
> >> персекается с горизонталью H в своем конце. Если эти вторые точки этих
> >> двух отрезков лежат по одну сторону от H, то считаем, что пересечения
> >> нет. Если по разные стороны - считаем одно пересечение.
> AT> Уточнение: ... Тогда существует еще ровно один _соседний_ отрезок
> AT> (считаем, что горизонтальных ребер в границе нет), который тоже
> AT> пересекается с горизонталью H в своем конце ...
>
> Или два.
Ровно один. Два быть не может.
> А ещё точка может лежать на одном из отрезков.
Вопрос лишь в том, считать ли ее внутри или снаружи. Потребуется
соответсвующаяе косметическая модификация алгоритма.
> Короче, после десятой итерации это решение заработает.
Нет. Это уже полностью завершенное решение.
Best regards,
Андрей.
Dmitry Krivitsky
Во!
Ноль, если снаружи, и плюс-минус 360 градусов, если внутри.
Yuriy Shalak
А это - не важно. Что коснулся, что пересек - нужно "переигрывать".
Andrey Tarasevich
>
> О! Вот это уже на что-то похоже.
> Осталось добавить, что проверку того, по одну сторону или по разные лежат
> точки от горизонтали, можно проводить сравнением их Y-координаты
> с координатой горизонтали.
Вряд ли кто-то станет это делать по-другому.
> А для охвата отрезка, совпадающего с горизонталью, сравинваем Y-координаты
> вторых концов СОСЕДНИХ отрезков.
Горизонтальные ребра границы можно выкинуть из списка ребер еще до
старта алгоритма. Они на решение никак не влияют.
Best regards,
Андрей.
Andrey Tarasevich
> ...
> Но есть на самом деле и работающий метод, связанный с углами.
> Говорить?
Описан в "Агоритмические основы машинной графики" Роджерса. Никита этот
метод уже упомянул.
Best regards,
Андрей.
Andrey Tarasevich
> ...
> >Для единичной задачи хорошо подходит именно тест на кол-во пересечений с
> >горизонталью.
>
> Не просто пересечений, а с детектированием "переход vs касание" при прохождении
> через вершину.
Это и имеется в виду (см. выше)
Best regards,
Андрей.
Dmitry Krivitsky
>Dmitry Krivitsky wrote:
>
>> Не работает.
>>
>> Но есть на самом деле и работающий метод, связанный с углами.
>> Говорить?
>
>
>Типа, обойти по кругу, считая углы поворота, чтобы решить с какой стороны
>внутренность (по или против часовой стрелки обходим)?
Уже его упомянули тут.
Если обозначить наху точку O, а вершины ломаной X1, X2, X3, ..., то считаешь
сумму углов X1 O X2, X2 O X3, X3 O X4 и т.д. с учетом знаков. Знак определяется
направлением: по или против часовой стрелки.
Сумма будет или ноль, если вне, или плюс-минус число оборотов вокруг точки,
умноженное на 360 градусов.
(Число оборотов для линии без самопересечений будет не больше 1.)
Andrey Tarasevich
> ...
> > Но есть на самом деле и работающий метод, связанный с углами.
> > Говорить?
>
>
> Типа, обойти по кругу, считая углы поворота, чтобы решить с какой стороны
> внутренность (по или против часовой стрелки обходим)?
(p[0], p[1], ..., p[n - 1]) - ломаная
t - наша тестовая точка.
Для каждой пары (p[i], p[i + 1]) меряем угол (p[i], t, p[i + 1]). Если
луч (t, p[i + i]) "повернут" по часовой стрелке относительно луча (t,
p[i]), то величину полученного угола прибавляем к общей сумме. В
противном случае - вычитаем из общей суммы.
Начальное значение общей суммы - 0. Не забыть обработать пару (p[n - 1],
p[0]).
Если после всего этого общая сумма равна 0, то точка снаружи. Иначе -
внутри (сумма будет кратна 360, если углы мерялись в градусах).
Best regards,
Андрей.
Nikita V. Belenki
>> >> Особый случай: если общая точка горизонтали H совпадает с концом
>> >> одного
>> >> из отрезков. Тогда существует еще ровно один отрезок, который тоже
>> >> персекается с горизонталью H в своем конце. Если эти вторые точки этих
>> >> двух отрезков лежат по одну сторону от H, то считаем, что пересечения
>> >> нет. Если по разные стороны - считаем одно пересечение.
>> AT> Уточнение: ... Тогда существует еще ровно один _соседний_ отрезок
>> AT> (считаем, что горизонтальных ребер в границе нет), который тоже
>> AT> пересекается с горизонталью H в своем конце ...
>> Или два.
AT> Ровно один. Два быть не может.
Один из отрезков лежит на прямой. Соответственно, оба его соседа имеют с этой
прямой общую точку.
>> А ещё точка может лежать на одном из отрезков.
AT> Вопрос лишь в том, считать ли ее внутри или снаружи. Потребуется
AT> соответсвующаяе косметическая модификация алгоритма.
Главное, чтобы это не приводило к делению на ноль.
Kit.
Andrey Tarasevich
>
> Dmitry Krivitsky wrote:
>
> > >Типа, обойти по кругу, считая углы поворота, чтобы решить с какой стороны
> > >внутренность (по или против часовой стрелки обходим)?
> >
> > Уже его упомянули тут.
>
>
Заметающая прямая - это несколько иное. Ближе даже к горизонтали и
подсчету пересечений.
Best regards,
Андрей.
Denis Nikitin
"Tatiana A. Zhdanova" <anton...@home.com> wrote in message
news:9q50fn$476$1...@ddt.demos.su...
> > Расскажи, как решала, Татьяна.
>
> Координаты осей (площадь занятая растением, грядка) Функция роста =
> 2*(площадь растения) (поскольку при данных условиях можно пренебречь более
> сложной зависимостью) Дальше задача сводится к тривиальной, с ответом "на
> четвёртый день" т.е. "пятница".
А что интересно, куда все "особо умные русские" пропали немедленно с
язвительными комментариями в адрес американской образовательной системы,
после того, как женщина правильный ответ привела, до которого ни один из
особо хорошо обученных не додумался. Характерно.
Денис
Andy Kovtun
Dmitry Krivitsky wrote:
> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> считать, что без самопересечений). Задана в виде набора координат вершин.
> Дана также произвольная точка на экране компьютера (координаты).
> Найти: находится точка внутри области, ограниченной ломаной, или снаружи.
Эхххх, склероз... Ведь читали же эту шнягу по машинной графике...
Стопудово там надо было проводить прямые из данной точки через все
вершины многоугольника... Хм... Что ж потом с ими делать надо было-то?
Помнится, алгоритм был простой до неприличия, но доказательство его
корректности - довольно развесистое.
-andy
Konstantin Novik
"Denis Nikitin" <di...@dataageinc.com> wrote...
> "Tatiana A. Zhdanova" <anton...@home.com> wrote in message
> > > Расскажи, как решала, Татьяна.
> >
> > Координаты осей (площадь занятая растением, грядка) Функция роста =
> > 2*(площадь растения) (поскольку при данных условиях можно пренебречь
более
> > сложной зависимостью) Дальше задача сводится к тривиальной, с ответом
"на
> > четвёртый день" т.е. "пятница".
>
> А что интересно, куда все "особо умные русские" пропали немедленно с
> язвительными комментариями в адрес американской образовательной системы,
> после того, как женщина правильный ответ привела, до которого ни один из
> особо хорошо обученных не додумался. Характерно.
Номер два. Урожайно :-).
K.N.
Dmitry Zotkin
hi,
Andy Kovtun (ako...@mediaone.net) wrote:
> Стопудово там надо было проводить прямые из данной точки через все
> вершины многоугольника... Хм... Что ж потом с ими делать надо было-то?
сумму углов последовательных поворотов посчитать. Если 2pi, то внутри,
если ноль, то снаружи.
Reference: J. Borish, "Extension of the image model to arbitrary
polyhedra", J. Acoust. Soc. Am., vol 75(6), 1984, p. 1827.
;)
/dz, Berwyn Heights, MD
Aleksey Dmitriyev
news:1b8a257.01101...@posting.google.com...
> Hi!
>
> Вот, нашел на anekdot.ru. Смех смехом, но неужали все так грустно ?
Просьба
> господам, у которых тут дети ходят в школу: оцените pls достоверность.
Очередная легенда про тупых американцев которая тешит самолюбие русских и
других национальностей, так и подрывает сказать "если ты такой умный то
почему такой бедный".
Мой ребенок еще не дорос до школы. Но я могу сказать что знаком с
америкнским ребенком (Томас Елиот) который в прошлом году участвовал в
передаче-конкурсе умненьких детишек. Мало того что он умный, так еще и очень
всесторонне развитый, ну там типа прыгать бегать и на лыжах тоже, а не
только за книжками сидеть. Я так понял что его способности были развиты
родителями и также он ходит в специально выбранную школу. А школы везде есть
плохие и хорошие, как в Штатах, так и в России.
--Aleksey
Ilya Languev
news:3BC67ED2...@mediaone.net...
> > Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> > считать, что без самопересечений). Задана в виде набора координат
вершин.
> > Дана также произвольная точка на экране компьютера (координаты).
> > Найти: находится точка внутри области, ограниченной ломаной, или
снаружи.
>
> Эхххх, склероз... Ведь читали же эту шнягу по машинной графике...
Для выпуклого многоугольника. Если точка лежит внутри, то для прямой,
проходящей через любые две соседние вершины, все остальные вершины и точка
in question должны лежать по одну сторону.
Так понятно или программу писать?
Невыпуклый многоугольник бьется на выпуклые.
Илья
Tatiana A. Zhdanova
> >> (а на самом деле, по математике).
> >> Дано: замкнутая ломаная линия на экране компьютера (будем для простоты
> >> считать, что без самопересечений). Задана в виде набора координат
вершин.
> >> Дана также произвольная точка на экране компьютера (координаты).
> >> Найти: находится точка внутри области, ограниченной ломаной, или
снаружи.
> >>
> >
> >Проводим линию от точки в любом направлении до границы экрана.
> >Если эта линия пересечет границу фигуры четное количество раз - точка вне
> >фигуры и наоборот.
>
> 1. Точное определение "пересечения границы" вместе с алгоритмом его
> нахождения - в студию.
Рассматриваем Декартову систему координат.
Соединяешь две точки y1x1 и y2x2 ломаной фигуры в прямую y=kx + a. Проводишь
луч от точки до границы экрана y = a (a - координата "y" у твоей точки),
смотришь пересекаются ли они, и если да, то лежит ли точка пересечения
внутри отезка заданного точками y1x1 и y2x2. Если лежит, то тебя эта точка
интересует, если нет - отбрасываешь.
> 2. Пересечение может быть и в одной из вершин.
У тебя в условии задачи заданы вершины, да?
Татьяна.
Aleksey Dmitriyev
"Aleksey Dmitriyev" <alek...@nevawind.com> wrote in message
news:9q6300$925$1...@ddt.demos.su...
> "Mike" <mik...@skeptik.net> wrote in message
> news:1b8a257.01101...@posting.google.com...
> > Hi!
> >
> > Вот, нашел на anekdot.ru. Смех смехом, но неужали все так грустно ?
> Просьба
> > господам, у которых тут дети ходят в школу: оцените pls достоверность.
>
> Очередная легенда про тупых американцев которая тешит самолюбие русских и
> других национальностей, так и подрывает сказать "если ты такой умный то
> почему такой бедный".
А вот как наши русские наши супер гении из лента-вру представляют себе
американцев (см. картинку)
http://lenta.ru/ww3/2001/10/11/iraq/
Как я понял картинка ихнего самопально-ленточного производства. Видимо долго
трудились, переводили, пердели и додумались нарисовать "супер остроумную"
вещь...
Andrey Tarasevich
> ...
> >> AT> (считаем, что горизонтальных ребер в границе нет), который тоже
> >> AT> пересекается с горизонталью H в своем конце ...
> >> Или два.
> AT> Ровно один. Два быть не может.
>
> Один из отрезков лежит на прямой. Соответственно, оба его соседа имеют с этой
> прямой общую точку.
Прямая, о которой идет речь, это горизонталь, проведенная через тестовую
точку. В ломаной же горизонтальных отрезков нет, как я уже сказал выше.
Все горизонтальные ребра можно выкинуть еще до начала алгоритма. Два
смежных с выкидываемым горизонтальным отрезком ребра при этом становятся
смежными друг другу. Именно к таким образом заданной ломаной и относятся
все мои утверждения. И ситуация "один из отрезков лежит на прямой"
невозможна.
Best regards,
Андрей.