| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
 Добавлено: Сб Июн 02 2007 12:14 Заголовок сообщения: Треугольник и точка. |
 |
|
В курсовой требуется написать такую программу:
Построить треугольник по заданным координатам. Внутри треугольника движется точка, отражаясь от его сторон.
С треугольником проблем не возникает, а вот как сделать чтоб точка правильно отбивалась от сторон не знаю. В принципе мне и алгоритма вполне хватит, но если кто захочет написать его реализацию скажу, что задачу нужно выполнить на С.
Заранее спасибо всем, кто откликнется. |
|
| Вернуться к началу |
|
 |
Kefir
Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь
|
| Добавлено: Вс Июн 03 2007 10:45 Заголовок сообщения: |
|
|
Ну типа эта... Угол падения равен углу отражения. Ну что? Теперь знаешь как сделать чтоб точка правильно отбивалась?
_________________
Самоловских Виталий aka Kefir |
|
| Вернуться к началу |
|
|
Phenics
Зарегистрирован: 03.06.2007
Сообщения: 2
|
| Добавлено: Вс Июн 03 2007 14:17 Заголовок сообщения: Треугольник и точка |
|
|
Что значит, чтобы правильно отражалась? Под правильным углом или в момент, когда точка совпадёт с треугольником?  |
|
| Вернуться к началу |
|
|
Dimasm
Зарегистрирован: 25.04.2005
Сообщения: 454
|
| Добавлено: Вс Июн 03 2007 18:02 Заголовок сообщения: |
|
|
берём школьный учебник геометрии, рисуем на листочке схемку и решаем школьную задачу
_________________
С уважением Dimasm |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Вт Июн 05 2007 20:24 Заголовок сообщения: |
|
|
| Dimasm писал(а): | | берём школьный учебник геометрии, рисуем на листочке схемку и решаем школьную задачу |
Не всё так просто, как кажется на первый взгляд.
Я не стремлюсь, чтобы она отбивалась под правильным углом, пока мне это не надо.
Дело в том, что если использовать стандартное уравнение принадлежности точки прямой: (x-x1)/(x2-x1)=(y-y1)/(y2-y1), то есть случаи, когда возникает деление на 0. Если преобразовать уравнение к виду (x-x1)*(y2-y1)=(x2-x1)*(y-y1), то получаем, но дело в том, что в данном случае возникают частные случаи, причём решение одной проблемы приводит к исключению возможности решения другой.
Вобщем выговорился. А вообще, я нашёл решение данной задачи при помощи векторов. Попробую применить, и если получится расскажу что к чему, если интересно... |
|
| Вернуться к началу |
|
|
Kefir
Зарегистрирован: 16.04.2005
Сообщения: 443
Откуда: Пермь
|
| Добавлено: Ср Июн 06 2007 06:02 Заголовок сообщения: |
|
|
Чувак, неужто ты думаешь что мы подобных задач не решали? Просто то как ты ставишь задачу раздражает. После постановки задачи хочется увидеть каким способом ты ее решаешь и что у тебя не получается. А то создается ощущение, что ты нихрена не делаешь, а хочешь чтоб твою задачу решили за тебя.
Короче, уравнения принадлежности точки прямой нафиг не нужны.
У тебя есть положение точки: x,y
Скорость: vx, vy
Перемещение за 1 шаг: dx = vx*t, dy=vy*t
Новое положение: x1=x+dx, y1=y+dy
1. Проверяешь лежит ли точка (x1,y1) в треугольнике. Если лежит то все зашибись, если нет, то хуже.
2. Выясняем с каким отрезком пересекается отрезок (x,y,x1,y1). Получаем точку пересечения (xc,yc). Блин, как же все просто в случае если стороны параллельны осям координат.
3. дальше нужно преобразовать x1, y1:
x1 = 2*xc-x1
y1 = 2*yc-y1
Как-то так короче... Надо проверять
_________________
Самоловских Виталий aka Kefir |
|
| Вернуться к началу |
|
|
grf
Зарегистрирован: 05.04.2005
Сообщения: 1242
Откуда: Москва
|
| Добавлено: Ср Июн 06 2007 08:37 Заголовок сообщения: |
|
|
в продолжение Kefir
по пункту 3.
После того как нашел Xc Yc применяешь закон отражения, тот который тебе нужен, если угол падения равен углу отражения, то делаешь угол отражения равный углу между векторами (XY; XcYc) и вектором прямой, если, например, угол отражения всегда равен 30 градусам, то делаешь угол в 30 градусов.
В соответствии с твоими законами физики изменяешь скорость движения, либо она не меняется, если упругое соударение, либо замедляется, если не упругое, либо, например увеличивается, либо от какой то стенки увеличивается от какойто уменьшается.
находишь время, которое точка летит до конца шага после отражения dT1
Находишь положение точки в конце шага после отражения с учетом изменившегося вектора движения и скоростей.
И далее в цикле.
_________________
Errare humanum est |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Сб Июн 09 2007 19:09 Заголовок сообщения: |
|
|
Kefir, grf, спасибо большое, что пытаетесь помочь, но как задать отражение точки, скорость и т.п. я знаю. Попробую сформулировать вопрос более конкретно:
Проблемы возникают в самом первом пункте. Инициализировать точку так, чтобы она была внутри треугольника не проблема. Далее надо отслеживать не вышла ли она за его границы. Вот нашёл для этого алгоритм:
http://algolist.manual.ru/olimp/geo_prb.php
Задача 8
Но с его реализацией как раз и возникают проблемы. Когда я выражаю параметр p из уравнения, для определения точки пересечения прямой и отрезка, выходит опять деление. От него нигде блин не избавишься. Более того, программа вообще как-то криво работает по этому алгоритму, даже без деления на 0 и точка с места не движется.
Даже не знаю что делать.
Курсак то я по этой фигне уже почти сдал, просто препода развёл, но мне уже самому интересно как это решается. |
|
| Вернуться к началу |
|
|
Dimasm
Зарегистрирован: 25.04.2005
Сообщения: 454
|
| Добавлено: Сб Июн 09 2007 19:43 Заголовок сообщения: |
|
|
| C@S писал(а): | | Далее надо отслеживать не вышла ли она за его границы. |
Ты наверно с девчёнками записками перекидывался в школе на геометрии, а в ВУЗе вышку прогуливал, и коспекты переписывал у одногрупников! 
у тебя есть 3 прямые - стороны треугольника
возьми прямую от твоей точки, до центра треугольника и ищи точку пересечения с каждой из сторон по очереди.
ну надеюсь, как найти уравнение прямой, зная две точки, и приветсти его к виду y=ax+b ты умеешь (тебе надо будет поднять конспекты по вышке)
далее, система линейных уравнений
y=a1*x+b2 - прямая от твоей точки (A), до центра треугольника
y=a2*x+b2 - одна из сторон
если выразить x, x = (b1-b2)/(a1-a2) (мог ошибиться, проверьте )
когда будет деление на ноль? при а1 = а2
а в уравнении прямой y=a*x+b, а - характреризует угол наклона
тоесть деление на ноль будет когда прямые параллельны, это возможно в твоём случае?
нашли x и y - это точка (B) перечения прямой от твоей точки, до центра треугольника и одной из сторон треугольника
теперь проверяешь, если точка А ближе чем Б к центру, то точка внутри, если дальше - то вне треугольника
и так для каждой из трёх сторон
| C@S писал(а): | | Dimasm писал(а): | | берём школьный учебник геометрии, рисуем на листочке схемку и решаем школьную задачу |
Не всё так просто, как кажется на первый взгляд. |
признаю, был не прав, школьной программой такое решить было бы сложно, ещё надо бы курс вышки прослушать
_________________
С уважением Dimasm |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Вс Июн 10 2007 12:50 Заголовок сообщения: |
|
|
| Dimasm писал(а): |
Ты наверно с девчёнками записками перекидывался в школе на геометрии, а в ВУЗе вышку прогуливал, и коспекты переписывал у одногрупников!
|
Спасибо Вам, конечно, за то, что пытаетесь помочь, но если бы Вы так не увлеклись домыслами о моей образованности, а уделили бы внимание постановке вопроса, то, возможно, заметили бы, что в подобных задачах деления вообще надо избегать. Если уж Вам было трудно перейти по той ссылке, которую я предоставил, то я цитату приведу прямо здесь (определяем пересекается ли прямая ax+b=y и отрезок с концами (x1,y1), (x2,y2)):
| Цитата: | Вариант 1. Можно через концы отрезка провести прямую cx+d=y и определить, принадлежит ли точка пересечения двух прямых x, если она существует, отрезку. То есть, мы должны решить уравнение x*(c-a)=(b-d), найти y=ax+b, и проверить выполнение неравенств x1<=x<=x2, y1<=y<=y2.
Но при нахождении x при делении могут возникнуть большие вычислительные погрешности или даже переполнение или потеря значимости, в результате чего получится неверный ответ. |
Судя по последнему абзацу можно однозначно сказать, что и тот способ, который описали Вы, не подходит для решения данной задачи. Вы думаете я до этого не додумывался???
Далее приведу альтернативный вариант решения:
| Цитата: | | Вариант 2. Обозначим F(x,y)=ax+b-y. Прямая ax+b=y разбивает плоскость на три части: в одной F(x,y)>0, в другой F(x,y)<0 и на прямой ax+b=y F(x,y)=0 . Если эта прямая пересекает отрезок, то либо концы отрезка лежат в различных полуплоскостях, либо хотя бы одна концевая точка отрезка лежит на прямой. Это равносильно выполнению следующего неравенства F(x1,y1)*F(x2,y2)<=0. Таким образом, не вычисляя точку пересечения, мы по знаку функционала судим о том, имеют ли прямая и отрезок общую точку. Очевидно, что второй вариант решения подзадачи предпочтительнее первого. |
Алгоритм великолепный, и мне подходит идеально, но для него нужно знать две точки для прямой и две точки для отрезка. Отрезок у нас есть, а вот как найти точку пересечения прямой, проходящей через нашу точку, с отрезком... Здесь глюки и возникают, опять таки без деления не обойтись.
Кстати, стороны треугольника у меня могут быть какими угодно, в том числе и параллельными осям координат, их координаты вводятся пользователем.
Прикладываю к посту изображение (рисовал прямо в универе, потому и в паинте). Здесь надо найти точки x1, x2, x1', x2' для того, чтобы определить находится ли наша точка между ними, или за/перед ними.
 |
