CODEWITHSUNDEEP
algorithmgeometrycomputational-geometry
Gealber
Gealber

Reputation: 483

Given a set of lattice points, how many group of points are there?

The idea is that given a set of lattices points in the plane, determine how many "group" of points there are in the given set. A group of points is defined as follow:

Given a set S of lattice points, 
it is said that these points form a group of points if and only if:
for each a of S the distance of the nearest point(s) is 1

The function must return a list with all the groups of points existing.

input: --> point: list
output: --> group: list

If it's possible to get a better algorithm beacause I'm not sure if this code work for every set of points.

My code look like this

def walk_point_path(points):
    groups = []
    points_x = sorted(points, key=lambda x: x[1])
    visited = [points_x[0]]
    q = [points_x[0]]
    while points_x:
        while q:
            x, y = q.pop()
            for x, y in (x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y):
                if [x, y] not in visited and [x, y] in points_x:
                    q.append([x, y])
                    visited.append([x, y])
        groups.append(visited)
        for point in visited:
            points_x.remove(point)
        if len(points_x) > 0:
            q = [points_x[0]]
            visited = [points_x[0]]
    return groups

Upvotes: 0

Views: 183

Answers (1)

MBo
MBo

Reputation: 80187

Consider some good implementation of connected-components labeling algorithm.

Your current approach exploits flood-fill algorithm (One component at a time kind) to get points in group.

Upvotes: 1

Related Questions