Ответы пользователя по тегу Геометрия
  • Каким алгоритмом или формулой можно выяснить, находится ли точка между паралельными прямыми?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Вычисляете (a1*x + b1*y + c1)*(a2*x + b2*y + c2). Если у него знак такой же, как у a1*a2+b1*b2, то точка принадлежит тупому углу между прямыми, если другой - то острому. В случае параллельных или почти параллельных прямых второй случай соответствует ситуации "лежит между", а первый - "нет".
    Ответ написан
    1 комментарий
  • Как спроецировать фигуру на плоскость?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Чтобы найти точку "в плоскости", вам нужно задать в ней систему координат. То есть, выбрать точку начала координат O(x0,y0,z0) и два базисных вектора X=(x1,y1,z1) и Y=(x2,y2,z2). Судя по тому, что вы говорите про "декартову систему координат", векторы должны быть единичной длины и перпендикулярны друг другу.
    Добавляете к системе вектор Z, параллельно которому идёт проектирование. Из условия непонятно, рассматриваете вы только ортогональную проекцию, или общий случай параллельной проекции.
    В случае ортогональной всё просто - не нужно даже возиться с матрицами:
    вектор Z вычисляется как векторное произведение X и Y, но он нам не нужен вообще: если проектируемая точка P имеет координаты (x,y,z), то её проекция Q будет иметь координаты (в системе координат плоскости)
    x'=(P-O,X)=(x-x0)*x1+(y-y0)*y1+(z-z0)*z1
    y'=(P-O,Y)=(x-x0)*x2+(y-y0)*y2+(z-z0)*z2.
    В случае косоугольной проекции вычисления сложнее - надо умножать вектор (P-O) на матрицу, обратную к матрице, составленной из X,Y,Z. И там главное не запутаться, где строки, а где столбцы.
    Ответ написан
  • Как найти вероятность того, что точка находится от центра на расстоянии меньшем r?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    1. Найти площадь области, содержащей все точки, находящиеся от центра на расстоянии, меньшем r
    2. Понять, чему равна вероятность того, что точка попадёт в круг радиуса R
    3. Найти площадь круга радиуса R
    4. Воспользоваться тем, что вероятности пропорциональны площадям.

    Просто интересно, какой из этих пунктов вообще может вызвать затруднения.
    Ответ написан
    Комментировать
  • Как найти расстояние от центра до стороны повернутого прямоугольника?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если его повернули на угол a, то
    A1=min(A/abs(cos(a)),B/abs(sin(a))),
    B1=min(B/abs(cos(a)),A/abs(sin(a))).
    Если приходится делить на 0, то результат деления считается равным бесконечности, а значение минимума - второму числу.
    Ответ написан
    1 комментарий
  • Нахождение общей площади, образованной объединением прямоугольников?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Довольно просто решить за O(N^3).
    Пусть координаты k-го прямоугольника - (x1[k],x2[k],y1[k],y2[k]).
    Берёте все x1,x2 (их 2*N штук), сортируете, выкидываете одинаковые. Это проекции вершин на ось X. Обозначим полученный массив A.
    Аналогично с y1,y2 - получается массив B (тоже длиной не больше 2*N).
    Теперь перебираем прямоугольники C=[A[p],A[p+1]]*[B[q],B[q+1]] для всех p,q. Ни один из них не пересекается сторонами исходных прямоугольников, так что если центр C лежит в одном из исходных прямоугольников, то весь прямоугольник принадлежит объединению, если нет - то не имеет с ним общих внутренних точек. Суммируем площади всех прямоугольников, принадлежащих объединению, и пишем ответ.
    Можно соптимизировать до O(N^2). Насчёт O(N*log(N)) не знаю.
    Ответ написан
    6 комментариев
  • Как определить пересечение отрезка и полигона?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала лучше перейти в систему координат, в которой стороны прямоугольника параллельны координатным осям, а центр - в точке (0,0): пусть при преобразовании (x,y) -> (p*x+q*y+r,-q*x+p*y+s) прямоугольник переходит в abs(X) <= A, abs(Y) <= B.
    Пусть (X1,Y1) и (X2,Y2) - координаты вершин отрезка после преобразования.
    Если max(X1,X2) < -A || min(X1,X2) > A || max(Y1,Y2) < -B || min(Y1,Y2) > B, то не пересекается: отрезок находится за одной из сторон прямоугольника.
    В противном случае условием пересечения, насколько я понимаю, будет
    abs(X1*Y2-Y1*X2) <= abs(A*(Y2-Y1)) + abs(B*(X2-X1))
    Тщательно не проверял, но шансы, что формула правильная, хорошие.
    Ответ написан
    Комментировать
  • Как правильно вычислять географические расстояния в высоконагруженных сервисах?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Может быть, вычислять расстояние только до пользователей, которые находятся в этом или смежных квадратах? Можно ограничиться 4 квадратами - расположенными вокруг вершины, ближайшей к пользователю.
    Ответ написан
    Комментировать
  • Как ускорить алгоритм?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Сначала учитываем 3*N^2 треугольников, у которых вершина с прямым углом лежит на одной из координатных осей (или вообще в точке (0,0)).
    Теперь посчитаем все остальные треугольники.
    Пусть (a,b) - координаты вершины с прямым углом, 0 < a <= N, 0 < b <= N.
    Если c=НОД(a,b), a1=a/c, b1=b/c, то оставшаяся вершина должна иметь координаты (x,y)=(a+t*b1,b-t*a1), где t - ненулевое целое число.
    Должны выполняться условия 0 <= x,y <= N. Перепишем их в виде условий на t:
    -a/b1 <= t <= (N-a)/b1, -(N-b)/a1 <= t <= b/a1 (заметим, что a1, b1 больше нуля, так что делить можно). Учитывая, что t должно быть целым, оно лежит на отрезке от
    t0 = -floor(min(a/b1,(N-b)/a1))
    до
    t1 = floor(min((N-a)/b1,b/a1))
    И, поскольку запрещённое значение 0 всегда принадлежит этому отрезку, получаем, что число треугольников с вершиной (a,b) равно t1-t0.
    Перебираем все точки (a,b), считаем t1-t0 и суммируем.
    Всё. Сложность N^2*log(N), основное время тратится на вычисление НОД.
    Если надо быстрее - надо будет думать. Скорее всего, надо будет перебирать взаимно простые пары (a1,b1), считать, сколько точек попало в перекошенный квадрат (переведённый в базис (a1,b1), (-b1,a1)), искать для них формулу и суммировать. Может быть, получится, может быть, нет. Какого порядка N?
    Ответ написан
    Комментировать
  • Как описать квадратом окружность, имея координаты точки и радиус?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Так и не решили? Интересная задачка.
    Предположим, что Земля шарообразная и её радиус RE. Радиус нашей окружности R, координаты точки выражены в радианах.
    Определим r=R/RE (это радиус в радианах).
    Расстояние от центра окружности до вершины описанного квадрата - a=arctg(sqrt(2)*tg(r)) (под квадратом понимается правильный сферический 4-угольник?)
    Теперь нам надо отступить от нашей точки на расстояние a под углом 45 гр к меридиану.
    Пусть P - северный полюс, O - центр окружности, A - вершина квадрата на северо-востоке.
    У треугольника AOP длина стороны OP=pi/2-Lat, AO=a, угол POA=pi/4. Отсюда, по 1-й теореме косинусов,
    AP=arccos(cos(AO)*cos(OP)+sin(AO)*sin(OP)*cos(AOP))=arccos(cos(a)*sin(Lat)+sqrt(0.5)*sin(a)*cos(Lat)). Получаем h1=pi/2-AP - широта точки A.
    Угол APO найдём по теореме синусов: sin(APO)/sin(AO)=sin(AOP)/sin(AP), откуда APO=d1=arcsin(sin(a)*sqrt(0.5)/cos(h1)). Долгота точки A будет Lon+d1, а координаты северо-западной вершины D - (h1,Lon-d1).
    С южными вершинами поступаем аналогично (только там угол будет 135 гр):
    BP=arccos(cos(a)*sin(Lat-sqrt(0.5)*sin(a)*cos(Lat)), h2=pi/2-BP.
    BPO=d2=arcsin(sin(a)*sqrt(0.5)/cos(h2)).
    Координаты точек B и C - (h2,Lon+d2) и (h2,Lon-d2).
    Если надо учитывать сплюснутость Земли, или под квадратом понималось нечто иное, то нужны более конкретные условия.
    Кстати, если радиус окружности будет больше четверти экватора, то вершины описанного квадрата окажутся внутри круга. Такая уж сферическая геометрия.
    Ответ написан
    Комментировать
  • Как построить задачу поиска оптимальной точки?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Я бы её решал как точку пересечения трёх сфер в пространстве с последующей проекцией на плоскость ABC, а потом на поверхность Земли:
    Пусть радиусы равны RA, RB, RC, а расстояния между точками - AB,AC,BC.
    Вычислим величины
    u=((RA^2-RB^2)/AB^2+1)/2
    v=((RA^2-RC^2)/AC^2+1)/2
    Это будут проекции точки пересечения сфер на отрезки AB и AC, выраженные в длинах этих отрезков.
    Пусть a - угол в вершине А треугольника АВС (найдём по теореме косинусов).
    Если Q - проекция точки пересечения сфер на плоскость ABC, то
    AQ=(AB*(u-v*cos(a))+AC*(v-u*cos(a)))/(sin(a)^2),
    т.е. Q=A*(1-(u+v)/(1+cos(a)))+B*((u-v*cos(a))/sin(a)^2)+C*((v-u*cos(a))/sin(a)^2),
    где A,B,C - трёхмерные координаты точек. Тогда Q*(R/|OQ|) - искомая точка (|OQ| - расстояние от Q до центра Земли, R - радиус Земли).
    Формулы не проверялись :(
    Ответ написан
    Комментировать
  • Знаете ли вы хороший сервис по изучению математики?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Игра в Евклида почему-то закрылась. Есть вот такой задачник: sciencevsmagic.net/geo/# но он, судя по всему, не о том. Но если поискать "interactive geometry problems", то много чего выдаёт, можно покопаться в результатах.
    Ответ написан
    1 комментарий
  • Как сгенерировать окружности на сфере, что бы они оптимально перекрывали друг-друга?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Это известная проблема. Пока её решили до 10 кругов и ещё для некоторых чётных значений. Впрочем, всё это сведения 25-летней давности, свежих результатов найти не удаётся. Вот статья, где разбирается построение для 11 кругов (правда, я её не читал, и не знаю, есть ли там окончательное решение для этого случая):
    https://eudml.org/doc/141375
    Или у вас задача - "дан радиус сферы и радиус круга, найти минимальное число кругов"? Или можно задать примерный радиус (или примерное число кругов) и найти какое-нибудь решение, близкое к оптимальному, для этого случая?
    В общем, сейчас задача упирается в вопрос "а зачем?". Если нужно точное решение для написания докторской диссертации - то решайте. Если есть какая-нибудь практическая цель - напишите, какая, и будем искать реалистичные приближения.

    UPD. В общем, берёте икосаэдр, и каждую грань делите на маленькие правильные треугольники. Вершины этих треугольников и дадут центры кругов. Радиус придётся считать исходя из картинки вблизи вершины икосаэдра - там треугольники заметно искажаются. Возможно, радиальное расстояние между точками там придётся слегка уменьшить.
    Ответ написан
    7 комментариев
  • Зачем нужны однородные координаты?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    По большому счёту, однородные координаты нужны с единственной целью - чтобы при получении экранных координат точки не нужно было различать ортогональную и перспективную проекции. В остальных ситуациях их полная поддержка была бы только лишней тратой ресурсов.
    Сразу надо сказать, что матрицей 3*3 вы не обойдётесь. Такие матрицы описывают только поворот, а в перемещениях объекта и камеры в 3D есть ещё сдвиги. Поэтому нужна матрица, по меньшей мере, 3*4 (в конвенции компьютерной графики, когда вектор это строка а не столбец).
    В терминах линейной алгебры пользоваться такими матрицами неудобно, поэтому к ним добавляют столбец (0,0,0,1), а к координатам точки - четвёртую координату 1. Де-факто мы при этом получаем проективное пространство, представленное однородными координатами. Но при любых операциях над матрицами и точками у нас последний столбец всегда будет (0,0,0,1), а последняя координата точки - 1.
    Если знать это, то можно хорошо сэкономить: для хранения матрицы хватит 12 чисел вместо 16, для перемножения двух матриц - 36 умножений вместо 64, а для умножения матрицы на точку - 9 умножений вместо 16. Надеюсь, что в реальных проектах так и делают.
    Но есть одно место, где последний столбец не равен (0,0,0,1), и четвёртая координата точки может отличаться от 1 - это перспективная матрица для вывода на экран (ссылку вам уже дали). Для вывода точки (x,y,z) результат её применения может быть, условно, (x,y,z,1) - тогда имеет место ортогональная проекция, и выведется точка (x,y), а может - (x,y,-1,z) - тогда координаты точки окажутся (x/z,y/z), и проекция будет перспективной. Хватило бы одного бита - как интерпретировать точку, делить ли на z. Но разработчики компьютерной графики решили, что матрица 4*4 и однородные координаты - это более эффективно. Им виднее.
    Ответ написан
    1 комментарий
  • Как найти положение камеры по трем точкам в пространстве?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Непростая задача.
    Сначала по фотографии измеряете углы между лучами, а по модели - расстояния между точками. Потом обозначаете через x,y,z неизвестные расстояния от камеры до точек (длину каждого луча), и записываете уравнения из теоремы косинусов:
    x^2-2*a*x*y+y^2=P^2
    x^2-2*b*x*z+z^2=Q^2
    y^2-2*c*y*z+z^2=R^2
    Здесь a,b,c - косинусы углов между лучами, а P,Q,R - расстояния.
    Дальше надо решить эту систему. Теоретически, она сводится к уравнению 8-й степени от одной переменной z. MAPLE смог найти этот многочлен, он занимает чуть больше экрана. Не знаю, хороший ли это вариант - может быть, и да. Можно попытаться решить систему численно - перебрать разные стартовые значения x,y,z и искать корень методом Ньютона. Но учтите, что система плохая - у неё вполне могут найтись 4 близких корня с положительными x,y,z. А могут и не найтись - тогда будут локальные минимумы. Можно перебрать расстояние x с мелким шагом. Для каждого x найти два варианта y, два варианта z, подставить их в третье уравнение, и из самой лучшей тройки начать искать решение - можно методом Ньютона, но можно и делением отрезка пополам.
    После того, как x,y,z найдены, находите положение центра камеры - как точку пересечения трёх сфер. И дальше надо найти правильную ориентацию. Это довольно противно, но должно быть не очень сложно (по сравнению со всеми предыдущими шагами).
    Ответ написан
  • Правильно ли я понял суть кватернионов?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Обычно берут кватернионы длины 1, т.е. x^2+y^2+z^2+w^2=1.
    Поворот на нулевой угол задаётся кватернионом (0,0,0,1) - направление оси (x,y,z) для него не определено, да и не нужно.
    В остальных случаях угол поворота определяется значением w по формуле
    w=cos(phi/2), где 0 <= phi <= 2*pi. То есть, чем больше угол поворота, тем меньше w. Для поворотов на 180 градусов w=0.
    Если w<0, то поворот получается на угол, больший 180 гр. Угол поворота отсчитывается против часовой стрелки, если смотреть в сторону (x,y,z). Получается, что кватернионы (x,y,z,w) и (-x,-y,-z,-w) задают один и тот же угол поворота.
    Почему так сделано - не очень важно. Главное, что суперпозиция двух последовательных поворотов описывается кватернионом, равным произведению кватернионов самих этих поворотов (в каком-то определённом порядке).
    Ответ написан
    3 комментария
  • Как найти длину перпендикуляра с точки на отрезок?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    double L=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    double PR=(x-x1)*(x2-x1)+(y-y1)*(y2-y1);
    bool res=true;
    double cf=PR/L;
    if(cf<0){ cf=0; res=false; }
    if(cf>1){ cf=1; res=false; }
    double xres=x1+cf*(x2-x1);
    double yres=y1+cf*(y2-y1);

    В (xres,yres) будут координаты ближайшей точки отрезка, а переменная res покажет, перпендикуляр получился, или нет.
    Ответ написан
  • Как повернуть уравнение плоскости относительно точки?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    повернуть уравнение плоскости на угол Y U W (относительно осей ox, oy, oz)

    - что имеется в виду? Повернуть плоскость на угол Y относительно ox, потом на U относительно oy, и потом на W относительно oz?
    Предположим, что так.
    Первым делом, надо сдвинуть систему координат так, чтобы точка M оказалась началом координат:
    x=x1+MX, y=y1+MY, z=z1+MZ. Уравнение плоскости в этой системе будет A*x1+B*y1+C*z1+(D+A*MX+B*MY+C*MZ)=0.
    Теперь выполним поворот относительно оси Ox: A1=A, B1=B*cos(Y)+C*sin(Y), C1=-B*sin(Y)+C*cos(Y). Свободный член в уравнении не изменится (расстояние до начала координат и длина вектора нормали не изменились), получилось уравнение A1*x+B1*y+C1*z+D1=0 (где D1=D+A*MX+B*MY+C*MZ). Аналогично выполняем повороты относительно Oy и Oz. Получится уравнение A3*x+B3*y+C3*z+D1=0. Осталось сдвинуть систему координат обратно, чтобы начало координат перешло в точку M: A3*x+B3*y+C3*z+(D1-A3*MX-B3*MY-C3*MZ)=0. Это есть ответ. Надо только убедиться, что повороты идут в правильные стороны.
    Ответ написан
    Комментировать
  • Как определить кривизну линии?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если надо проверить среднее отклонение от прямой, то можно посчитать матрицу ковариации:
    xm=sum(x[i])/N; ym=sum(y[i])/N;
    a=sum((x[i]-xm)^2); b=sum((x[i]-xm)*(y[i]-ym)); c=sum((y[i]-y0)^2);
    и посчитать отношение собственных значений:
    R=(a+c-sqrt((a-c)^2+4*b^2)/(a+c+sqrt((a-c)^2+4*b^2).
    Если R достаточно мало (скажем, меньше 0.01), то считаем, что это прямая.

    Если надо проверить, прямая это или дуга, то берём крайние точки (x0,y0) и (xn,yn). Пусть dx=xn-x0,dy=yn-y0.
    Считаем для всех точек
    z[i]=((x[i]-x0)*dx+(y[i]-y0)*dy)/sqrt(dx^2+dy^2), w[i]=((x[i]-x0)*dy-(y[i]-y0)*dx)/sqrt(dx^2+dy^2),
    Теперь приближаем зависимость w(z) параболой (по методу наименьших квадратов): w=A*z^2+B*z+C. Величина A пропорциональна кривизне дуги, по которой идут точки.
    Ответ написан
    Комментировать
  • Как кластеризовать точки по принадлежности к разным (неизвестным) прямым?

    Mrrl
    @Mrrl
    Заводчик кардиганов
    Если времени не очень жалко, можно попробовать так:
    Перебираем углы от 0 до 180 с шагом, например, 1 градус.
    Проектируем точки на прямую, идущую под этим углом к горизонтали.
    Ищем на проекции достаточно короткий отрезок, в который попало достаточно много точек.
    Ищем методом наименьших квадратов прямую, наилучшим образом приближающую точки, попавшие в этот отрезок.

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

    Первая часть алгоритма не опробована. В сущности, это то же преобразование Хафа, но разделённое на этапы. Вторую применял неоднократно.
    Ответ написан
  • Проективное преобразование (поиск относительного положения точки)

    Mrrl
    @Mrrl
    Заводчик кардиганов
    А можете для какого-нибудь примера написать полученные прямую и обратную матрицы? Например, для A=M, B=N, D=K, C=(2,2) ?
    Ответ написан