Преобразование ломаной линии

#cpp #алгоритм #геометрия #2d

                    
Я имею неравномерную сетку в виде координат узлов в двумерном пространстве
Узлы сетки хранятся в одномерном векторе, где нумерация снизу-вверх слева-направо



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

Количество точек ломаной линии не совпадает с количеством точек результирующей ломаной.

Есть ли у кого-нибудь идеи по решению данной задачи?
    

Ответы

Ответ 1

Алгоритм:


Выбираем клетки, через которые проходит ломаная.





Циклично проверяем выбранные клетки:


2.1 Берем на границах клетки две точки, в которых ломаная пересекает эту клетку (или
одну из крайних точек ломаной) и соединяем отрезком.



2.2 Сдвигаем отрезок так, чтоб обе точки находились на границах клетки (в случае
с крайними точками ломаной).

2.3 Считаем углы между отрезком и границами к летки, к которым прилегает отрезок
(достаточно неточного расчета в три варианта >45|=45|<45).



2.4 "основная" граница будет та, у которой угол <45 (обведено красным). Если угол
=45, то обе границы равнозначны.

Повторяем для всех клеток




На основе полученных выборок по две границы строим ломаную




Может получиться, что ломаная пройдет "вдоль" нескольких клеток, в этом случаем сравниваем
результаты проверки текущей клетки и предыдущей. Если сторона клетки с минимальным
углом одинаковая в обоих клетках, то вторую сторону не учитываем.


Ответ 2

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

Если синяя линия проходит через этот прямоугольник, значит, она задействует соответствующий
узел основной сетки.

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

Обходя все сегменты синей линии мы получаем несколько таких массивов. Нужно их слить
в один. Если последний узел в предыдущем массиве равен первому узлу в последующем массиве,
записывать этот узел в результирующий массив всего один раз.


Ответ 3

#include 
#include 
#include 
using namespace std;


int main()
{  
    // вообше то с такими задачами хранить лучше в std::valarray
    // допустим количество узловых точек = 4 * 4 и для примера приведу 
    //конкретные цифры
    // в задаче же уже заданы эти цифры, я лишь для демонстрации идеи
    const int n = 4;
    valarray< int > matrix(n * n);
    // инициализируем первую строку снизу от нулевого индекса `n` штук
    valarray row{ 2, 4, 7, 8 };
    // теперь учитываем что разница между соответствующим элементами
    // следующей строки должны быть одинаковыми.
    //  и допустим эти цифры заданы в векторе
    vector dif{ 3, 2, 4 };
    // инициализируем последовательность по срезам
    for (int i = 0; i < n; ++i) {
        matrix[slice(i * n, n, 1)] = row;
        if (i == n - 1) break;
        row += dif[i];
    }
   // точки на кривой лучше хранить в map, так как кривая монотонно растет
    map curve{{ 3.4, 2.7 }, {4.1, 6}, {5, 9.3}};
    // для первой точки на кривой
    auto para = curve.begin();
    // теперь берем  ближайшие целые этих точек
    int x = lround(para->first), y = lround(para->second);
    //...
    return 0;}


теперь чтобы знать к каким элементам нашей последовательности ближе точка с 
    координатами (x, y) всего лишь дело техники... для сравнения y наверняка понадобится
dif, а
    STL альгоритмы дадут нам возможность рассмотреть любое количество точек
    с соответствующими предикатами. Вообшем идея такая, дальше подумайте сами


Ответ 4

0) Учащаем точки ломаной: в цикле определяем расстояние между соседними точками (D)
у ломаной, если это расстояние больше, чем расстояние диагонали ячейки сетки (d), то
вставляем дополнительною точку.




Это шаг предобработки ломаной. В конце объясню зачем это нужно

1) Определяем ближайший узел (curr_node) к начальной точке (p) исходной ломаной


Далее в цикле:

2) Определяем соседние узлы для curr_node (соседями не считать предыдущий посещенный
узел)



3) Определяем расстояние от curr_node и от его соседних узлов до следующей точки
ломаной (p_next). 



4) Если расстояние от curr_node до p_next меньше, чем минимальное расстояние от его
соседей до p_next, то p_next станет следующей точкой ломаной, иначе "посещаю" следующий
узел сетки (тот соседний узел, который ближе всего к точке p_next)

Далее возвращаемся к шагу 2

В итоге получаем такую картину посещения узлов



т.е. собирая посещенные узлы (черные), получаем такую ломаную, проходящую по узлам сетки:



А теперь покажу зачем нужно было делать нулевой шаг:



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

Как повернуть треугольник к новой нормали?

#алгоритм #opengl #геометрия

Жил был треугольник и была у него нормаль, но вот однажды нормаль изменила ему и
стала смотреть в другую сторону, на совсем другой вектор.

Погоревал треугольник 1мс и решил тоже повернутся чтоб зажили они как и прежде.

Задачка:
Как повернуть треугольник к его нормали? что бы жили они долго и по перпендикулярному?
    

Ответы

Ответ 1

выбираем нулевую вершину треугольника A за базовую точку
откладываем от неё произвольный вектор, перпендикулярный новой нормали и с длиной
вектора AB
вычисляем вектор AD , перпендикулярный N и AB', как их векторное произведение
находим вектор AC' как линейную комбинацию AB' и AD, обеспечивающую нужную длину
AC и угол AC'B'


Для других вариантов постановка задачи не обеспечивает достаточно данных.

Вычислить координаты ортогональной проекции точки на отрезок

#javascript #математика #геометрия

Проект для создания чертежей в svg, на нативном js. 

Столкнулся со следующей задачей:

Известны координаты 3х точек A B C на плоскости. Точки A B являются началом и концом
отрезка AB. Нужно найти координаты ортогональной проекции (точка D) точки С на отрезок
АВ. Как это сделать?
    

Ответы

Ответ 1

Проекцию можно найти, используя скалярное произведение векторов

 D = A + AB * Dot(AC, AB) / Dot(AB, AB)


В псевдокоде:

 abx = B.X - A.X
 aby = B.Y - A.Y
 dacab = (C.X - A.X) * abx + (C.Y - A.Y) * aby
 dab = abx * abx + aby * aby
 t = dacab / dab
 D.X = A.X + abx * t
 D.Y = A.Y + aby * t


Здесь немного другие обозначения (C=P, N=D) и пояснения


Ответ 2

Метод "пересечения":

Если построить точку С' = (Cx - (By - Ay), Cy + (Bx - Ax)), то прямая CC' будет перпендикулярна
прямой AB. Пересечение прямых AB и CC' даст вам точку D.

Метод "тяжеловат" с вычислительной точки зрения из-за того, что использует пересечение
двух прямых в качестве примитива. Но прост в реализации, если такой примитив уже есть
под руками.
Метод "расстояния":

Если AA, BB и CC - коэффициенты уравнения прямой, содержащей отрезок AB (легко вычисляются
через координаты точек A и B), то величина

DD = AA * Cx + BB * Cy + CC


