Comment dessiner un polygone basé sur des points aléatoires dans le canevas

Aujourd'hui, alors que j'étudiais le livre "HTML5+Javascript Animation Basics", dans la troisième section du chapitre 8, j'ai expliqué comment utiliser trois ressorts pour relier trois points afin d'effectuer des mouvements d'étirement.

Après avoir terminé l'exemple, j'ai réfléchi à ce qui se passerait si c'était quatre ou cinq points.

J'ai réécrit le code et rendu le nombre de points variable. L'effet final est de réaliser le mouvement d'étirement final de chaque point pour équilibrer, mais les connexions entre les points ne sont pas très belles, et certaines sont croisées.

Je me demandais donc si cette zone pouvait être optimisée.

Les points de l’exemple précédent sont tous situés à des positions aléatoires, les connexions sont donc incontrôlables. Je veux donc commencer par cela en premier.

Tout d’abord, utilisez un certain point comme point de référence pour obtenir les angles d’autres points par rapport à ce point.

Reliez ensuite ces points selon l'angle du petit au grand, afin de pouvoir dessiner un polygone normal.

Le code d'implémentation approximatif est le suivant :

 let ballNum = [];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; balles.push(ball) if (!firstBall) { firstBall = balle ball.angle = 0 } else { const dx = ball.x - firstBall.x, dy = ball.y - firstBall.y; ball.angle = Math.atan2(dy, dx }}// Essayez de faire de la ligne reliant les boules un polygone régulier = balles .sort((ballA, ballB) => { return ballA.angle - ballB.angle})

De cette façon, lorsque la connexion est finalement tracée, l'angle peut être tracé de petit à grand en parcourant le réseau.

L'effet est le suivant :

Cela peut réduire considérablement le nombre de lignes qui se croisent, mais cela ne peut toujours pas être complètement évité.

Ensuite, je veux essayer d'optimiser cette solution. Par exemple, utiliser Math.abs pour corriger l'angle ou trouver le point avec le plus petit angle pour relier chaque point. Mais le résultat n’est pas bon, il est impossible d’éviter de franchir les lignes.

Ensuite, une autre idée m'est venue à l'esprit. Si le point central du polygone peut être déterminé, alors les angles de tous les points par rapport au point central peuvent être calculés séparément et ces points peuvent être connectés dans le sens des aiguilles d'une montre ou dans le sens inverse.

Cependant, après une longue recherche sur Internet, tous les algorithmes de points nécessitent une série de points disposés dans un certain ordre dans le sens des aiguilles d'une montre.

Mais si j'ai ces points, je peux déjà dessiner le polygone. J'ai dû abandonner

En désespoir de cause, j'ai dû chercher sur Google, puis j'ai trouvé une bonne réponse sur Zhihu : Comment connecter un groupe de points désordonnés sur le plan en un simple polygone ?

Pour la description spécifique de l'algorithme, regardez simplement la réponse et je n'entrerai pas dans les détails.

Cependant, lors de la connexion de la chaîne supérieure et de la chaîne inférieure, il vous suffit de vous assurer que la chaîne supérieure est connectée dans l'ordre décroissant sur l'axe X et que la chaîne inférieure est connectée dans l'ordre croissant sur l'axe X (dessinée dans le sens inverse des aiguilles d'une montre). . Quant aux points ayant le même axe X, peu importe que l’axe Y soit plus grand ou plus petit.

Une fois implémenté, il est implémenté strictement selon l'algorithme de la réponse.

Pour juger si un point appartient à la chaîne supérieure ou à la chaîne inférieure, l'idée initiale est de déterminer l'équation fonctionnelle de la droite basée sur deux points, puis d'introduire les coordonnées des points pour le calcul. Mais plus tard, j'ai pensé que tous les points utilisaient le pôle le plus à gauche pour calculer l'angle oblique, puis le divisons en fonction de la taille de l'angle, ce qui est plus facile à comprendre visuellement.

Le code approximatif est le suivant :

 let balles = [];let tempBalls = [];let ballNum = 6;let isDragingBall = false;while(ballNum--) { let ball = new Ball(10, parseColor(Math.random() * 0xffffff)) balle. x = Math.random() * largeur; balle.y = Math.random() * hauteur; Laissez les points être triés par ordre croissant sur tempBalls.length -1]; laissez smallXBalls = tempBalls.filter(ball => ball.x === firstBall.x), bigXBalls = tempBalls.filter(ball => ball.x === lastBall.x)// Gérer la situation où il y a plusieurs pôles gauche et droit 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]//Obtenir l'angle de la connexion des pôles let splitLineAngle = Math.atan2(lastBall.y - firstBall.y, lastBall.x - firstBall.x);let upperBalls = [], lowerBalls = [];//Tous les autres points calculent les angles avec firstBall// Tout ce qui est plus grand que splitLineAngle est en chaîne descendante // D'autres sont en chaîne supérieure 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) }})// Gérer le tri de la même situation sur l'axe X 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})// Connectez tous les points dans le sens inverse des aiguilles d'une montre balles = [firstBall].concat(lowerBalls, [lastBall], upperBalls)balls = balles. map((balle, i) => { ball.text = i + 1; return ball})

Les boules finalement renvoyées sont les points du polygone triés dans le sens inverse des aiguilles d'une montre.

L'effet est le suivant :

L'état interne de chaque boule est le suivant :

Ce qui précède représente l’intégralité du contenu de cet article. J’espère qu’il sera utile à l’étude de chacun. J’espère également que tout le monde soutiendra le réseau VeVb Wulin.