Оптимизация перебора поверхностей, составленных из треугольников

Извиняюсь, не ту букву в склейку вписал, не так посчиталось. Да, есть плоскость. Она же без края )
x(F)=1 K=0 m=1.0 [[A B C], [A B D], [A C E], [A D F], [B C F], [B E F], [C D E], [A E F], [B D E], [C D F]]

Оптимизация перебора поверхностей, составленных из треугольников

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

Например
[[A B C], [A B D], [A C D]]
это тетраэдр без дна, он по идее гомеоморфен диску. То есть BCD то «виден», но лишь чисто визуально, он не участвует в склейке.
А вот
[[A B C], [A B D], [A C D], [B C D]] уже можно сказать что сфера

Оптимизация перебора поверхностей, составленных из треугольников

Теперь начал понимать. Нарисовал ленту мебиуса в виде графа треугольников, получилось обычное кольцо. Так что да, для каждого графа надо еще генерить кучу склеек

Оптимизация перебора поверхностей, составленных из треугольников

Хотя, у ленты мебиуса такие же характеристики, так что хз

Оптимизация перебора поверхностей, составленных из треугольников

Когда забил в прогу триангуляцию из википедии, получилось
x(F)=0 K=1 m=1.0 [[A D C], [D C B], [B F A], [A F C], [B E A], [A E D], [B D F], [C E F], [E F D]]

И таких среди десяток несколько есть

x(F)=0 K=1 m=1.0 [[A B C], [A B D], [A C E], [A D F], [B C G], [B G H], [C E I], [D F J], [F G H], [F G J]]
x(F)=0 K=1 m=1.0 [[A B C], [A B D], [A C E], [A D F], [B C G], [B G H], [D F H], [D H I], [G H I], [G I J]]

и даже среди девяток

x(F)=0 K=1 m=1.0 [[A B C], [A B D], [A C D], [B C E], [B D E], [C D F], [C E G], [D F G], [E F G]]

Оптимизация перебора поверхностей, составленных из треугольников

Мне не надо «рисовать» склейки, мне достаточно их перечислить в том виде, что я привел в топике.

То есть, берем любую вершину графа Петерсена, обзываем её ABC. Три ребра, AB BC AC
AB отдаем направо, BC налево, AC внутрь

Берем треугольник слева, две вершины у него мы уже знаем, BC. Приписываем D и «повторяй всё сначала»
Потом, после того как построили склейку, посчитали Эйлерову характеристику, число компонент края и готово. Не уж то не так? Может я объяснил неправильно?

Оптимизация перебора поверхностей, составленных из треугольников

Охохонюшки, спасибо за инфу

Löb и möb: странные петли в Хаскеле

Почему-то вспомнилось «Мозг сам дал себе название»

Оптимизация перебора поверхностей, составленных из треугольников

а разве не по любому графу с валентностью <= 3 можно построить валидную склейку? В смысле, что пёс с ней с постройкой, мы все хорошие графы найдем, а склейки «по определению» можно будет построить, не без геммора конечно

Оптимизация перебора поверхностей, составленных из треугольников

Все сойдут, там разберутся. Я очень хотел доперебирать до тора из 14ти и бутылки клейна из 16ти, но видать не судьба. А насчет строить склейку — да, есть у меня под рукой работа, где девочка ручками строила эти склейки для пяти треугольников и там не всё так очевидно. Но, почему то казалось, что эта задача не такая сложная

Оптимизация перебора поверхностей, составленных из треугольников

В общем, в результате копаний нашел такую штуку: oeis.org/A000088
Если генерить неориентированные графы (а способ есть, это описано тут: en.wikipedia.org/wiki/Pólya_enumeration_theorem) то можно выбирать из них только те, что имеют валентность не больше трех, строить склейки и смотреть что за поверхность получится. Походу, способа быстрее не будет.
Единственный момент — я голову сломал читать описание алгоритма, к нужному сроку я его точно не успею сделать

Оптимизация перебора поверхностей, составленных из треугольников

Вообще да, есть такой подход типа вершины графа это треугольники, а рёбра — соединения треугольников по ребру. Но как тогда перебирать связные графы?

Оптимизация перебора поверхностей, составленных из треугольников

то есть, «склейка» из трех треугольников будет представлена как граф из трёх вершин?

Вечный торт: интервью с Денисом Крючковым, основателем Хабрахабра

Скажем так, за серьезную алгоритмическую статью автор редко получает больше одного-двух плюсов в карму. В отличие от топиков типа «Смарите как я в стиле матрицы обои себе забабахал на балконе». Карма штука эмоциональная, она оценивает всё что угодно кроме объективной ценности топика и его создателя

Что Java 8 нам готовит

дайте структуры и unsigned! в топку эти лямбды. А еще честные дженерики, а не этих уродцев

DES на J в сотню строк

#define er1(k) (rotr(2*x[(r-1)%xw]^x[(r+1)%xw]^k^r,8)*9^k)
 enRUPT (u32 *x, const u32 xw, u32 *key, const u32 kw)
{
    u32 r, s=4, n=s*(2*xw+kw);
    for (r=1; r<=n; r++) x[r%xw] ^= er1(key[r%kw]);
}
 unRUPT (u32 *x, const u32 xw, u32 *key, const u32 kw)
{
    u32 r, s=4, n=s*(2*xw+kw);
    for (r=n; r   ; r--) x[r%xw] ^= er1(key[r%kw]);
}

EnRupt в 11 строчек вместе с расшифровкой

Печенье от Ватсона

А E235, E458 они в него заложили?

Смартфон от РЖД: расставляем точки над i

[удалено, т.к. не читал комментарии ниже]

Смартфон от РЖД: расставляем точки над i

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

Смартфон от РЖД: расставляем точки над i

Я правильно понимаю, это первый проект в истории новой России, на котором не распилили ни копейки?