Как нарисовать многоугольник на основе случайных точек на холсте

Сегодня, когда я изучал книгу «Основы анимации HTML5+Javascript», в третьем разделе главы 8 я рассказывал о том, как использовать три пружины для соединения трех точек для выполнения растягивающих движений.

Закончив пример, я подумал, а что, если бы это было четыре балла или пять баллов.

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

Поэтому я задумался о том, можно ли оптимизировать эту область.

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

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

Затем соедините эти точки по углу от малого к большому, чтобы получился нормальный многоугольник.

Примерный код реализации выглядит следующим образом:

 let balls = [];let ballNum = 6;let firstBall = null; while(ballNum--) { let ball = new Ball(20, parseColor(Math.random() * 0xffffff)) ball.x = Math.random( ) * width; ball.y = Math.random() * height; balls.push(ball) if (!firstBall) { firstBall = ball ball.angle = 0 } else { const dx = ball.x - firstBall.x, dy = ball.y - firstBall.y; ball.angle = Math.atan2(dy, dx }}// Попробуем сделать линию, соединяющую шары, правильным многоугольником balls; = шары .sort((ballA, ballB) => { return ballA.angle - ballB.angle})

Таким образом, когда соединение наконец будет нарисовано, угол можно будет нарисовать от меньшего к большему, пересекая массив.

Эффект следующий:

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

Далее я хочу попытаться оптимизировать это решение. Например, использовать Math.abs для исправления угла или найти точку с наименьшим углом для соединения каждой точки. Но результат нехороший, пересечения линий не избежать.

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

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

Но если у меня есть эти точки, я уже могу нарисовать многоугольник. Пришлось отказаться

В отчаянии мне пришлось поискать в Google, а затем я нашел хороший ответ на Zhihu: Как соединить группу неупорядоченных точек на плоскости в простой многоугольник?

Подробное описание алгоритма можно найти в ответе, и я не буду вдаваться в подробности.

Однако при соединении верхней цепи и нижней цепи вам нужно только следить за тем, чтобы верхняя цепь соединялась в порядке убывания по оси X, а нижняя цепь - в порядке возрастания по оси X (нарисовано в направлении против часовой стрелки). . Что касается точек с одинаковой осью X, то не имеет значения, больше или меньше ось Y.

При реализации он реализуется строго по алгоритму в ответе.

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

Примерный код выглядит следующим образом:

 let balls = [];let tempBalls = [];let ballNum = 6;let isDragingBall = false; while(ballNum--) { let ball = new Ball(10, parseColor(Math.random() * 0xffffff)) ball. x = Math.random() * ширина; ball.y = Math.random() * высота; tempBalls.push(ball)}// Пусть точки отсортированы по возрастанию на tempBalls.length -1];let smallXBalls = tempBalls.filter(ball => ball.x === firstBall.x), bigXBalls = tempBalls.filter(ball => ball.x === LastBall.x)// Обрабатываем ситуацию, когда имеется несколько левых и правых полюсов if (smallXBalls.length > 1) { smallXBalls.sort((ballA, ballB) => { return ballB.y - ballA.y })}if (bigXBalls.length > 1) { bigXBalls.sort((ballA, ballB) => { return ballB.y - ballA.y })}firstBall = smallXBalls[0]lastBall = bigXBalls[0]//Получить угол соединения опоры let SplitLineAngle = Math.atan2(lastBall.y - firstBall.y,lastBall.x - firstBall.x);let UpperBalls = [], LowerBalls = [];//Все остальные точки вычисляют углы с помощью firstBall// Все, что больше, чем SplitLineAngle, находится в нижней цепочке // Остальные — в верхней цепочке tempBalls.forEach(ball => { if (ball === firstBall || ball === LastBall) { return false } let angular = Math.atan2(ball.y - firstBall.y, ball.x - firstBall.x); if (angle > SplitLineAngle) { lowBalls.push(ball) } else { UpperBalls.push(ball) }})// Обрабатываем сортировку одной и той же ситуации по оси X lowBalls = lowBalls.sort((ballA, ballB) => { if (ballA.x !== ballB.x) { return ballA.x - ballB.x } return ballB.y - ballA.y})upperBalls = UpperBalls.sort((ballA, ballB) => { if (ballA.x !== ballB.x) { return ballB.x - ballA.x } return ballB.y - ballB.x})// Соединяем все точки против часовой стрелки balls = [firstBall].concat(lowerBalls, [lastBall], UpperBalls)balls = balls. map((ball, i) => { ball.text = i + 1; вернуть мяч})

Наконец возвращенные шары представляют собой точки многоугольника, отсортированные против часовой стрелки.

Эффект следующий:

Внутреннее состояние каждого шара следующее:

Выше приведено все содержание этой статьи. Я надеюсь, что она будет полезна для изучения всеми. Я также надеюсь, что все поддержат сеть VeVb Wulin.