2차원 평면에서 임의의 점을 모두 연결하는 다각형 폐곡면을 그리는 코드 (N 가능)

임의의 150개 점에 대해 : 소요 시간 0.001초

import pygame, sys

from pygame.locals import *

import time

import random

import numpy as np

import matplotlib.pyplot as plt

import math

def points_draw(points, N):

    c_x = 0

    c_y = 0

    for i in range(len(points)):

        x0 = points[i][0]

        y0 = points[i][1]

        c_x += x0

        c_y += y0

    cc_x = int(c_x/N)

    cc_y = int(c_x/N)

    angle = []

    for j in range(len(points)):

        x0 = points[j][0]

        y0 = points[j][1]

        dx = cc_x - x0

        dy = cc_y - y0

        angle.append(math.atan2(dy, dx))

        pygame.draw.circle(screen, '#FF0000', [x0, y0], 3)

    temp = []

    for tt in angle:

        temp.append(tt)

    angle.sort()

    ind = []

    for ang in angle:

        ind.append(temp.index(ang))

    for j in range(len(ind)):

        if j < N-1:

            x0 = points[ind[j]][0]

            y0 = points[ind[j]][1]

            x1 = points[ind[j+1]][0]

            y1 = points[ind[j+1]][1]

        elif j >= N-1:

            print(j)

            x0 = points[ind[j]][0]

            y0 = points[ind[j]][1]

            x1 = points[ind[0]][0]

            y1 = points[ind[0]][1]

        pygame.draw.line(screen, '#00FF00', [x0, y0], [x1, y1], 1)

    pygame.draw.circle(screen, '#FFFFFF', [cc_x, cc_y], 3)

    return angle

pygame.init()

dis_width = 600

dis_height = 600

N = 150

screen = pygame.display.set_mode((dis_width, dis_height))

pygame.display.set_caption(str(N)+' points Simulation')

font = pygame.font.Font("C:\Windows\Fonts\HYSANB.ttf", 20)

FPS = 0.1

clock = pygame.time.Clock()

dis_min = 600*600

cou = 0

while True: # the main game loop

    screen.fill('#000000')

    for event in pygame.event.get():

        if event.type == QUIT:

            pygame.quit()

            sys.exit()

    points = []

    for i in range(N):

        x = random.randint(5, 595)

        y = random.randint(5, 595)

        points.append((x, y))

    angle = points_draw(points, N)

    pygame.display.update()

    clock.tick(FPS)

   

pygame.quit()

 

N	소요 시간 (sec)
150	0.001 ~ 0.0012
1500	0.0154 ~ 0.0225
15000	0.882 ~ 0.9877

임의의 15000개의 점에 대해 :