pythonalgorithmpolygonconcave

Ordering points that roughly follow the contour of a line to form a polygon

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:

  1. The polygon is not self-intersecting.
  2. The resulting polygon is not necessarily convex; a convex hull will not suffice
  3. The polygon needs to go through all of the points. I have tried the alphashape concave hull algorithm, but I was not able to get it to work (it ignored some points, and I wasn't sure what to tune the alpha value to)
  4. 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.

Example of problem

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.

Solution

  • Here is some demo code in C++ to show how this algorithm works

    void cSolver::gen1()
{
    // Example from https://stackoverflow.com/q/79696095/16582
    // (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)]]
    myInputPoints = {{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}};
}
void cSolver::connect()
{
    // working copy of input
    auto work = myInputPoints;

    mySortedPoints.clear();

    // select first point
    cxy p = work[0];

    // loop unitl all points connected
    while (mySortedPoints.size() < work.size())
    {
        // output selected point
        mySortedPoints.push_back(p);

        // find nearest unconnected point
        double mind = INT_MAX;
        int mindex;                 // index of nearest point
        for (int i = 1; i < work.size(); i++)
        {
            // ignore connected and self points
            if (p.isValid() && ( ! ( p == work[i] )))
            {
                double d = p.dist2(work[i]);
                if (d < mind)
                {
                    mind = d;
                    mindex = i;
                }
            }
        }
        // select nearest point
        p = work[mindex];

        // prevemt it being reconsidered
        work[mindex].invalidate();
    }
}

    Running on your sample data this produces

    enter image description here

    Complete app code at https://codeberg.org/JamesBremner/Polygonify

    As @stef pointed out, if the polygon has a narrow neck like a sand timer then this algorithm may become confused by jumping across the narrow neck. This could be prevented by checking that all connections between dots do not intersect the 'drawn line' in the middle of the polygon.

    enter image description here

    I took a look at your code, but cannot spot where the drawn line specification are. So I guessed.

    void cSolver::gen1()
{
    // Verices of polygon in random order
    // Example from https://stackoverflow.com/q/79696095/16582
    // (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)]]
    myInputPoints = {{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}};

    // polygon middle line
    // my guess
    myMiddleLine = {{100, 300}, {200, 400}, {300, 450}};
}
void cSolver::connect()
{
    // working copy of input
    auto work = myInputPoints;

    mySortedPoints.clear();

    // select first point
    cxy p = work[0];

    // loop unitl all points connected
    while (mySortedPoints.size() < work.size())
    {
        // output selected point
        mySortedPoints.push_back(p);

        // find nearest unconnected point
        double mind = INT_MAX;
        int mindex; // index of nearest point
        for (int i = 1; i < work.size(); i++)
        {
            // ignore previously connected points
            if (!p.isValid())
                continue;

            // ignore self points
            if (p == work[i])
                continue;

            // ignore connections that cross the middle line
            bool cross = false;
            cxy prev;
            for (cxy &mp : myMiddleLine)
            {
                if (!prev.isValid())
                {
                    prev = mp;
                    continue;
                }
                cxy intersect;
                if (cxy::isIntersection(
                        intersect,
                        p, work[i],     // test connection
                        prev, mp))      // middle line segment
                        {
                            cross = true;
                            break;
                        }
            }
            if( cross )
                continue;

            double d = p.dist2(work[i]);
            if (d < mind)
            {
                mind = d;
                mindex = i;
            }
        }
        // select nearest point
        p = work[mindex];

        // prevent it being reconsidered
        work[mindex].invalidate();
    }

    Minor notes: