[МишаИнженер]

Очень интересно ознакомиться с алгоритмами триангуляции Делоне на Basic. Если кто может поделиться опытом или дать ссылку на материалы в Интернете поделитесь пожалуйста!

[Лиспер]

http://www.google.ru/search?source=i...D0%BC&aq=0&oq= и переводи на тот язык, который нужен...

[МишаИнженер]

Скачал недавно программу вместе с кодом, которая строит триангуляцию контура из точек с помощью треугольников. Точки задаются нажатием левой кнопки мыши. А если нажимать правую кнопку мыши то будут указываться точки которые или лежат внутри контура или снаружи. Наружние точки окрашиваются в красный цвет, внутренние в коричневый.
Так вот надо бы както вывести на экран те треугольники которые программа создаёт в результате триангуляции. Это раз. Затем мне хочется понять: алгоритм триангуляции сделан в стандартной библиотеке Windows или этот алгоритм разработал автор программы самостоятельно?
В общем хочется всё что делает эта программа перенести на экран AutoCAD и желательно с использованием кода Basica. Хочется чтобы эта программа создавала триангуляционную сетку на экране AutoCAD! Поэтому у меня вопрос: код триангуляции стандартный и взят из библиотеки Windows или это разработка автора? И где находится этот код?
Посмотрите программу и её код в архивном файле

[Александр Ривилис]

Сообщение от МишаИнженер Поэтому у меня вопрос: код триангуляции стандартный и взят из библиотеки Windows или это разработка автора? И где находится этот код?

В библиотеке Windows нет кода для триангуляции. В приведенном коде программа работает только с треугольниками, вершины которых опредлены как целые числа. Алгоритм не анализировал. Он находится в файле win32.cpp, функция triangulation. Я бы на твоем месте поискал алгоритмы триангуляции Делоне.
Посмотри здесь: http://paulbourke.net/papers/triangulate/

[МишаИнженер]

Спасибо Александр!
На сайте нашёл описание алгоритма триангуляции:

Код:

[Выделить все]

subroutine triangulate
input : vertex list
output : triangle list
   initialize the triangle list
   determine the supertriangle
   add supertriangle vertices to the end of the vertex list
   add the supertriangle to the triangle list
   for each sample point in the vertex list
      initialize the edge buffer
      for each triangle currently in the triangle list
         calculate the triangle circumcircle center and radius
         if the point lies in the triangle circumcircle then
            add the three triangle edges to the edge buffer
            remove the triangle from the triangle list
         endif
      endfor
      delete all doubly specified edges from the edge buffer
         this leaves the edges of the enclosing polygon only
      add to the triangle list all triangles formed between the point 
         and the edges of the enclosing polygon
   endfor
   remove any triangles from the triangle list that use the supertriangle vertices
   remove the supertriangle vertices from the vertex list
end

И попробовал перевести этот алгоритм на русский язык:

Код:

[Выделить все]

треугольная подпрограмма
вход: список вершины
продукция: список треугольника
   калибруйте список треугольника
   определите супертреугольник
   добавьте вершины супертреугольника до конца списка вершины
   добавьте супертреугольник к списку треугольника
   для каждого типового пункта в списке вершины
      калибруйте буфер края
      для каждого треугольника в настоящее время в списке треугольника
         вычислите треугольник circumcircle центр и радиус
         если пункт находится в треугольнике circumcircle тогда
            добавьте три края треугольника к буферу края
            удалите треугольник из списка треугольника
         endif
      endfor
      удалите все вдвойне указанные края из буфера края
         это оставляет края многоугольника приложения только
      добавьте к списку треугольника все треугольники, сформированные между пунктом 
         и края многоугольника приложения
   endfor
   удалите любые треугольники из списка треугольника, которые используют вершины супертреугольника
   удалите вершины супертреугольника из списка вершины
конец

Что такое супертреугольник? Можно ли более понятно перевести этот алгоритм?

[AlexV]

треугольная подпрограмма - в этом что-то есть!
"каким был бы программный код, если бы Билл Гейтц сотоварищи жили и творили в России"
Интересно, а чего endif с endfor не превратилися в "конецесли" с "конецдля"?

[Александр Ривилис]

МишаИнженер, посмотри здесь на странице 32. И пользуйся поиском.
И чем тебя не устроили готовые алгоритмы на VB, ссылку на которые я привел?

[МишаИнженер]

Спасибо Александр!
На сайте который Вы мне посоветовали нашёл код на Basice и скопировал его в VBA!
Получилась програмка триангуляции Делонэ
Но вот почему иногда появляются перекрывающиеся треугольники?
С самого начала появлялась ошибка в следующем коде:

Код:

[Выделить все]

xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2)

Если знаменатель (m1 - m2) становился равным 0
Чтобы избежать частого появления ошибок изменил код на следующий:

Код:

[Выделить все]

'Спорный код в программе
   If (m1 - m2) <> 0 Then
      xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2)
   Else
'Неизвестно почему может из-за этой строки иногда появляются перекрывающиеся треугольники
      xc = (m1 * mx1 - m2 * mx2 + my2 - my1)
   End If

Помогите разобраться почему появляются перекрывающиеся треугольники!
Модуль DVB посмотрите в прикреплённом файле

[Александр Ривилис]

Михаил. Я не пишу на VB/VBA, а разбираться с чужим алгоритмом на VBA у меня нет возможности. Прошу прощения. В любом случае проверка

Код:

[Выделить все]

If (m1 - m2) <> 0 Then

мне не нравится. Проверять IMHO следует абсолютную величину и не с нулём, а с каким-нибудь достаточно малым числом. Например, с 0.000001
Т.е. что-то такое:

Код:

[Выделить все]

If Abs(m1 - m2) > 0.000001 Then

P.S. Всё же немного поглядел на код. Во первых все координаты в целых числах (Long). Их явно нужно поменять на плавающие (Double). Потом не обрабатывается (попросту не учитывается) координата Z. В результате треугольники плоские. Ну а смотреть на имена функций/переменных написанных русскими буквами я просто не могу без слёз.

[МишаИнженер]

Спасибо Александр!
Учёл Ваши замечания насчёт Long, изменил на Double!
Сделал новый алгоритм вычисления центра описанной окружности.
Программа стала работать значительно лучше!
Можете сами убедиться по картинке триангуляции прямоугольника. Все треугольники поляризованы и гипотенузы во всех треугольниках параллельны!
Но правда если взять всего два таких треугольника и сначала поделить их на 4 одинаковых то затем никак не получается поделить эти одинаковых 4 треугольника на более мелкие!
Попробуйте может у кого получится.
Самое интересное почему это не получается. Кто может разобраться?