Search code examples
pythonpoint-clouds

How to sort a random array of points into a shape?

I have a random array of points that forms a shape like this:

enter image description here

But it comes in such a way that the points (coordinates) that make it up are randomly distributed in an array.

How do I sort them so they are continuous (every pair of consecutive points in the array corresponds to a pair of consecutive points in the shape)?

Edit: should've explained it better.

We tried using some sort of clockwise-ness of the points, but it breaks at the edges and at the straight lines in the back. Some sort of seed, where the lowest X point is the starting point, and the closest ones get appended to it. Also breaks at the edges, where the closest point isn't necessary the consecutive one. If I separate upper and lower (using the lowest X point as the Y-criteria), and sort both arrays separately, the concave part breaks this as well.

The points come in a .dat file, where each line is 2 numbers, separated by a space:

2.345 1.234
1.234 2.345
Solution

  • According to this answer: https://cs.stackexchange.com/a/52627 you can use a part of Grahm Scan convex hull algorithm.

    The first step of the Grahm Scan is to sort the points in a set based on the angle made with the X axis when drawing a line through the point and the lower-right point of the set.

    If two or more points form the same angle with the X axis (i.e. are aligned with respect to the reference point) then those points should be sorted based on distance from the reference point.

    import dataclasses
from functools import cmp_to_key


@dataclasses.dataclass
class Point:
    x: float
    y: float


def left_(p: Point, a: Point, b: Point) -> float:
    return (a.x - p.x) * (b.y - p.y) - (b.x - p.x) * (a.y - p.y)


def compare_angle(p: Point, a: Point, b: Point) -> float:
    left = left_(p, a, b)
    if left == 0:
        return compare_distance(p, a, b)
    return left


def compare_distance(p: Point, a: Point, b: Point) -> float:
    distance_a = (p.x - a.x) ** 2 + (p.y - a.y) ** 2
    distance_b = (p.x - b.x) ** 2 + (p.y - b.y) ** 2
    return distance_a - distance_b


def sort_points(points: list[Point]):
    y0 = min(map(lambda p: p.y, points))
    p0 = Point(
        y=y0,
        x=max(map(lambda p: p.x, filter(lambda p: p.y == y0, points)))
    )
    return sorted(points, key=cmp_to_key(lambda a, b: compare_angle(p0, a, b)))

    Although, it still has some limitations, so possibly it won't make it perfectly in 100% cases, as shapes may be too complex. I think, it will do the work with even points distribution and when there is a decent amount of point comparing to the shape size, but if there will be some complex shape with long-running edges between points, close calls between the shape parts etc., it may make mistakes.

    P.S.: what I mean when I say in the comments that the computer does not know the correct shape so it can be wrong:

    both are the same points and both are mathematically correct non-self intersecting polygons example