На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Нахождение короткого пути, посторение линий
    ЛЮДИ!!!
    Вообчим есть две точки A(x1,y1) и B(x2,y2). Нужно провести линию из одной к другой и знать координату каждой точки на этой линии. Т.е. простое line (x1,y1)-(x2,y2) не подойдёт. Где-то слышал, что использовать векторы, но при их сложении всё-равно вылезает не то, что нужно.

    Или сделаем проще: как процессор рисует линию. Формула какая-то млин нужна.
      формула прямой
      y = a * x + b

      ограничиваем по координатам x1, x2 (или y1, y2) получаем формулу отрезка
        Линии чаще всего рисуют с помощью алгоритма Брезенхема (есть и другие, но этот - один из самых быстрых). Подробности: http://www.enlight.ru/demo/faq/smth.phtml?query=alg_line_misc
          А хочешь простейший алгоритм, ведь если ты немыл руки плохим мылом
          как ты сможешь оценить все прелести хорошего :) в частности алг. Брезенхема.
          В общем идея такая:
          1. Вычисляем уравнение прямой т.е. находим a и b в формуле y=a*x+b.
          2. Потом рисуем y ( y=a*x+b :) ) для каждого  x1<=x<=x2
          3. Потом рисуем x (x=(y-b)/a  )для каждого  y1<=y<=y2

          Шаг три нужен т.к. нет гарантии что после шага 2 линия будет сплошной.
            Цитата (Mixxx @ 05.07.03, 09:11:46)
            ...  x1<=x<=x2
            y1<=y<=y2  ...

            из условия не очевидно, что x1 <= x2, может оказаться и наоборот, а y зависит от функции, тем более условие не верное.
            Сообщение отредактировано: MeG -
              Цитата
              из условия не очевидно, что x1 <= x2, может оказаться и наоборот, а y зависит от функции, тем более условие не верное

              Ну вообщем да. Я забыл сказать что если х1>x2 To Их надо обменять значениями.
              Аналогично нужно поступить для y1 и y2.
              Мы же сейчас говорим не про абстрактный график а про прямую у которой есть особеность - каждому значению Y соответствует единственное значение X.
                можно задать отрезок [AB]  параметрическим уравнением

                x = t * a + b
                y = t * c + d

                где  a, b, c, d некоторые константы, t — параметр. При изменении t от минус бесконечности, до плюс бесконечности получим все точки (x, y)  прямой.
                Поскольку нам нужен отрезок, ограничим параметр t, таким образом, чтобы при t = 0 получились координаты точки A(x1, y1), а при t = 1 — координаты точки B(x2, y2)

                Найдем константы b, d системы уравнений. Подставляем координаты точки A(x1, y1) и значение параметра для этой точки t = 0
                x1 = 0 * a + b
                y1 = 0 * c + d

                получаем b = x1; d = y1

                дальше находим a, c через точку B(x2, y2) и t = 1
                x2 = 1 * a + x1
                y2 = 1 * c + y1


                получаем a = x2 – x1;  c = y2 – y1

                Таким образом получаем уравнение отрезка [AB] выраженное через координаты точек  A(x1, y1) и B(x2, y2):
                x = t * (x2 - x1) + x1
                y = t * (y2 - y1) + y1
                , при 0 <= t <= 1
                Изменяя t от нуля до единицы получим все точки отрезка

                ЗЫ: урок по геометрии ;D
                Сообщение отредактировано: MeG -
                  Пример использования параметрического уравнения прямой. Принадлежит ли точка заданному отрезку

                  Есть отрезок с координатами концов A(5, 1) и B(-1, -2).
                  Параметрическое уравнение для отрезка [AB]:
                  x = -6 * t + 5
                  y = -3 * t + 1


                  Найдем положение точки C(2, 3) относительно отрезка [AB].
                  Подставляем координаты отрезка в уравнение
                  2 = -6 * t + 5
                  3 = -3 * t + 1

                  упрощаем
                  -3 = -6 * t
                  2 = -3 * t

                  выражаем параметр
                  1/2 = t
                  -2/3 = t

                  получилось два разных значения параметра t, точка C не лежит на прямой

                  Точка D(7, 2)
                  Подставляем координаты отрезка в уравнение,
                  7 = -6 * t + 5
                  2 = -3 * t + 1

                  выражаем параметр
                  -2/6 = t
                  -1/3 = t

                  получили одно значение параметра t = -1/3, точка D лежит на прямой.
                  значение параметра t = -1/3 выходит за границы 0 <= t <= 1. Точка D находится вне отрезка [AB].

                  Точка E(1, -1)
                  1 = -6 * t + 5
                  -1 = -3 * t + 1

                  одно значение параметра t = 2/3, точка E лежит на отрезке [AB].
                  Точка E лежит на отрезке на расстоянии две третьих длинны |AB| от точки A. То есть |AE| = 2 * |EB|

                  Этот пример можно наглядно изобразить на бумажке  smile.gif
                  Сообщение отредактировано: MeG -
                    Помогите, пожалуйста с задачей.

                    Даны вершины A(7; − 4) , B(3; − 7) , C(−2; 5) треугольника. Требуется
                    найти:
                    1) длину стороны BC ;
                    2) площадь треугольника ABC ;
                    3) уравнение стороны BC ;
                    4) уравнение высоты, проведенной из вершины A;
                    5) длину высоты, проведенной из вершины A;
                    6) угол B в радианах с точностью до 0,01.
                    Сделать чертеж. :huh:

                    у МЕНЯ ПОЛУЧИЛОСЬ

                    1) ВС=13
                    2) площадь АВС = 31.5
                    3) что такое уравнение стороны? может напишите?
                    4-6) тоже не знаю.
                      Цитата olga0883@mail.ru @
                      что такое уравнение стороны?

                      Может имеется ввиду уравнение прямой, на которой лежит сторона. Уравнение прямой можно записать так: x2 = a * x1 + b , поочередно подставляем в это уравнение координаты точек, через которые должна проходить прямая, находим a и b. Отрезок [B(b1, b2), C(c1, c2)] можно задать параметрически, например так: x1 = t, тогда x2 = a * t + b и t меняется от b1 до c1

                      Добавлено
                      Цитата olga0883@mail.ru @
                      4) уравнение высоты, проведенной из вершины A;

                      т.е. перпендикуляр к стороне BC, пусть уравнение ее x2 = a * x1 + b или x2 - a * x1 = b , тогда (-a, 1) - вектор нормали к этой прямой или направляющий вектор прямой, перпендикулярной BC. Нужно написать уравнение прямой проходящей через A с направляющим вектором (-a, 1)
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0,0333 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:54 GMT ]