даст вам знаковое расстояние от этой прямой до точки C, домноженное на |(AA, BB)|.
Если к точке C прибавить вектор DD * (-AA, -BB), то мы получим точку, которая смещена
относительно C в правильном направлении, но, условно выражаясь, "слишком далеко": расстояние
превышает требуемое в |(AA, BB)|^2 раз. Достаточно разделить смещение на эту величину
- мы получим требуемую точку D

             DD 
D = C + ------------ * (-AA, -BB)
        |(AA, BB)|^2


Этот метод тоже несколько громоздок из-за "лишних" вычислений уравнения прямой, но
может быть полезен, если вы и так уже знаете/вычисляете уравнение прямой, а также если
вам в дополнение к точке проекции нужно еще вычислять и расстояние от C до AB.
Метод "скалярного произведения":

Очевидно, что 

        |(A, D)|
D = A + -------- * (A, B)
        |(A, B)|


При этом скалярное произведение вектора (A, C) на вектор (A, B) - это длина проекции
(A, D), домноженная на |(A, B)|. 

(A, C)•(A, B) = |(A, D)| * |(A, B)|


Тогда

        (A, C)•(A, B)
D = A + ------------- * (A, B)
          |(A, B)|^2



(Можно показать, что если собрать все вычисления второго метода в одну формулу, то
она "сократится" до третьего метода.)

Проверить, принадлежит ли какая-либо точка отрезка заданной (заданным) окружностям

#cpp #геометрия

Привет. Прошу помощи. В общем задача: на координатной плоскости задается отрезок
с началом в точке А и с концом в точке В. Также задаются круги (можно и 1 круг) с центрами
в точках M1,M2,M3,...M100 и с радиусами R1,R2,R3,...,R100. Нужно проверить, принадлежит
ли какая-либо точка отрезка заданной (заданным) окружностям.
В общем-то это задача из олимпиады, код компилируется на сервере. Мой код: http://ideone.com/J5MJEH 
double xA, yA, xB, yB;
int count = 0;
int n;

cin >> xA >> yA >> xB >> yB; // Координаты A и B отрезка: 
cin >> n; // Количество окружностей

double * * Arr = new double * [3]; // Задаем массив для кругов, в каждой строчке
которого будут хранится x,y,r круга
for (int i = 0; i < n; i++)
    Arr[i] = new double[3];

for (int i = 0; i < n; i++) {
    for (int j = 0; j < 3; j++) {
        cin >> Arr[i][j];
    }
}
double r12 = sqrt((xB - xA) * (xB - xA) + (yB - yA) * (yB - yA)); // Длина отрезка
от A до B
for (int i = 0; i < n; i++) {
    double r1 = sqrt((Arr[i][0] - xA) * (Arr[i][0] - xA) + (Arr[i][1] - yA) * (Arr[i][1]
- yA)); // Длина отрезка от т. M до A
    double r2 = sqrt((Arr[i][0] - xB) * (Arr[i][0] - xB) + (Arr[i][1] - yB) * (Arr[i][1]
- yB)); // Длина отрезка от т. M до B

    if (((r12 * r12 + r1 * r1) - r2 * r2) >= 0 && ((r12 * r12 + r2 * r2) - r1 * r1)
>= 0) { // Если перпендикуляр опущенный на прямую, проведенную через A u B лежит на
отрезке AB, то проверяем, равен или больше ли радиус окружности
        double d = (abs((yB - yA) * Arr[i][0] + (xB - xA) * Arr[i][1] + (xA * yB
- yA * xB))) / sqrt((yB - yA) * (yB - yA) + (xB - xA) * (xB - xA));
        if ((Arr[i][2] - d) >= 0) {
            count++;
        }
    } else { // Иначе, если перпендикуляр опущенный на прямую лежит вне отрезка,
то проверяем, равен или больше ли радиус одному из отрезков от точки М до А или В
        if ((Arr[i][2] - r1) >= 0 || (Arr[i][2] - r2) >= 0) {
            count++;
        }
    }
}
cout << count;

В комментариях кода написал, что,где, как нахожу.
То, как определить, падает ли перпендикуляр на отрезок, я взял отсюда: http://algolist.manual.ru/maths/geom/misc/perp.php,
а именно неравенства: B2 <= A2 + C2, C2 <= A2 + B2.
В общем-то программа работает, но, вероятно, не всегда правильно. Уже достаточно
много перепробовал тестовых примером, всё правильно определяет. Но, когда отправляю
решение на сервер олимпиады, сервер говорит: "Wrong Answer". Я все грешу на типы. Сможете
помочь?     

Ответы

Ответ 1

Вы не проверяете случай, когда часть отрезка лежит в одной окружности, а часть -
в другой. Например, A(10, 10), B(10, 20), M1(10, 10), R1(5), M2(10, 20), R2(5). тут
половина отрезка лежит в первой окружности, а половина - во второй.
http://ideone.com/TdMCuz
Я бы предложил следующий алгоритм. Для каждой окружности проверяем, лежит ли отрезок
в ней полностью (т. е. лежат ли оба конца отрезка внутри окружности). Если да, то ответ
- "да", выходим. Если оба конца отрезка вне окружности, переходим к следующей окружности.
Если один конец внутри, а другой - снаружи, то обезаем отрезок, оставляя только ту
его часть, что снаружи, и продолжаем проверки. Если после проверки всех окружностей
остался ненулевой участок отрезка, ответ - "нет".


Ответ 2

Проверку того, что какая-либо точка отрезка принадлежит окружности, можно заменить
на проверку всего лишь трёх точек: концов отрезка и проекции центра окружности на прямую,
содержащую отрезок (третью точку берём только если она принадлежит отрезку).
Вы же проверяете третью точку, но не проверяете края. То есть, теряете случай, когда
очень короткий отрезок пересекает границу окружности. (Плюс наверное где-то ошибки
реализации из-за очень «низкоуровневого» кода.)
Реализация не очень сложна (но придётся вспомнить геометрию за 9-ый класс):
bool GetProjection(const Segment& segment, const Point& source,
                   Point& projection)
{
    Vector direction = segment.end - segment.begin;
    double segmentLength = direction.Length();
    Vector unitDirection = direction / segmentLength;
    Vector beginToSource = source - segment.begin;
    double projectionLength = scalarProduct(unitDirection, beginToSource);
    if (projectionLength < 0 || projectionLength > segmentLength)
        return false;
    projection = segment.begin + unitDirection * projectionLength;
    return true;
}

bool IsPointInCircle(const Point& point, const Circle& circle)
{
    var radiusVector = point - circle.center;
    return radiusVector.Length() <= circle.radius;
}

bool AnyPointInCircle(const Segment& segment, const Circle& circle)
{
    Point projection;
    return
        IsPointInCircle(segment.begin, circle) ||
        IsPointInCircle(segment.end, circle) ||
        (GetProjection(segment, circle.center, projection) &&
            IsPointInCircle(projection, circle));
}

Классы Point, Vector и прочие определяются самоочевидным образом.


Ответ 3

На рисунке изображены два случая непересечения отрезком окружности:


Когда прямая не пересекает окружность.
Когда прямая пересекает окружность, а отрезок не пересекает.




Для каждой окружности (R,M) и отрезка AB можно применить следующий алгоритм: 


