캔버스의 임의의 점을 기반으로 다각형을 그리는 방법

오늘은 "HTML5+Javascript Animation Basics" 책을 공부하던 중 8장 3절에서 3개의 스프링을 이용해 3개의 점을 연결하여 스트레칭 동작을 하는 방법에 대해 이야기했습니다.

예제를 마치고 4점이면 어떨까, 5점이면 어떨까 생각해봤습니다.

코드를 다시 작성하고 포인트 수를 가변적으로 만들었습니다. 최종 효과는 균형을 맞추기 위해 각 점의 최종 스트레칭 동작을 달성하는 것이지만 점 사이의 연결이 그다지 좋지 않고 일부가 교차됩니다.

그래서 이 부분을 최적화할 수 있을까 고민했어요.

이전 예의 점은 모두 임의의 위치에 있으므로 연결을 제어할 수 없습니다. 그래서 저는 먼저 이것부터 시작하고 싶습니다.

먼저 특정 점을 기준점으로 사용하여 이 점을 기준으로 다른 점의 각도를 구합니다.

그런 다음 작은 각도에서 큰 각도에 따라 이 점들을 연결하면 일반 다각형을 그릴 수 있습니다.

대략적인 구현 코드는 다음과 같습니다.

 letball = [];let ballNum = 6;let firstBall = null;while(ballNum--) { let ball = new Ball(20,parseColor(Math.random() * 0xffffff)) ball.x = Math.random( ) * 너비; ball.y = Math.random() * 높이;balls.push(ball) if (!firstBall) { firstBall = 공 ball.angle = 0 } else { const dx = ball.x - firstBall.x, dy = ball.y - firstBall.y; ball.angle = Math.atan2(dy, dx) }}// 공을 연결하는 선을 정다각형 공으로 만듭니다. = 공 .sort((ballA, ballB) => { ballA.angle 반환 - ballB.angle})

이런 식으로 최종적으로 연결이 그려지면 배열을 순회하면서 작은 각도에서 큰 각도로 그릴 수 있습니다.

효과는 다음과 같습니다.

이렇게 하면 교차하는 선의 수를 크게 줄일 수 있지만 여전히 완전히 피할 수는 없습니다.

다음으로, 이 솔루션을 최적화하려고 합니다. 예를 들어 Math.abs를 사용하여 각도를 수정하거나 각 점을 연결하는 가장 작은 각도의 점을 찾습니다. 하지만 결과는 좋지 않고, 선을 넘는 것도 피할 수 없습니다.

그러다가 또 다른 아이디어가 떠올랐습니다. 다각형의 중심점이 결정되면 중심점에 대한 모든 점의 각도를 개별적으로 계산할 수 있으며 이러한 점은 시계 방향 또는 시계 반대 방향으로 연결될 수 있습니다.

그러나 인터넷에서 오랜 시간 동안 검색한 결과 모든 포인트 알고리즘에는 특정 시계 방향 순서로 배열된 일련의 포인트가 필요합니다.

하지만 이러한 점이 있으면 이미 다각형을 그릴 수 있습니다. 포기해야 했어요

필사적으로 Google을 검색해야 했고 Zhihu에서 좋은 답을 찾았습니다. 평면의 무질서한 점 그룹을 간단한 다각형으로 연결하는 방법은 무엇입니까?

구체적인 알고리즘 설명은 답변만 살펴보시고 자세한 내용은 다루지 않겠습니다.

단, 상부체인과 하부체인을 연결할 때에는 상부체인이 X축을 기준으로 내림차순으로 연결되고, 하부체인이 X축을 기준으로 오름차순(반시계방향으로 그려짐)으로 연결되어 있는지만 확인하시면 됩니다. . X축이 동일한 점의 경우 Y축이 더 크거나 작은지는 중요하지 않습니다.

구현 시 답변에 나온 알고리즘에 따라 엄격하게 구현됩니다.

한 점이 상부 체인에 속하는지 하부 체인에 속하는지 판단할 때 초기 아이디어는 두 점을 기준으로 직선의 함수 방정식을 결정한 다음 계산을 위해 점의 좌표를 도입하는 것입니다. 그런데 나중에 생각해보니 모든 점은 가장 왼쪽 극을 이용해서 경사각을 계산한 뒤 이를 각도 크기에 따라 나누는 것이 시각적으로 이해하기 더 쉽더군요.

대략적인 코드는 다음과 같습니다.

 letballs = [];let tempBalls = [];let ballNum = 6;let isDragingBall = false;while(ballNum--) { let ball = new Ball(10,parseColor(Math.random() * 0xffffff)) 공. x = Math.random() * 너비; ball.y = Math.random() * tempBalls.push(ball)}// tempBalls.length -1]에서 점을 오름차순으로 정렬합니다. 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 angle = Math.atan2(ball.y - firstBall.y, ball.x - firstBall.x); if (angle > SplitLineAngle) { lowerBalls.push(ball) } else { upperBalls.push(ball) }})// 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})// 모든 점을 시계 반대 방향으로 연결합니다.ball = [firstBall].concat(lowerBalls, [lastBall], upperBalls)balls = 공. map((ball, i) => { ball.text = i + 1; 공 반환})

최종적으로 반환된 공은 시계 반대 방향으로 정렬된 다각형 점입니다.

효과는 다음과 같습니다.

각 공의 내부 상태는 다음과 같습니다.

위의 내용은 이 기사의 전체 내용입니다. 모든 분들의 학습에 도움이 되기를 바랍니다. 또한 모든 분들이 VeVb Wulin Network를 지지해 주시길 바랍니다.