I have a list of points (x,y). A line is drawn somewhere 'inside' these points (within the area they form). I have been trying different algorithms for ordering these points to create a polygon, with these constraints:
- The polygon is not self-intersecting.
- The resulting polygon is not necessarily convex; a convex hull will not suffice
- The polygon needs to go through all of the points. I have tried the
alphashapeconcave hull algorithm, but I was not able to get it to work (it ignored some points, and I wasn't sure what to tune thealphavalue to) - The resulting polygon will not intersect with the drawn line. I think this is relevant to remove a lot of the ambiguity for concave polygons
Some clarification for how the points are ordered: they roughly follow the profile of a contoured line, which is unknown and different from the drawn line. The drawn line will be intrinsically quite similar to this unspecified line however.
I have also tried the very simplistic angle sort algorithm, which unsurprisingly does not work. However, running the algorithm at differnt points along the line gave more promising results, but I am not sure how to use the data.
Above is a screenshot of the following test program I cobbled together:
import pygame import numpy as np from scipy.interpolate import splprep, splev import sys import random # Pygame setup pygame.init() screen = pygame.display.set_mode((1000, 1000)) pygame.display.set_caption("Smoothed Curve with Draggable Points") clock = pygame.time.Clock() # Colors WHITE = (255, 255, 255) BLUE = (0, 0, 255) RED = (255, 0, 0) GREEN = (0, 200, 0) BLACK = (0, 0, 0) drawing = False points = [] smoothed = [] normals = [] # Dot settings DOT_RADIUS = 6 DRAG_RADIUS = 10 # Dot class for draggable points class Dot: def __init__(self, pos): self.x, self.y = pos self.dragging = False def pos(self): return (int(self.x), int(self.y)) def is_mouse_over(self, mx, my): return (self.x - mx)**2 + (self.y - my)**2 <= DRAG_RADIUS**2 def start_drag(self): self.dragging = True def stop_drag(self): self.dragging = False def update_pos(self, mx, my): if self.dragging: self.x, self.y = mx, my # crude test arrangement of dots. random_dots = [Dot(tup) for tup in [(159, 459),(133, 193),(286, 481),(241, 345),(411, 404),(280, 349),(352, 471),(395, 361),(85, 390),(203, 321),(41, 281),(58, 348),(175, 275),(75, 185),(385, 443),(44, 219),(148, 229),(215, 477),(338, 339),(122, 430)]] def downsample(points, step=2): return points[::step] def smooth_curve(points, smoothness=150): if len(points) < 4: return [], [] points = downsample(points, step=2) x, y = zip(*points) try: tck, u = splprep([x, y], s=100.0, k=3) u_new = np.linspace(0, 1, smoothness) # Evaluate curve points x_vals, y_vals = splev(u_new, tck) # Derivatives: dx/du, dy/du dx_du, dy_du = splev(u_new, tck, der=1) gradients = np.array(dy_du) / np.array(dx_du) # dy/dx return list(zip(x_vals, y_vals)), list(zip(dx_du, dy_du)) except: return [], [] def draw_normals(screen, smoothed, derivatives, spacing=10, length=30): for i in range(0, len(smoothed), spacing): x, y = smoothed[i] dx, dy = derivatives[i] # Normal vector is (-dy, dx) nx, ny = -dy, dx norm = np.hypot(nx, ny) if norm == 0: continue nx /= norm ny /= norm x1 = x - nx * length / 2 y1 = y - ny * length / 2 x2 = x + nx * length / 2 y2 = y + ny * length / 2 pygame.draw.line(screen, GREEN, (x1, y1), (x2, y2), 2) def generate_random_dots(n=20, w=800, h=600): return [Dot((random.randint(0, w), random.randint(0, h))) for _ in range(n)] # Main loop dragged_dot = None running = True while running: screen.fill(WHITE) mx, my = pygame.mouse.get_pos() for event in pygame.event.get(): if event.type == pygame.QUIT: running = False elif event.type == pygame.MOUSEBUTTONDOWN: drawing = True points = [] smoothed = [] normals = [] # Check for draggable dot for dot in random_dots: if dot.is_mouse_over(mx, my): dragged_dot = dot dot.start_drag() drawing = False break elif event.type == pygame.MOUSEBUTTONUP: drawing = False if dragged_dot: dragged_dot.stop_drag() dragged_dot = None else: smoothed, normals = smooth_curve(points) elif event.type == pygame.MOUSEMOTION: if dragged_dot: dragged_dot.update_pos(mx, my) elif drawing: points.append((mx, my)) elif event.type == pygame.KEYDOWN: if event.key == pygame.K_p: random_dots = generate_random_dots() if event.key == pygame.K_l: for i in random_dots: print(f"({i.x}, {i.y})") # Draw random draggable dots for dot in random_dots: pygame.draw.circle(screen, BLACK, dot.pos(), DOT_RADIUS) # Draw raw stroke if len(points) > 1: pygame.draw.lines(screen, BLUE, False, points, 1) # Draw smoothed curve if len(smoothed) > 1: pygame.draw.lines(screen, RED, False, smoothed, 3) # Draw normals if smoothed and normals: draw_normals(screen, smoothed, normals) pygame.display.flip() clock.tick(60) pygame.quit() sys.exit() What algorithm could I use to accomplish this?
EDIT:
Some details about the diagram. The black dots are the input points to form the polygon. The red is the drawn line, which is a smoothed version of the blue one. The green lines show some equidistant test points on the drawn line. The required output order is the order in which the points have to be joined up to form the polygon, i.e. A,B,C,D for a rectangle. The input order of the points is not ordered in any meaningful way.