Вычисляем коэффициенты уравнения
(A+qB)/(1+q) on (R,M), или
(xa + q* xb - (1+q)* xm)2 + (ya + q* yb - (1+q)* ym)2 = (1+q)2*R2:
С2q2+2C1q+C0 = 0, где
C0 = (xa - xm)2 + (ya - ym)2 - R2,
C1 = (xa - xm) * (xb - xm) + (ya - ym) * (yb - ym) - R2,
C2 = (xb - xm)2 + (yb - ym)2 - R2.  
Если C0 <= 0, точка A попала в круг.
Если C2 <= 0, точка B попала в круг.
Если det = C12 - C0C2 <= 0, прямая АB с кругом не пересекается.
Вычисляем корни уравнения q1 и q2 (если есть).
Если q1 >= 0 ИЛИ q2 >= 0, то попали.
Иначе не попали.  


Программа:

function are_crossed($a, $b, $r, $m){
    $rr = $r*$r;        
    $am = array($a[0] - $m[0], $a[1] - $m[1]);      // вектор AM 
    $bm = array($b[0] - $m[0], $b[1] - $m[1]);      // вектор BM 
    $eq = array(
        $am[0]*$am[0] + $am[1]*$am[1] - $rr,
        $am[0]*$bm[0] + $am[1]*$bm[1] - $rr,
        $bm[0]*$bm[0] + $bm[1]*$bm[1] - $rr
    );
    $det = $eq[1]*$eq[1] - $eq[0]*$eq[2];

    if($eq[0] <= 0) return 1;                       // начало отрезка попало в круг
    if($eq[2] <= 0) return 2;                       // конец отрезка попал в круг
    if($det < 0) return -1;                         // линия не пересекает круг

    $d = sqrt($det); 
    $root1 = ( -$eq[1] - $d) / $eq[2];              // первая точка пересечения линии
и круга 
    $root2 = (-$eq[1]+$d)/$eq[2];                   // вторая точка пересечения линии
и круга

    if(($root1>=0) return 3;                        // первая точка принадлежит отрезку
    if(($root2>=0) return 4;                        // вторая точка принадлежит отрезку
    return -2;                                      // обе точки пересечения - вне
отрезка 
} 

$a = array(5, 20);
$b = array(25, 5);
$m = array(5, 5);
$r = 12;

$result = are_crossed($a, $b, $r, $m);
print "A = "; print_r($a);
print "
B = "; print_r($b);
print "
M = "; print_r($m);
print "
R = $r";
print("
result = $result
");
print($result>0 ? "пересекаются" : "не пересекаются");


Результаты:



A = Array ( [0] => 5 [1] => 20 ) 
B = Array ( [0] => 25 [1] => 5 ) 
M = Array ( [0] => 5 [1] => 5 ) 
R = 12
result = 3
пересекаются

Как составить правильную формулу расчета угла между векторами?

#математика #геометрия #вектор

Есть стандартная формула расчета угла между векторами:



И вот есть два вектора, угол между которыми никак не вычислить, так как правая часть
уравнения меньше -1. Вот эти вектора:

var x1 = -0.045797169475341334, y1 = -0.9989507591808752;
var x2 = 0.04579716947534099, y2 = 0.9989507591808753;


В итоге, выражение:

(x1 * x2 + y1 * y2) / Math.sqrt(Math.pow(x1, 2) + Math.pow(y1, 2)) * Math.sqrt(Math.pow(x2,
2) + Math.pow(y2, 2))


дает результат: -1.0000000000000002

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

Как мне скорректировать формулу, чтобы этой ошибки не было?
    

Ответы

Ответ 1

Варианта решения проблемы имеются как минимум 2. Оба они требует, чтобы оба вектора
имели ненулевую длину, но для вектора с нулевой длиной сама постановка вопроса о каком-либо
угле не вполне корректна, и как Вам обрабатывать такую ситуацию, Вам должно быть виднее.

1) вычисляем промежуточное значение:

r = (x1 * x2 + y1 * y2) / Math.sqrt(Math.pow(x1, 2) + Math.pow(y1, 2)) * Math.sqrt(Math.pow(x2,
2) + Math.pow(y2, 2))


Проверяем на попадание r в диапазон [-1, 1]:

if (r < -1) r = -1; if (r > 1) r = 1;


Вычисляем арккосинус. Так убираются ошибки округления, "выбивающие" r из диапазона.

2) Пользуемся функцией atan2

phi = Math.atan2(y2, x2) - Math.atan2(y1, x1);


При необходимости, приводим полученный угол в нужный диапазон (0-180град или -90 - +90)



Я бы написал так:

if (phi < 0) phi += Math.PI * 2;
if (phi > Math.Pi) phi -= Math.PI;




Оба алгоритма выдадут ошибку при x1=y1=0 или x2=y2=0, о чем написано выше.
Вариант с atan2, имхо предпочтительней, т.к., например при x1=y1=1e+10, x2=y2=1e-10
точность вычислений по первому варианту будет околонулевой (e10 взято просто для примера,
м.б. нужно существенно больше).



Математические функции указаны для Java, для .NET названия содержат заглавную букву:
Math.Sqrt, Math.Atan2 и т. д.


Ответ 2

Если есть желание воспользоваться формулой для разности углов (а оно понятно из вопроса),
то можно использовать тангенсы половинного аргумента с периодом 360: 
phi = 2(Math.atan2(y2, x2+r2) - Math.atan2(y1, x1+r1));

Проверим эту формулу на данных  x1 = sqrt(3), y1=1, x2= - sqrt(3), y2=1 r1=r2=2:
Правильный ответ: cos(fi) = -1/2, fi=120.
По формуле для разности:
fi1=2arctg(1/(2+sqrt(3))) = 30, fi2=2arctg(1/(2-sqrt(3))=150, fi=fi2-fi1 = 120.
Остаётся только преобразовать интервал, на выбор:
 либо mod(fi,360), либо mod(fi+180,360)-180 

В то же время:


Модуль нужно убрать, потому что его нет в теории.
Тангенсы в чистом виде лучше не использовать, потому что есть риск ошибки.
Так, для тех же данных по формуле
phi = (Math.atan2(y2, x2) - Math.atan2(y1, x1);
имеем:
fi = arctg(sqrt(-3)) - arctg(sqrt(3)) = -120.
Парадокс объясняется тем, что тангенс имеет период 180, а
сos(fi+180) = cos(fi)cos(180)+sin(fi)sin(180) = - cos(fi).

Как по имеющимся координатам начала и конца двух линий узнать пересекаются ли они? Аналог Line2D.intersectsLine на Android

#java #android #геометрия

Дано:

Координаты 4 (A, B, C, D) точек на плоскости (int x, int y). 

Задача:

Узнать пересекутся ли линии, A-B и C-D.

Проблема:

Как я понял из гугла, то в java есть класс Line2D, а у него метод intersectsLine(Line2D
line) возвращающий то, что надо. Но в андроиде нема пакета java.awt.geom. Нашёл на
gitHub порт библиотеки сей, но он древний и почти без звёзд и заброшен.

Вопрос:

Так таки есть ли готовые решения сей задачи или надо вспоминать геометрию и собирать
велосипед?
    

Ответы

Ответ 1

Вот вам код из java.awt.geom.Line2D.linesIntersect, он ссылается только на один метод
java.awt.geom.Line2D.relativeCCW

public static boolean linesIntersect(double x1, double y1, double x2, double y2, 
                                     double x3, double y3, double x4, double y4) {

    boolean r1 = relativeCCW(x1, y1, x2, y2, x3, y3) * 
                 relativeCCW(x1, y1, x2, y2, x4, y4) <= 0;

    boolean r2 = relativeCCW(x3, y3, x4, y4, x1, y1) * 
                 relativeCCW(x3, y3, x4, y4, x2, y2) <= 0;
    return r1 && r2;
}


public static int relativeCCW(double x1, double y1, double x2, double y2,
                              double px, double py) {
    x2 -= x1;
    y2 -= y1;
    px -= x1;
    py -= y1;
    double ccw = px * y2 - py * x2;
    if (ccw == 0.0) {
        ccw = px * x2 + py * y2;
        if (ccw > 0.0) {
            px -= x2;
            py -= y2;
            ccw = px * x2 + py * y2;
            if (ccw < 0.0) {
                ccw = 0.0;
            }
        }
    }
    return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0);
}


Ответ 2

Если ничего не напутал, то 

boolean intersection(double x1, double y1, ... double x4, double y4){
    Double x=null;
    double y;
    Double a,a1=null,a2=null;
    Double b,b1=null,b2=null;
    if(x1==x2){
        if(x3==x4) return false;
        x=x1;
    }else{
        a1=(y1-y2)/(x1-x2);
        b1=y1-a1*x1;
    }

    if(x3==x4){
        x=x3;
    }else{
        a2=(y3-y4)/(x3-x4);
        b2=y3-a2*x3;
    }

    if(x==null){
        x=(b2-b1)/(a1-a2);
    }
    if(x==x1){
        a=a2;
        b=b2;
    }else{
        a=a1;
        b=b1;
    }
    if(x>Math.max(x1,x2)||x>Math.max(x3,x4)||x=Math.min(y1,y2)&&y<=Math.max(y1,y2)&&y>=Math.min(y3,y4)&&y<=Math.max(y3,y4);
}

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

#математика #геометрия

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

У меня есть идея только того, что чтобы найти новые координаты фигуры, нужно минимизировать
расстояния между вершинами первого треугольника и второго (т.е. взять производную и
приравнять нулю), однако как действовать дальше не знаю ..
    

Ответы

Ответ 1

Будем пользоваться полярными координатами. Зададим 2 треугольника парами значений
в полярных координатах:





Угол поворота второго треугольника относительно первого: 

Так как у вас нет четкого условия про минимальное расстояние, возьмем сумму квадратов
расстояний (визуально это должен быть наилучший вариант). Используя формулу для расстояния
между 2 точками на полярных координатах получаем такие квадраты расстояний:







Мы должны найти минимум функции сумм этих 3 величин. В нас здесь много констант,
что бы упростить формулу, положим:















И тогда наша сумма квадратов расстояний примет вид:



Возьмем производную, что бы найти экстремумы функции:



Если расписать синус разницы, то получим:



Положим:





И получим:



Такое уравнение легко решить, если взять такой угол , что:





Тогда уравнение примет вид:



Такое легко решить. Дальше нужно повторить все это, смещая точки второго треугольника:
сначала сместить на 1 (первая точка станет второй, вторая третьей и т. д.), потом на 2.

Найти координаты точки, лежащей на биссектрисе угла, образованного двумя векторами, зная их координаты

#алгоритм #геометрия #векторы

Даны 2 вектора а и b, исходящие из точки А, необходимо найти координаты точки В.
Расстояние АВ вычисляю, АВ делит угол, образованный векторами пополам. Предполагаю
перемещать координаты т.А для поиска В: 

В = (Ах + АВ * Соs Alpha; Аy + АВ * Sin Alpha)

Затем строю вектор от А по Ох:

e = {100; 0}  


Нахожу углы между а,е и b,e:

cos Betta = a * e / |a| * |e| ;   cos Gamma = a * e / |a| * |e|


И вот теперь для поиска Alpha, возможны два условия:

Alpha = (Betta - Gamma) / 2


Либо

Alpha = (Betta - Gamma) / 2 + min(Betta, Gamma)


Скажите, верны ли мои суждения? И какое условие должно быть для поиска Alpha?
    

Ответы

Ответ 1

точки, лежащей на биссектрисе угла


Вы знаете сколько там точек, на биссектрисе? Миллионы!



Все гораздо проще. Приведите вектора а и b к единичной (или любой одинаковой) длине
и сложите (векторно, конечно). Добавьте координаты их суммы к координатам точки А -
это будет точка B. А AB - это диагональ ромба, построенного на приведенных векторах
равной длины. Если в условии есть требование к длине |AB|, приведите получившийся вектор
AB к этой длине.

Линейное движение точки под углом: отскок

#анимация #алгоритм #геометрия

Приветствую.
В общих чертах, пишу алгоритм перемещения точки в пределах прямоугольника, скажем
600 x 400. Точка имеет такие свойства:

текущие координаты X и Y, при чем, X = [0,600]; Y = [0,400] (просто перемещаю div
по relative-контейнеру)
кинетический заряд A (длина шага за 1 такт — гипотенуза)
угол Angle (град.)

Сначала долго ломал голову насчет самого передвижения точки в направлении, указанном
углом Angle. Когда обнаружил решение, стало стыдно. Вот оно:
X = X + A * cos(Angle * PI / 180);
Y = Y + A * sin(Angle * PI / 180);

С этим все нормально:

если Angle = 0, то точка движется вправо по OX,
если Angle = 180, то влево,
если Angle = 90, то вниз по OY (!),
если 45 — то вправо-вниз...

Но уже битый час не могу понять, какие ставить условия и как разворачивать угол при
столкновении со «стеной» прямоугольника, которым описана площадь, за которую точка
не должна вылезти.
В каждой итерации (такт) происходит смещение точки по приведенным выше формулам и
делается тест на столкновение. Извиняюсь за толстую просьбу, но я прошу дополнить (поправить?)
эту секцию кода:
if (x <= 0)
    { Angle = ... }
else if (x >= 600)
    { Angle = ... }

if (y <= 0)
    { Angle = ... }
else if (y >= 400)
    { Angle = ... }

И еще у меня может быть и само движение неправильно описано, тоже поправьте пожалуйста,
если так (у меня такое впечатление, что по-правильному, с увеличением угла Angle траектория
точки должна заворачиваться против, а не по часовой — как у меня).    

Ответы

Ответ 1

исправил я функцию step, обратите внимания на коментарии
this.step = function()
    {
    this.x = this.x + this.a * Math.cos(this.angle * Math.PI / 180);
    this.y = this.y + this.a * Math.sin(this.angle * Math.PI / 180);

    if (this.x <= 0)
        { // 
          this.angle = 180 - this.angle;
          if (this.angle < 0) this.angle += 360; // что бы угол был положительным
        }
    else if (this.x >= 600)
        { // 0 -> 180   10 -> 170
           this.angle = 180 - this.angle;
           if (this.angle < 0) this.angle += 360;
        }

    if (this.y <= 0)
        { // 270 -> 90  269 -> 91
          this.angle = 360 - this.angle;
        }
    else if (this.y >= 400)
        { // 90 -> 279   180 - 180
        this.angle = 360 - this.angle;
        }

    return this;
    };

или даже ещё короче
this.step = function()
    {
    this.x = this.x + this.a * Math.cos(this.angle * Math.PI / 180);
    this.y = this.y + this.a * Math.sin(this.angle * Math.PI / 180);

    if (this.x <= 0 | this.x >= 600)
        { // 
            this.angle = 180 - this.angle;
            if (this.angle < 0) this.angle += 360;
        }

    if (this.y <= 0 | this.y >= 400)
        { // 270 -> 90  269 -> 91
          this.angle = 360 - this.angle;
        }
    return this;
    };

Соединить две окружности. В чём ошибка?

#javascript #svg #vector #геометрия #2d

Пытаюсь повторить полигон, тот что изображен зеленой линией на рисунке ниже. Пользовался
этими советами:

Совет первый 
Совет второй

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

Jsfiddle проект 

Писал на JS, но подойдёт любое другое решение.
Даже без кода, в чистой теории, в чем неверен мой подход.



//

    

Ответы

Ответ 1

Поскольку нужны только внешние касательные (могут быть ещё внутренние), то подход
может быть не слишком сложным:

Пусть центр большей окружности CR, меньшей cr. Вектор разности d, его длина и нормализованный
вектор:

 d = cr - CR
 dlen = length(d)
 ud = d / dlen


Общие касательные к окружностям разного радиуса пересекаются где-то в точке OP. Касательная
вместе с радиусами к точкам касания образует два подобных прямоугольных треугольника
(поскольку радиус перпендикулярен касательной). Из подобия следует

Coeff = R / (R - r)
OP = CR + d * Coeff


Синус и косинус угла A этого треугольника  

ca = R / (dlen * Coeff)
sa = Sqrt(1-ca*ca)


Точки касания большой окружности могут быть получена поворотом вектора ud*R на A и -A

P.x = CR.x + ca * R * ud.x + sa * R * ud.y
P.y = CR.y - sa * R * ud.x + ca * R * ud.y
Q.x = CR.x + ca * R * ud.x - sa * R * ud.y
Q.y = CR.y + sa * R * ud.x + ca * R * ud.y


Аналогично для малой окружности с использованием её центра и радиуса. 

Тест:



fiddle:  (подправил последовательность точек и знаки углов)

let c1 = this.state.circles[0];
let c2 = this.state.circles[1];

let l = getVectorLen(c1,c2);

let v = {x: c2.x-c1.x, y: c2.y-c1.y};
let uv = {x: v.x / l, y: v.y / l};

let ca = (c2.r - c1.r) / l;
let sa = Math.sqrt(1 - ca*ca);

let ps = [

    c1.x - ca * c1.r * uv.x - sa * c1.r * uv.y, 
    c1.y + sa * c1.r * uv.x - ca * c1.r * uv.y,
    c1.x - ca * c1.r * uv.x + sa * c1.r * uv.y,
    c1.y - sa * c1.r * uv.x - ca * c1.r * uv.y,

    c2.x - ca * c2.r * uv.x + sa * c2.r * uv.y,
    c2.y - sa * c2.r * uv.x - ca * c2.r * uv.y, 
    c2.x - ca * c2.r * uv.x - sa * c2.r * uv.y, 
    c2.y + sa * c2.r * uv.x - ca * c2.r * uv.y 
];


Ответ 2

На картинке 2 из вашего вопроса имеется две окружности с центрами в точках c1 и c2
радиусов r1 и r2. Центры окружностей соединены прямой. Необходимо в каждой окружности
провести 2 диаметра перпендикулярных отрезку, соединяющему центры. Точки пересечений
диаметров с окружностью образуют искомый четырехугольник (трапецию).

circles: [
        { r: 20, x: 50, y: 150, f: 'black'},   // c1
        { r: 50, x: 150, y: 100, f: 'black'}   // c2
    ]


Для решения необходимо определить угол alpha между вектором c1c2 и осью Х. После
чего будет понятно, под каким углом проходят диаметры. Нам потребуется поставить 4
точки, каждая из которых будет удалена от центра на расстояние радиуса под углом alpha
+ 90 или alpha - 90.

Как известно, тангенс угла в прямоугольном треугольнике равен отношению длины противолежащего
катета к прилежащему. Так что угол alpha достаточно просто вычисляется с помощью формулы
(не рассматриваем ситуацию когда x1=x2):

let alpha = Math.atan( (c2.y - c1.y) / (c2.x-c1.x) );


Если нам известна исходная точка (x0, y0), и нам надо сдвинуться на расстояние R
под углом a, то координаты новой точки будут иметь вид x1 = x0 + R*Cos(a) и y1 = y0
+ R*Sin(a).
В данном случае R будет принимать значения r1 и r2 (радиусов окружностей), а угол
с поворотом на 90 градусов -  alpha + PI/2 и alpha - PI/2.

В исходном виде формула для вычисления координат первой точки будет иметь вид

x1 = c1.x + Math.cos(alpha + Math.PI/2)*c1.r;
y1 = c1.y + Math.sin(alpha + Math.PI/2)*c1.r;


Для второй - то же самое с углом alpha - Math.PI/2. Затем аналогичные равенства для
окружности c2.

Вспомнив тригонометрические формулы приведения (про углы α ± π/2 и -α) все эти вычисления
сводятся к следующему:

let cosA = Math.cos(alpha);
let sinA = Math.sin(alpha);

let ps = [
    c1.x - sinA*c1.r, // x1 
    c1.y + cosA*c1.r, // y1    
    c1.x + sinA*c1.r, // x2 
    c1.y - cosA*c1.r, // y2

    c2.x + sinA*c2.r, // x3 
    c2.y - cosA*c2.r, // y3
    c2.x - sinA*c2.r, // x4 
    c2.y + cosA*c2.r, // y4        
];


jsfidlle

Как рассчитать радиус?

#математика #геометрия

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

  

Когда я поверну угол на 90 градусов вокруг точки O, то отрезок CA займет место отрезка
AB.  

Теперь представьте что угол 45 градусов.  

  

Как мне найти длину радиуса OE чтобы отложив от отрезка AB перпендикуляр равной длины,
я нашел точку, повернув угол вокруг которой на 45 градусов я поместил отрезок CA в
положение AB?
    

Ответы

Ответ 1

Если я правильно понял условие, то точку O надо поместить в точку пересечения биссектрисы
угла BAC и срединного перпендикуляра к отрезку AB.

В общем, равнобедренный треугольник AOB с основанием AB, угол OAB равен половине
угла BAC. Надо найти высоту. Для этого есть несколько способов разной сложности.


Ответ 2

Так это же очень просто, как мне кажется. Обозначим через x половину отрезка AB,
он же будет половиной АС, радиус R должен быть таким, чтобы окружность касалась отрезка
AB, и отрезка AC, деля их пополам в точках касания (доказательство этого факта обсуждается
в 9-м классе на геометрии, что касательные, выпущенные из одной точки, имеют равную
длину до момента касания окружности). Дальше получаем уравнение x/R = tg Pi/8. Отсюда
R = x / (tg Pi/8). Величину x я так понял, Вы знаете. Тангенс Pi/8 равен корню из частного
двух разностей: первая разность это корень из двух минус один, а вторая корень из двух
плюс один.

Пересечение отрезка и эллипса

#java #графика #геометрия

Дан отрезок из двух точек А и В (у каждой точки есть координаты).

Дан эллипс (пока что задаю верхней левой точкой, длиной и шириной, но при необходимости
эти параметры можно заменить на любые другие). 

Задача: узнать пересекаются ли отрезок с эллипсом. Случай, при котором отрезок полностью
в эллипсе не удовлетворяет условие.

Помогите, пожалуйста, а то ничего в голову не приходит. Если возможно, то нужен код
в java, если нет - дайте решение, а код напишу сам.
    

Ответы

Ответ 1

UPD (исходя из комментария @AnT):

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



Вариант, с помощью которого не нужно решать уравнения (без использования численных
методов):

Пусть задан эллипс:

(x-x0)^2/a^2 + (y-y0)^2/b^2 = 1


, где:


(x0;y0) – координаты центра эллипса;
a и b – длины большой и малой полуосей соответственно.


и отрезок AB, где A(x1;y1) и B(x2;y2).

Для того, чтобы отрезок AB пересекал заданный эллипс, необходимо и достаточно, чтобы
была верна одна из систем неравенств:

(x1-x0)^2/a^2 + (y1-y0)^2/b^2 < 1
(x2-x0)^2/a^2 + (y2-y0)^2/b^2 > 1


(случай, когда точка A лежит внутри эллипса, а B – вне его);

(x1-x0)^2/a^2 + (y1-y0)^2/b^2 > 1
(x2-x0)^2/a^2 + (y2-y0)^2/b^2 < 1


(случай, когда точка A лежит вне эллипса, а B – внутри его).

Если интересует случай с принадлежностью точек дуге эллипса, то в вышеприведенных
системах неравенства будут нестрогие.


Ответ 2

Из геометрии-
две линии пересекаются, если для системы уравнений, описывающей эти линии, существует
решение

создаем систему уравнений из 2х 
прямая = (x-xa)/(xb-xa)=(y-ya)/(yb-ya)
уравнение эллипса необходимо выбирать максимально вам подходящее, после чего в обоих
уравнениях выражаете  y  и решаете систему

для канонического уравнения эллипса (оси эллипса совпадают с осями координат) (x^2/a^2+y^2/b^2=1)
прямая  y=((x-xa)*(yb-ya))/(xb-xa)+ya
эллипс  y=+-sqrt((1/b^2)-(x^2/a^2*b^2))

далее подставляем все известные данные и получаем или не получаем точку, если получили
- есть пересечение, не получили = нет


Ответ 3

Любой эллипс является ни чем иным, как "растянутой" (или, если хотите, "сплюснутой")
окружностью. Достаточно построить преобразование координат, которое превратит исходный
эллипс в произвольную окружность ненулевого радиуса, и задача сведется к определению
факта пересечения отрезка с окружностью. (Понятно, что такое преобразование координат
переведет отрезок в отрезок.)

Из приведенного условия можно неявно заключить, что речь идет не о произвольном эллипсе,
а об эллипсе, оси которого параллельны осям координат. (Кстати, почему этого не сказано
явно в условии?). В такой ситуации требуемое преобразование строится элементарно -
это просто домножение одной из координат на коэффициент a/b - соотношение длин осей
эллипса.

Тем самым мы сводим задачу к задаче о пересечении отрезка и окружности.

Задача пресечения отрезка с окружностью решается просто. Достаточно вычислить координаты
концов хорды, "отсекаемой" прямой, содержащей наш отрезок (если таковая хорда существует).
Положение концов отрезка относительно концов хорды сразу же скажет нам, пересекает
ли наш отрезок данную окружность (и, если надо, даст нам координаты точек пересечения).

Обратное преобразование координат даст нам координаты точек пересечения с исходным
эллипсом (если они нас интересуют).

Область пересечения ромба и прямоугольника

#алгоритм #математика #геометрия

Известны вершины ромба и прямоугольника. Какой наиболее простой и эффективный способ
нахождения области их пересечения(координат вершин фигуры, которая одновременно принадлежит
и ромбу и прямоугольнику)?
Ромб и прямоугольник всегда имеют такую ориентацию, меняются только их размеры и
расположение на плоскости(надеюсь, правильно выразился). 


    

Ответы

Ответ 1

Для нахождения пересечения произвольных выпуклых многоугольников, особенно если один
из них является осеориентированным прямоугольником, прекрасно работает алгоритм последовательного
отсечения (Sutherland–Hodgman algorithm). 

Вы просто выбираете один из многоугольников в качестве отсекаемого, а затем в цикле
последовательно "отрезаете от него все лишнее" прямыми, содержащими стороны второго
(отсекающего) многоугольника. В вашем случае естественным решением будет выбрать именно
прямоугольник в качестве отсекающего: отсечение горизонтальными и вертикальными прямыми
выполняется тривиальным образом.


Ответ 2

Результат может быть выпуклым многоугольником с количеством вершин от 0 до 8. Чтобы
не анализировать все возможные случаи, можно использовать общий алгоритм пересечения
выпуклых многоугольников O'Rourke из книги Computational Geometry in C. 

Здесь есть ссылка на исходники. Результат - последовательность вершин в порядке обхода.

Если вероятность пересечения невелика, то вначале стоит проверить сам факт пересечения
(например, с помощью SAT - метода separating axes)

Алгоритм поиска пары ближайших точек

#алгоритм #геометрия

Подскажите, пожалуйста, алгоритм со сложностью O(n ln(n)) для поиска пары ближайших
точек (плоскость) в массиве. Было бы очень хорошо, если есть реализация на C# (но подойдет
хотя бы псевдокод).
p.s. На входе массив с точками (точки имеют координаты Х, У). На выходе - две точки,
которые находятся на самом коротком расстоянии среди всех возможных вариантов.
p.s.s. Фишка именно в сложности алгоритма: O(n ln(n)).
    

Ответы

Ответ 1

Приведу выписку из своих конспектов по АиСД:

Отсортируем наш массив по координате x и y (На выходе получим два отсортированных
массива; Время — O(nlogn)). Теперь мы запустим рекурсивную функцию, которая вернет
нам две ближайшие точки.

В рекурсивной функции мы разделим массив точек на две части относительно медианы
(за O(n)) и рекурсивно найдем в каждой из частей две ближайшие точки. Назовем кратчайшее
расстояние, известное на данный момент, δ.



Осталось проверить, нету ли таких точек, которые лежат в разных половинах, и расстояние
между ними короче, чем δ. Для этого рассмотрим любую точку и заметим вот что: если
есть точка, расстояние до которой меньше, чем δ, она непременно должна лежать в прямоугольнике
со сторонами δ на 2δ:



Но в таком прямоугольнике может уместиться не более шести точек, иначе расстояние
между ними станет меньше δ и возникнет противоречие.

Тогда достаточно для каждой точки рассмотреть 6 следующих ее соседей в отсортированном
по y массиве.

Время работы T[n]=2T[n/2]+O(n)=O(nlogn) по основной теореме о рекуррентных соотношениях.

Реализация на python

При каком условии равносторонний треугольник можно поместить в квадрат?

#алгоритм #геометрия

Пусть есть квадрат со стороной a и равносторонний треугольник со стороной b.

Представим квадрат как некую дырочную область на земле в которую могут опускаться
плоские формы (равносторонний треугольник в нашем случае).

При каком условии можно в него поместить этот треугольник?

Правила вписывания абсолютно любые, треугольник при этом можно поворачивать и перемещать
как угодно в пространстве.
    

Ответы

Ответ 1

При каком условии можно в него поместить этот треугольник ?


(a * sqrt(2)) >= (b * sqrt(3) / 2), 

где

a * sqrt(2) - диагональ квадрата - максимальная проекция квадрата как отрезка,

b * sqrt(3) / 2 - высота треугольника - минимальная проекция треугольника как отрезка.


Ответ 2

Задача просто вписать треугольник в квадрат на плоскости все-таки чуть интереснее,
хотя и школьная геометрия та же.

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


Ответ 3

Если считать, что плоский треугольник это призма с высотой 1 точка (просто про высоту
плоских фигур в задаче ничего не сказано) то треугольник влезет в "дырочную область"
при условии если высота треугольника меньше диагонали квадратного сечения.

(a * sqrt(2)) > (b * sqrt(3) / 2)


А если эти значения будут равны, то треугольник уже не влезет. Это я вам как инженер
говорю.


Ответ 4

Если необходимо, чтобы все углы треугольника лежали на разных сторонах квадрата,
то равносторонний треугольник получится вписать в квадрат только при соблюдении соотношений
сторон:
a<=b<=a/0.9659
Если же допустить возможность, что 2 стороны треугольника будут "лежать" на сторонах
квадрата, то главное условие - b<=a/0.9659

Вычитание векторов в полярной системе координат

#математика #геометрия

Есть два вектора A и B, заданные длиной и углом (от 0 до 360 градусов). Нужно найти
угол вектора C, который получился в результате разницы векторов A и B.

Я пытался. Но уверен что это принципиально неверно. 

Vector Computing::lateralDem(Vector v1, Vector v2) {
    double z = pow(v1.value, 2) + pow(v2.value, 2) - 2 * v1.value*v2.value*cos(v1.angle
+ PI - v2.angle); // --длина(по теореме косинусов)
    double c = asin(sin(v1.angle + PI - v2.angle) * v2.value / z) - v1.angle; //
--угол(по теореме синусов)
    return{ c,sqrt(z) };
}

    

Ответы

Ответ 1

Vector Computing::Subtract(Vector v1, Vector v2) {
  // calculates new vector as (v2 - v1)

  double a1 = v1.angle * PI / 180;
  double a2 = v2.angle * PI / 180;

  double x1 = v1.value * cos(a1);
  double y1 = v1.value * sin(a1);
  double x2 = v2.value * cos(a2);
  double y2 = v2.value * sin(a2);

  double x3 = x2 - x1;
  double y3 = y2 - y1;

  double value3 = sqrt(x3*x3 + y3*y3);
  double angle3 = atan2(y3, x3);

  return { value = value3, angle = angle3 / PI * 180 };
}


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

v1 = { 0, 100 };
v2 = { 180, 100 };

v3 = v2 - v1 = { 180, 200 };


Что касается отрицательных углов, диапазон значений, возвращаемых функцией atan2,
- от -PI до PI. Если Вам нужны значения от нуля до 2PI, просто прибавьте PI к отрицательному
результату.


Ответ 2

Переход в декартову систему, вычитание, переход в полярную



Думаю, далее понятно, как посчитать угол?

Как повернуть треугольник?

#математика #android #java #геометрия

Рисую на Canvas равнобедренный треугольник посередине экрана. Рисую от центра треугольника
(места пересечения медиан). Соответственно, известны экранные координаты центра треугольника
и размер треугольника. Нужно иметь возможность поворачивать треугольник на произвольный
(рандомный) угол по часовой стрелке. Делаю так:
// Исходные данные
float angle = 90; // Угол на который будем поворачивать треугольник
final float height = 60; // Высота треугольника
final float width = 36; // Ширина треугольника
float centerX = 540; // Координаты центра треугольника на экране
float centerY = 960;

// Вычисляем экранные координаты всех вершин до поворота
// l1, l2, l3 - это расстояние от центра треугольника до вершины
// это расстояние вычисляю по формуле √ ((X2-X1)²+(Y2-Y1)²)
float x1 = centerX;
float y1 = centerY - height / 2;
float l1 = (float) Math.sqrt(Math.pow(centerX - x1, 2) + Math.pow(centerY - y1, 2));
float x2 = centerX + width / 2;
float y2 = centerY + height / 2;
float l2 = (float) Math.sqrt(Math.pow(centerX - x2, 2) + Math.pow(centerY - y2, 2));
float x3 = centerX - width / 2;
float y3 = y2;
float l3 = l2;

// Вычисляем координаты вершин с учетом поворота треугольника
float alpha1 = (float) (Math.atan(y1 / x1) - angle);
x1 = (float) (centerX + l1 * Math.cos(alpha1));
y1 = (float) (centerY + l1 * Math.sin(alpha1));

float alpha2 = (float) (Math.atan(y2 / x2) - angle);
x2 = (float) (centerX + l2 * Math.cos(alpha2));
y2 = (float) (centerY + l2 * Math.sin(alpha2));

float alpha3 = (float) (Math.atan(y3 / x3) - angle);
x3 = (float) (centerX + l3 * Math.cos(alpha3));
y3 = (float) (centerY + l3 * Math.sin(alpha3));

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

Ответы

Ответ 1

Поворот вокруг начальной точки на угол A, описываемый формулой:
Xn = Xc * cos(A) - Yc * sin(A)
Yn = Xc * sin(A) + Yc * cos(A)

где Xc, Yc - координаты относительно центра поворота; Xn, Yn - новые координаты.
Все что остается перейти к новой системе координат с нулевой точкой в центре треугольника
выполнить поворот и потом вернуться к старой системе координат.
Переход к новой системе координат выполняет по формуле:
Xn = X - Ox
Yn = Y - Oy

Т.е. для Вашего случая получаем для каждой точки нужно сделать преобразования:
x1 = (x1 - centerX) * cos(angle) - (y1 - centerY) * sin(angle) + centerX;
y1 = (x1 - centerX) * sin(angle) + (y1 - centerY) * cos(angle) + centerY;

Для больших подробностей откуда такие формулы и т.д. погуглите тему аффинные преобразования.


Ответ 2

Вы неверно вычисляете координаты поворота. Посмотрите на формулу (19) поворота осей здесь
Ну и кроме того как верно сказал @Nofate ♦ - у вас неверно заданы углы. Надо задавать
в радианах: angle*Math.PI/180


Ответ 3

Вы учитываете, что тригонометрические функции в java.lang.Math оперируют радианами,
а не градусами?
Чтобы не мучиться - задавайте исходные координаты относительно нуля.
Затем поворачивайте:

xNew = x*cos(angle) - y*sin(angle)
yNew = x*sin(angle) + x*cos(angle)

И потом позиционируйте относительно центра экрана.

Как найти точки пересечения лучей с погрешностью

#математика #геометрия

Есть несколько (конкретно 6) лучей в пространстве. Не имеет значения как они заданы
(я подгоню входные данные под решение, если нужно). Нужно найти точки, в которых пересекаются
3 луча за раз с заданной погрешностью (то есть 3 луча за раз скорее всего не пересекутся,
но будут близки к этому).
    

Ответы

Ответ 1

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

При этом самый простой вариант такой:

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

А дальше уже либо работаете с этой тройкой точек, либо вычисляете некую среднюю точку.

Построить полигоны слева и справа от ломаной

#cpp #алгоритм #геометрия

У меня есть некоторая ломаная на плоскости, необходимо слева и справа от нее построить
два многоугольника на заданных расстояниях.

Например:

Пусть задана красным цветом ломаная, относительно нее необходимо отстроить левый
и правый полигон А и В. Таким образом, полигоны А и В как бы стыкуются в заданной ломаной.
Для построения полигонов, с сохранением кривизны ломаной, задаются два расстояния,
для левой и правой частей.



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

Ограничения исходных данных: 
1) Ломаная без самопересечений 
2) Ломаная не может быть загнута, т.е. например на одном значении оси X или Y лежит
строго одна точка

