Совместный проект , коммерческий продукт руками участников форума

[prografix]

Вроде здесь много всяких разных специалистов, поэтому у меня появилась идея объединиться и сделать какую-то программу, которую потом можно будет продавать. Что именно делать я не знаю, но думаю, что найдутся люди, которые знают, что и кому можно продать.
Например, кто-то имеет идею, но одному её реализовать нереально, а если группой - то можно.
Недавно некоторые участники форума собирались в Москве ( я потом пожалел, что не присоединился ). Не знаю, что они там обсуждали, но можно было бы обсудить какие-то проекты.

[Nirvanko]

Цитата prografix @ 19.03.17, 10:21

Вроде здесь много всяких разных специалистов, поэтому у меня появилась идея объединиться и сделать какую-то программу, которую потом можно будет продавать. Что именно делать я не знаю, но думаю, что найдутся люди, которые знают, что и кому можно продать.
Например, кто-то имеет идею, но одному её реализовать нереально, а если группой - то можно.
Недавно некоторые участники форума собирались в Москве ( я потом пожалел, что не присоединился ). Не знаю, что они там обсуждали, но можно было бы обсудить какие-то проекты.

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

Перспективна разработка мобильных приложений. Что-нибудь утилитарное, с использованием геолокации.

[prografix]

Есть такая задача. Дан многогранник с большим количеством граней. Для начала будем считать, что они треугольные. Нужно найти похожий на него многогранник с меньшим количеством граней.
Тут можно предложить несколько точных формулировок:
1) Найти многогранник с наименьшим количеством граней такой, чтобы расстояние между поверхностями многогранников не превышало заданную величину.
2) Найти многогранник с заданным количеством граней такой, чтобы расстояние между поверхностями многогранников было минимальным.
3) Что-то ещё.
У меня есть некоторые идеи, как это можно сделать, но вначале я хочу посмотреть какие будут другие предложения по реализации этой задачи.

[OpenGL]

Неужели эта задача не решалась раньше? Вроде же упрощение моделей везде применяется. Или там просто какие-то эвристические алгоритмы используются, а надо точные?

[prografix]

Эта задача решалась. Есть коммерческие продукты. Например, Simplygon шведской фирмы Donya Labs, у которой потом этот продукт купила Microsoft.
Понятно, что никто не будет делиться информацией о том, что можно продать.
Упрощать можно по-разному, поэтому я интересуюсь какие будут идеи.

[MBo]

А идеи, похожие на Рамера-Дугласа-Пекера, к многогранникам нельзя применить? (понятно, что стянуть грани и сочленить их несравненно сложнее, чем отрезки)

https://gis.stackexchange.com/questions/534...for-3d-topology

[prografix]

У меня другой подход: наоборот, постепенно упрощать исходной многогранник.

[prografix]

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

[MIF]

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

Сообщение отредактировано: MIF - 23.05.17, 23:11

[amk]

Теорема Пифагора тут не поможет.
Но по мне так проще по формуле Герона найти площадь треугольника, а зная площадь, нет проблем найти и все высоты.
По крайней мере меньше умножений/делений приходится выполнять.

[prografix]

Изначально я решал задачу - найти расстояние от точки до треугольника в пространстве.
Первое, что пришло в голову - это вычислить его через вектора. А потом я обнаружил, что квадрат расстояния можно вычислить через квадраты расстояний между точками. Их 6 штук ( 3 между сторонами треугольника и 3 от вершин до точки ). Сейчас расписываю формулы. Возможно, с вычислительной точки зрения так будет быстрее.

[amk]

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

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

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

Жаль до конца не получилось довести.

[prografix]

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

// Функция 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 - 28.06.17, 08:07

[ter_nk_]

Написали вирус атаковал популярные месседжеры. Давайте напишем непопулярный месседжер.