На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
  
> Совместный проект , коммерческий продукт руками участников форума
    Вроде здесь много всяких разных специалистов, поэтому у меня появилась идея объединиться и сделать какую-то программу, которую потом можно будет продавать. Что именно делать я не знаю, но думаю, что найдутся люди, которые знают, что и кому можно продать.
    Например, кто-то имеет идею, но одному её реализовать нереально, а если группой - то можно.
    Недавно некоторые участники форума собирались в Москве ( я потом пожалел, что не присоединился ). Не знаю, что они там обсуждали, но можно было бы обсудить какие-то проекты.
      Цитата prografix @
      Вроде здесь много всяких разных специалистов, поэтому у меня появилась идея объединиться и сделать какую-то программу, которую потом можно будет продавать. Что именно делать я не знаю, но думаю, что найдутся люди, которые знают, что и кому можно продать.
      Например, кто-то имеет идею, но одному её реализовать нереально, а если группой - то можно.
      Недавно некоторые участники форума собирались в Москве ( я потом пожалел, что не присоединился ). Не знаю, что они там обсуждали, но можно было бы обсудить какие-то проекты.

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

      Перспективна разработка мобильных приложений. Что-нибудь утилитарное, с использованием геолокации.
        Есть такая задача. Дан многогранник с большим количеством граней. Для начала будем считать, что они треугольные. Нужно найти похожий на него многогранник с меньшим количеством граней.
        Тут можно предложить несколько точных формулировок:
        1) Найти многогранник с наименьшим количеством граней такой, чтобы расстояние между поверхностями многогранников не превышало заданную величину.
        2) Найти многогранник с заданным количеством граней такой, чтобы расстояние между поверхностями многогранников было минимальным.
        3) Что-то ещё.
        У меня есть некоторые идеи, как это можно сделать, но вначале я хочу посмотреть какие будут другие предложения по реализации этой задачи.
          Неужели эта задача не решалась раньше? Вроде же упрощение моделей везде применяется. Или там просто какие-то эвристические алгоритмы используются, а надо точные?
            Эта задача решалась. Есть коммерческие продукты. Например, Simplygon шведской фирмы Donya Labs, у которой потом этот продукт купила Microsoft.
            Понятно, что никто не будет делиться информацией о том, что можно продать.
            Упрощать можно по-разному, поэтому я интересуюсь какие будут идеи.
              А идеи, похожие на Рамера-Дугласа-Пекера, к многогранникам нельзя применить? (понятно, что стянуть грани и сочленить их несравненно сложнее, чем отрезки)

              https://gis.stackexchange.com/questions/534...for-3d-topology
                У меня другой подход: наоборот, постепенно упрощать исходной многогранник.
                  В ходе работы над упрощением многогранника я вывел формулу, в которой квадрат высоты треугольника выражается через квадраты сторон при помощи только арифметических операций.
                  Этот факт мне настолько понравился, что я записал эту формулу в википедию.
                    По ссылке не пошел. Кажется, формулу, связывающую квадраты сторон прямоугольного треугольника, Пифагор вывел.
                    Сообщение отредактировано: MIF -
                      Теорема Пифагора тут не поможет.
                      Но по мне так проще по формуле Герона найти площадь треугольника, а зная площадь, нет проблем найти и все высоты.
                      По крайней мере меньше умножений/делений приходится выполнять.
                        Изначально я решал задачу - найти расстояние от точки до треугольника в пространстве.
                        Первое, что пришло в голову - это вычислить его через вектора. А потом я обнаружил, что квадрат расстояния можно вычислить через квадраты расстояний между точками. Их 6 штук ( 3 между сторонами треугольника и 3 от вершин до точки ). Сейчас расписываю формулы. Возможно, с вычислительной точки зрения так будет быстрее.
                          Посмотрел твою формулу высоты треугольника (думаю): именно она получается, если найденную по формуле Герона площадь поделить на половину основания (возведя в квадрат естественно).

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

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

                          Жаль до конца не получилось довести.
                            В итоге у меня получился такой алгоритм для вычисления квадрата расстояния от точки до треугольника:
                            ExpandedWrap disabled
                              // Функция getDistance2Edge вычисляет квадрат расстояния от точки до ребра треугольника
                               
                              bool getDistance2Edge ( double a, double b, double c, double & d )
                              {
                                  // Проверим попадает ли проекция точки на ребро?
                                  const double t = fabs ( b - c );
                                  if ( t >= a ) return false;
                                  // Вычислим квадрат расстояния до ребра
                                  d = b + c - 0.5 * ( a + t * t / a );
                                  if ( d > 0 )
                                      d *= 0.5;
                                  else
                                      d = 0;
                                  return true;
                              }
                               
                              double getDistance2Facet ( double a, double b, double c, double d, double e, double f, double q )
                              {
                                  // Вычислим скалярные произведения
                                  const double p1 = 0.5 * ( a + c - b );
                                  const double p2 = 0.5 * ( d + a - e );
                                  const double p3 = 0.5 * ( c + d - f );
                                  // Проверим попадает ли проекция точки внутрь треугольника?
                                  const double g = a * p3 - p1 * p2;
                                  if ( g <= 0 ) return q;
                                  // Если треугольник - вырожденный, то вернём квадрат расстояния до ребра
                                  const double h = a * c - p1 * p1;
                                  if ( h <= 0 ) return q;
                                  const double gg = g * g;
                                  const double ah = a * h;
                                  if ( 4 * gg * c >= ah * h ) return q;
                                  // Вычислим квадрат расстояния до плоскости треугольника
                                  q -= gg / ah;
                                  return q < 0 ? 0 : q;
                              }
                               
                              double getDistance2Triangle ( double ab, double bc, double ca, double ap, double bp, double cp )
                              {
                                  double d = _min ( ap, bp, cp );
                                  if ( ! d ) return 0;
                                  // Вычислим квадраты расстояний до рёбер треугольника
                                  double d1, d2, d3;
                                  nat edge = 0; // номер ближайшего к точке ребра
                                  nat count = 0; // количество рёбер на которые есть проекция точки
                                  if ( getDistance2Edge ( ab, ap, bp, d1 ) )
                                  {
                                      if ( d > d1 ) d = d1, edge = 1;
                                      ++count;
                                  }
                                  if ( getDistance2Edge ( bc, bp, cp, d2 ) )
                                  {
                                      if ( d > d2 ) d = d2, edge = 2;
                                      ++count;
                                  }
                                  if ( getDistance2Edge ( ca, cp, ap, d3 ) )
                                  {
                                      if ( d > d3 ) d = d3, edge = 3;
                                      ++count;
                                  }
                                  if ( ! d ) return 0;
                                  // Если точка проецируется хотя бы на 2 ребра треугольника
                                  if ( count > 1 )
                                  {
                                      switch ( edge )
                                      {
                                      case 1: return getDistance2Facet ( ab, bc, ca, ap, bp, cp, d );
                                      case 2: return getDistance2Facet ( bc, ca, ab, bp, cp, ap, d );
                                      case 3: return getDistance2Facet ( ca, ab, bc, cp, ap, bp, d );
                                      }
                                  }
                                  return d;
                              }
                               
                              double getDistance2 ( const Triangle3d & t, const Vector3d & p )
                              {
                                  // Вычислим квадраты расстояний до вершин треугольника
                                  const double ap = qmod ( t.a - p );
                                  const double bp = qmod ( t.b - p );
                                  const double cp = qmod ( t.c - p );
                                  // Вычислим квадраты расстояний между вершинами треугольника
                                  const double ab = qmod ( t.a - t.b );
                                  const double bc = qmod ( t.b - t.c );
                                  const double ca = qmod ( t.c - t.a );
                                  // Основной алгоритм
                                  return getDistance2Triangle ( ab, bc, ca, ap, bp, cp );
                              }

                            Причём класс Triangle3d можно заменить на треугольник в пространстве другой размерности. Можно было сделать класс-шаблон, но я не стал, т.к. другие размерности меня пока не интересуют.
                            11.06.2017 я обнаружил и исправил ошибку в этом алгоритме.
                            Сообщение отредактировано: prografix -
                              Написали вирус атаковал популярные месседжеры. Давайте напишем непопулярный месседжер.
                              0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                              0 пользователей:


                              Рейтинг@Mail.ru
                              [ Script execution time: 0,0448 ]   [ 15 queries used ]   [ Generated: 19.03.24, 08:19 GMT ]