Пишу на c++

Подкиньте идею)
    

Ответы

Ответ 1

Допустим, имеются точки C = [(x1, y1), (x2, y2), ..., (xn, yn)] - это ломаная.

Отрезок (x1, y1) - (xn, yn) соединяет первую и последнюю точки. Сделаем из него вектор
направления ломаной v:

(vx, vy) = (xn - x1, yn - y1)

И повернём на 90 градусов:

               | 0  -1 |
d = (vx, vy) * |       | =  (-vy, vx)
               | 1   0 |


Это вектор с абы какой длиной, повернутый перпендикулярно "направлению" ломаной.
Тут будет куча нюансов, но о них позже. Пока нормализуем (приведём к длине 1):

vL = sqrt(vx*vx + vy*vy)
dN = d / vL = (-vy / vL, vx / vL)


Собственно, теперь, имея расстояния, на которые надо отступить "слева" и "справа"
(p, q), смешаем каждую точку и получаем новые ломаные:

 L= C + dN * p = [(x1 + dN.x * p, y1 + dN.y * p), ...]
 R= C - dN * q = [(x1 - dN.x * q, y1 - dN.y * q), ...]


Для замыкания их на оригинальную ломаную, добавить оригинальные точки в перевёрнутом
порядке, иначе при отрисовке будут странные диагонали:

 M1 = [L1, L2, ..., Ln, Cn, Cn-1, ... C1]
 M2 = [R1, R2, ..., Rn, Cn, Cn-1, ... C1]


