Геометрическая задача

[krossovochkin]

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

Point[] points = {(0, 0), (5, 1) ...}

где каждая точка определяет переход между двумя кусками линейных частей этой функции.
Например: у нас есть первая точка (0, 0) и вторая (5, 1). Значит на отрезке [0, 5] функция имеет вид y = x / 5.
Все точки в массиве отсортированы по первой координате.

Также пусть у нас есть прямоугольник со сторонами width и height.
Задача: нужно провести вычисления таким образом, чтобы прямоугольник, двигаясь в положительном направлении оси абсцисс, все время касался своими нижним левым и нижним правым углом данной кривой.
То есть визуально будет выглядеть словно прямоугольник двигается по этой кривой (ну не совсем, но неважно).

Задача, как я понял заключается в следующем: сдвигая каждый раз центр прямоугольника на dx, получать координату y центра прямоугольника и угол поворота прямоугольника вокруг своего центра.

Если кто-нибудь сможет помочь, буду благодарен.

@темы: Вопрос, Алгоритм

Comments

[CD_Eater]

левая нижняя точка у вас равномерно бежит по графику функции
правая нижняя вычисляется как точка, лежащая на графике и одновременно на окружности радиуса width с центром в первой точке (несложная система уравнений, решений может быть даже больше двух, нужно выбрать точку, которая ближе к точке с предыдущего шага, при равенстве расстояний - у которой больше абсцисса)
зная две нижние точки прямоугольника, вычисляется его центр и угол наклона (опять несложно)
самый прикол в том, что не по всем графикам прямоугольник сможет проехать!!! (пример: график в виде буквы W, у которой длина палочек равна width)

[Ri]

CD_Eater всё правильно говорит.

А есть требования насчет скорости движения прямоугольника? Она должна быть постоянной относительно Ox? Или относительно графика функции? Как прямоугольник должен вести себя на изломах?

Откуда вообще эта задача появилась?

[krossovochkin]

CD_Eater, насчет пересечения графика с окружностью - это отличная идея. есть только проблема, которую я вижу навскидку.
когда у меня задан массив точек на плоскости, которые представляют собой к-г функцию, соединенные друг за другом, то я могу использовать эту информацию только так:
- getY(float x) - получить у по х
- получить уравнение прямой в какой-либо конкретной х. (можно считать, что если я попадаю в узел, то брать "правую" часть)
и возникает проблема в составлении системы. На примере. Я беру левую нижнюю точку прямоугольника и строю окружность с радиусом width - тут все просто.
но как найти пересечение этой окружности с кривой?
Приходит в голову только цикл: пусть левый нижний угол принадлежит отрезку этой кривой с номером I, тогда беру отрезок II, получаю для него уравнение - смотрю, решается ли система. Если вдруг нет - то беру отрезок III и т. д. пока не найду пересечение.
Но это может быть достаточно затратный способ (особенно если разбиение на прямые кусочки будет очень мелким).
Но ничего быстрее мне в голову сейчас не приходит.

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

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

Ri, требований фактически никаких нет, кроме того, что она постоянна. В первом приближении, я считаю, что скорость постоянна относительно Ox. В дальнейшем можно сделать так, чтобы скорость была постоянна относительно графика.
Всегда прямоугольник должен нижними углами касаться графика. Прямоугольник может пересекать график.

Задача взялась вот откуда:
Есть путь, который задается последовательным набором точек. По этому пути движется тело - пусть это будет автомобиль - на колесах. Надо его переместить по этому пути так, чтобы было ощущение, что автомобиль едет по дороге (то есть надо, чтобы колеса были на дороге). Дорога имеет некоторую толщину - линия, которая задается функцией проложена по середине этого пути. Точек пути достаточно много (каждый отрезок пути меньше по размерам чем ширина автомобиля), но на пути есть и выпуклости и вогнутости.
Это все из одной игрушки, которая мне досталась в наследство. Там какой-то паршивый алгоритм был - что машина как будто крутилась, а не ехала. К тому же в коде было написано очень криво - разобраться в задумке просто не представляется возможным.
Хотел использовать физический движок, чтобы движение было вообще идеальным, но по некоторым причинам это оказалось невозможным.
Сейчас необходимость изменения того, что есть сейчас, отпала, но то, что я никак не могу это сделать меня угнетает. Просто не могу оставить эту задачу, которую уже не надо делать, потому что она с виду простая, пока я ее не сделаю...

[Ri]

Пусть мы движемся из точки 0 по этой дороге с равномерной скоростью v. Тогда в каждый момент времени t переднее колесо отстоит от начала дороги на vt. Пусть длина i-го участка дороги s(i). Тогда мы находимся на i-м участке, когда


А расстояние от начала текущего участка дороги до колеса определим как


Зная это расстояние и координаты отрезка, узнаем точную координату колеса.

Чтобы определить положение второго колеса, можно поступить так. Сначала определяете, с какой точностью вам надо узнать угол наклона машины, чтобы это нормально выглядело. Потом мысленно ставите машину так, чтобы второе колесо оказалось над первым, и начинаете ее крутить с выбранным шагом, чтобы первое колесо не двигалось, а второе колесо оказалось сзади. На каждом шаге проверяете, над или под дорогой находится колесо. Когда оно оказывается под дорогой, берете это или предыдущее положение и фиксируете.

[krossovochkin]

CD_Eater, Ri, спасибо за идеи - я думаю, сейчас у меня все получится