Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

Всем у кого не работает. файл wizard.script Ещё одно упоминание Glut32 в строке "if (!VerifyLibFile(dir_nomacro_lib, _T("glut32"), _T("GLUT's"))) return false;" меняем на "if (!VerifyLibFile(dir_nomacro_lib, _T("freeglut"), _T("GLUT's"))) return...
Не получается, емаё
огромное спасибо за подробное объяснение про 3д графику на питоне, в интернете очень мало подобной информации
dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?
Очень интересно! ии сайт крутой жалко что умирает(

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика

Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.

Алгоритм жадной триангуляции заключается в следующем:

  1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и сортируется по длине.
  2. Начиная с самого короткого, в триангуляцию последовательно вставляются отрезки из множества отсортированных по длине отрезков. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.

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

Алгоритм корректно работает как для множества точек на плоскости, так и для выпуклых многоугольников.

В случае с невыпуклым многоугольником алгоритм добавит несколько лишних отрезков снаружи.

Трудоемкость работы жадного алгоритма в среднем составляет ~O(N2logN), поэтому на практике он практически не применяется, однако является очень простым для понимания.