Теперь нюансы.


"Лево" и "право" очень относительные понятия, зависят от порядка точек в исходной
ломаной. Если они заданы по проекции на плоскость, возможно, их придётся перевернуть.
Возможны ситуации, когда смещённая ломаная пересечётся с оригинальной, либо будет
невозможно соединить прямыми начальные и конечные точки с оригинальной ломаной, чтобы
получить непересекающийся полигон.


Пример второй ситуации:


Красная при перемещении налезла на оригинальную; с зелёной не удаётся сделать полигон
без пересечений.

Алгоритм нарезки прямоугольника на равные меньшие прямоугольники

#алгоритм #геометрия

Дан исходный прямоугольник N×M.
Задача: определить сколько раз можно полностью "уложить" (ориентация любая) меньший
прямоугольник n×m в исходный.
Возможно, для будущих ходоков будет интересно КАК.
Спасибо.    

Ответы

Ответ 1

Чистая эвристика: сделал модель с простым перебором на JS. В очередную точку пробует
поставить блок гор. или верт. Есть вариант с приоритетом вертикального положения, есть
с приоритетом горизонтального. 

Добавил случайность: каждый раз с вероятностью 50% выбирается приоритет гор. или
вертикального расположения очередного блока. С откатом на оставшийся вариант, если
«приоритетный» не влезает.

