How to draw a polygon based on random points in canvas

Today when I was studying the book "HTML5+Javascript Animation Basics", in the third section of Chapter 8, I talked about how to use three springs to connect three points to perform stretching movements.

After finishing the example, I thought about what if it was four points or five points.

I rewrote the code and made the number of points variable. The final effect is to achieve the final stretching movement of each point to balance, but the connections between the points are not very good-looking, and some are crossed.

So I was thinking about whether this area could be optimized.

The points in the previous example are all at random positions, so the connections are uncontrollable. So I want to start with this first.

First, use a certain point as a reference point to obtain the angles of other points relative to this point.

Then connect these points according to the angle from small to large, so that you can draw a normal polygon.

The approximate implementation code is as follows:

 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); }}// Try to make the line connecting the balls a regular polygon balls = balls .sort((ballA, ballB) => { return ballA.angle - ballB.angle})

In this way, when the connection is finally drawn, the angle can be drawn from small to large by traversing the array.

The effect is as follows:

This can greatly reduce the number of crossing lines, but it still cannot be completely avoided.

Next, I want to try to optimize this solution. For example, use Math.abs to correct angle, or find the point with the smallest angle to connect each point. But the result is no good, crossing lines cannot be avoided.

Then another idea came to mind. If the center point of the polygon can be determined, then the angles of all points relative to the center point can be calculated separately, and these points can be connected clockwise or counterclockwise.

However, after searching for a long time on the Internet, all point algorithms require a series of points arranged in a certain clockwise order.

But if I have these points, I can already draw the polygon. Had to give up

In desperation, I had to search Google, and then I found a good answer on Zhihu: How to connect a group of disordered points on the plane into a simple polygon?

For the specific algorithm description, just look at the answer and I won’t go into details.

However, when connecting the upper chain and the lower chain, you only need to ensure that the upper chain is connected in descending order on the X axis and the lower chain is connected in ascending order on the X axis (drawn in a counterclockwise direction). As for the points with the same X axis, it doesn't matter whether the Y axis is larger or smaller.

When implemented, it is implemented strictly according to the algorithm in the answer.

When judging whether a point belongs to the upper chain or the lower chain, the initial idea is to determine the function equation of the straight line based on two points, and then introduce the coordinates of the points for calculation. But later I thought that all points use the leftmost pole to calculate the oblique angle, and then divide it according to the angle size, which is easier to understand visually.

The approximate code is as follows:

 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() * width; ball.y = Math.random() * height; tempBalls.push(ball)}// Let the points be sorted in ascending order on the tempBalls.length -1];let smallXBalls = tempBalls.filter(ball => ball.x === firstBall.x), bigXBalls = tempBalls.filter(ball => ball.x === lastBall.x)// Handle the situation where there are multiple left and right poles 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]//Get the angle of the pole connection let splitLineAngle = Math.atan2(lastBall.y - firstBall.y, lastBall.x - firstBall.x);let upperBalls = [], lowerBalls = [];//All other points calculate angles with firstBall// Anything larger than splitLineAngle is down chain // Others are up chain tempBalls.forEach(ball => { if (ball === firstBall || ball === lastBall) { return false } let angle = Math.atan2(ball.y - firstBall.y, ball.x - firstBall.x); if (angle > splitLineAngle) { lowerBalls.push(ball) } else { upperBalls.push(ball) }})// Handle the sorting of the same situation on the X axis lowerBalls = lowerBalls.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})// Connect all points counterclockwise balls = [firstBall].concat(lowerBalls, [lastBall], upperBalls)balls = balls.map((ball, i) => { ball.text = i + 1; return ball})

The balls finally returned are the polygon points sorted counterclockwise.

The effect is as follows:

The internal state of each ball is as follows:

The above is the entire content of this article. I hope it will be helpful to everyone’s study. I also hope everyone will support VeVb Wulin Network.