Задача. Реализовать алгоритм красивого рисования графа с рёбрами - отрезками.
Для рисования используйте HTML5 Canvas:
Что можно сделать с помощью HTML5 Canvas?
Выполняйте задание мелкими шагами. После каждого шага что-то должно работать.
Задание 1. Рисование графа с заданными позициями вершин (10 баллов)
Создайте страницу с элементом <canvas>, нарисуйте на канве круг.
Попробуйте добиться, чтобы круг был маленьким и залит синим цветом.
Напишите функцию draw_circle(x, y), которая рисует круг с центром в точке (x, y). Вызовите эту функцию три раза, чтобы протестировать.
Напишите функцию draw_segment(x1, y1, x2, y2), которая рисует отрезок из точки (x1, y1) в точку (x2, y2). Вызовите эту функцию для пары точек, чтобы протестировать.
Выберите простой граф (5-10 вершин). Выберите способ хранения графа. Задайте граф в коде в переменной graph.
Выберите начальные положения каждой вершины, задайте их в коде в переменной coords.
Напишите функцию draw_graph(graph, coords), которая рисует граф, располагая вершины в точках coords. Протестируйте её.
Задание 2. Подбор оптимальных позиций вершин (20 баллов)
Если граф сложный, то может быть неочевидно, как следует расположить его вершины, чтобы он лучше всего смотрелся. Для этого можно применять разные подходы.
Первый подход - физический (force-based graph layout). Будем считать, что все вершины отталкиваются друг от друга с силой, обратно пропорциональной квадрату расстояния между ними. Также примем, что каждое ребро стремится стянуть два своих конца по закону Гука. Таким образом, для любого расположения вершин для каждой вершины можно посчитать векторную сумму всех действующих на неё сил. Для подбора оптимальных позиций вершин можно итеративно смещать каждую вершины вдоль этой суммы. Картинка графа будет постепенно улучшаться.
Второй подход состоит в том, чтобы перебирать случайные расположения вершин на плоскости и для каждого расположения считать функцию "хорошести" расположения. "Хорошесть" должна оценивать красоту графа. Формула "хорошести" может включать в себя: минимальную длину ребра, максимальную длину ребра, углы между рёбрами, расстояния между вершинами. Перебираем 100-1000 вариантов случайного расположения вершин и показываем пользователю вариант с максимальной "хорошестью".
Задайте в коде сложный граф (15-100 вершин).
Напишите функцию init_coords(n), которая расставляет вершины графа либо по окружности, либо случайным образом в некотором прямоугольнике.
Реализуйте один из двух подходов к подбору оптимальных позиций вершин.
Код своего решения выложите на JSFiddle или CodePen.
Пример с урока: анимация через <canvas>.