|
| Вернуться к началу |
|
|
Dimasm
Зарегистрирован: 25.04.2005
Сообщения: 454
|
| Добавлено: Вс Июн 10 2007 14:48 Заголовок сообщения: |
|
|
| C@S писал(а): | Спасибо Вам, конечно, за то, что пытаетесь помочь, но если бы Вы так не увлеклись домыслами о моей образованности, а уделили бы внимание постановке вопроса, то, возможно, заметили бы, что в подобных задачах деления вообще надо избегать. Если уж Вам было трудно перейти по той ссылке, которую я предоставил, то я цитату приведу прямо здесь (определяем пересекается ли прямая ax+b=y и отрезок с концами (x1,y1), (x2,y2)):
| Цитата: | | Вариант 1. Можно через концы отрезка провести прямую cx+d=y и определить, принадлежит ли точка пересечения двух прямых x, если она существует, отрезку. То есть, мы должны решить уравнение x*(c-a)=(b-d), найти y=ax+b, и проверить выполнение неравенств x1<=x<=x2, y1<=y<=y2. |
|
в ссылке вы говорили о 8-й задаче, а цитата из 6-й
Без деления "вообще" не бывает. Ноль в знаменателе может появиться в конкретных случаях, всего пару раз. Эти случаи можно выловить!
http://dimasm.hotmail.ru/doc1.htm - я описал более подробно что имел в виду. я не навязываю вам этот вариант, но поясните, чем он не подходит? (деление на ноль - не аргумент, оно может быть всего в паре случаев, которые можно описать)
_________________
С уважением Dimasm |
|
| Вернуться к началу |
|
|
grf
Зарегистрирован: 05.04.2005
Сообщения: 1242
Откуда: Москва
|
| Добавлено: Ср Июн 13 2007 09:40 Заголовок сообщения: |
|
|
Боже мой! Куда мы катимся!
Уважаемый C@S, неужели Вы думаете, что Вы первый, кто столкнулся с подобной задачкой.
| Цитата: | | Чувак, неужто ты думаешь что мы подобных задач не решали? |
Далее
| Цитата: | | берём школьный учебник геометрии, рисуем на листочке схемку и решаем школьную задачу |
| Цитата: | | признаю, был не прав, школьной программой такое решить было бы сложно, ещё надо бы курс вышки прослушать |
Зря ты так, Dimasm, зря. Огорчил ты меня до невозможности.
Математика - 6-7 класс, программирование - 9 класс, больше ничего не нужно.
Теперь по существу задачи
если
| Цитата: | | Вариант 1. Можно через концы отрезка провести прямую cx+d=y и определить, принадлежит ли точка пересечения двух прямых x, если она существует, отрезку. То есть, мы должны решить уравнение x*(c-a)=(b-d), найти y=ax+b, и проверить выполнение неравенств x1<=x<=x2, y1<=y<=y2. |
Открою тебе страшную математическую тайну, если с=а, то прямые y=ax+b и y=cx+d параллельны, и соответственно не пересекаются. Отсюда и возникает деление на 0. Отслеживается это, обычно, конструкцией
if then else
или как она выглядит у тебя на твоем языке программирования, в алгоритмах - это ромбик с условием внутри, и + и - по боковым вершинам.
В твоем случае If (c-a)>e then ....
где e - погрешность вычеслений (машинный ноль)
Ветвь else тебе таже не нужна, ибо тут ничего не происходит, точка движется вдоль ребра.
Да, наше образование падает все ниже и ниже. Скоро курс арифметики будут 11 лет в школе читать. А уж начала анализа - институтский курс вышки. Матричное и тензорное исчисление - кандидат как минимум. Урмат - академик, не меньше.
Я в шоке 
_________________
Errare humanum est |
|
| Вернуться к началу |
|
|
grf
Зарегистрирован: 05.04.2005
Сообщения: 1242
Откуда: Москва
|
| Добавлено: Ср Июн 13 2007 15:34 Заголовок сообщения: |
|
|
| Цитата: | Задача 8
Но с его реализацией как раз и возникают проблемы. |
Паришься ты не в тему.
1. Есть три точки, вершины треугольника.
2. Проводишь три прямые, которые в пересечении образуют твой треугольник.
3. Берешь одну прямую (она, естественно, проходит через две вершины) и смотришь условие что бы третья вершина и твоя точка лежали по одну сторону от этой прямой.
4. Проверяешь это условие трижды, относительно трех прямых.
5. Если во всех трех раз получил истину точка лежит в треугольнике.
6. Варианты, когда точка лежит на ребре или совпадает с вершиной, рассматриваешь отдельно, по условиям задачи, положение грани считается в треугольнике или вне.
Я в шоке.
_________________
Errare humanum est
Последний раз редактировалось: grf (Ср Июн 13 2007 16:22), всего редактировалось 2 раз(а) |
|
| Вернуться к началу |
|
|
grf
Зарегистрирован: 05.04.2005
Сообщения: 1242
Откуда: Москва
|
| Добавлено: Ср Июн 13 2007 15:45 Заголовок сообщения: |
|
|
| Цитата: | | Кстати, стороны треугольника у меня могут быть какими угодно, в том числе и параллельными осям координат, их координаты вводятся пользователем. |
Ершкин кот. О том, что данные, вводимые пользователем надо проверять, Вы естественно не знаете.
Грамотная программа, на просьбу к пользователю "Введите координату х первой вершины" на вход получит символ "Д" должна не загнуться из-за несоответствия типов, а предупредить пользователя:
"Ошибка: координата х представляет собой число, а не символ. Допускается ввод числа в следующих форматах:
6
6.0
6.07Е-7
мантисса числа длиннее 9 порядков округляется.
Повторите ввод.
Введите координату х первой вершины _ "
или что-нибудь в таком роде.
Необходимо сделать проверку, что бы пользователь не ввел две (три) одинаковых точки, что бы все три точки не лежали на одной прямой и пр. пр. пр.
_________________
Errare humanum est |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Чт Июн 14 2007 12:27 Заголовок сообщения: |
|
|
| grf писал(а): | | Цитата: | | Кстати, стороны треугольника у меня могут быть какими угодно, в том числе и параллельными осям координат, их координаты вводятся пользователем. |
Ершкин кот. О том, что данные, вводимые пользователем надо проверять, Вы естественно не знаете.
Грамотная программа, на просьбу к пользователю "Введите координату х первой вершины" на вход получит символ "Д" должна не загнуться из-за несоответствия типов, а предупредить пользователя:
"Ошибка: координата х представляет собой число, а не символ. Допускается ввод числа в следующих форматах:
6
6.0
6.07Е-7
мантисса числа длиннее 9 порядков округляется.
Повторите ввод.
Введите координату х первой вершины _ "
или что-нибудь в таком роде.
Необходимо сделать проверку, что бы пользователь не ввел две (три) одинаковых точки, что бы все три точки не лежали на одной прямой и пр. пр. пр.
|
Да при чём тут ввод??? У меня с ним проблем вообще никаких нет. |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Чт Июн 14 2007 12:29 Заголовок сообщения: |
|
|
| Dimasm писал(а): |
в ссылке вы говорили о 8-й задаче, а цитата из 6-й
|
Вообще-то 6-ая задача упоминается непосредственно в тексте 8. |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Чт Июн 14 2007 12:33 Заголовок сообщения: |
|
|
Вызывайте врача.
На днях кину листинг того, что у меня получилось. Ато на словах у вас больно просто всё получается. |
|
| Вернуться к началу |
|
|
C@S
Зарегистрирован: 02.06.2007
Сообщения: 17
|
| Добавлено: Чт Июн 14 2007 12:38 Заголовок сообщения: |
|
|
| Kefir писал(а): | | Чувак, неужто ты думаешь что мы подобных задач не решали? |
Если бы я так думал, или сомневался бы в компетенции форумчан я бы и напрягаться не стал, оставляя тут сообщения. |
|
| Вернуться к началу |
|
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