Забавно: наблюдаю, что с «хаосом» иногда получаются результаты лучшие, чем когда
выбран определённый вариант приоритета. Т.е. оптимум лежит в более сложном алгоритме.

Для размера «гаража» 320x278 и «машины» 12x56 я пока поймал максимум в 125:


P.s. потыкав и понаблюдав расстановки, интуитивно понял, что надо начинать из углов,
двигаясь к центру. Если кому не лень форкнуть и разобраться, дайте знать. Может, конкурс
устроить? Битву алгоритмов : )   Все пишут свои варианты. В назначенный день объявляем
конкурсный размер гаража и машины, и смотрим, кто найдёт максимум за меньшее время.


Ответ 2

Задачка решается просто.
Если нужен ответ на вопрос КАК
// Возвращает массив расположения блоков [ { x, y, w, h } ]
function calc(W, H, w, h) {

    var hor = pack([], W, H, w, h, 0, 0);
    var ver = pack([], W, H, h, w, 0, 0);

    // сортировка блоков в порядке сверху-вниз, слева-направо
    // если не планируется нумеровать блоки - можно удалить
    return (hor.length >= ver.length ? hor : ver).sort(function(a, b) {
        return (a.y - b.y) || (a.x - b.x);
    });

    function pack(pieces, W, H, w, h, x0, y0) {
        var x, y;
        var nx = W / w | 0;  // число блоков, умещающееся по ширине
        var ny = H / h | 0;  // по высоте
        var n = nx * ny;     // всего
        for (y = 0; y < ny; y++) for (x = 0; x < nx; x++) {
            pieces.push({ x: x0 + x*w, y: y0 + y*h, w: w, h: h });
        }
        if (W % w >= h && H >= w) {  // осталось полезное место справа
            pack(pieces, W % w, H, h, w, x0 + nx*w, 0);
        } else if (H % h >= w && W >= h) {  // осталось полезное место снизу
            pack(pieces, W, H % h, h, w, 0, y0 + ny*h);
        }
        return pieces;
    }

}

Если нужен ответ на вопрос СКОЛЬКО
// Возвращает число блоков
function calc(W, H, w, h) {

    return Math.max(pack(W, H, w, h), pack(W, H, h, w));

    function pack(W, H, w, h) {
        var n = (W / w | 0) * (H / h | 0);
        if (W % w >= h && H >= w) {
            n += pack(W % w, H, h, w);
        } else if (H % h >= w && W >= h) {
            n += pack(W, H % h, h, w);
        }
        return n;
    }

}

Демо: http://jsfiddle.net/RHq23/