0

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
Gealber
  • 463
  • 5
  • 13
  • In a 1D example, if you have the points `{1, 2, 5, 6}`. Is this a single group (because your condition is true for all the points) or two separate groups? Is your lattice uniform and unit-spaced (i.e., do you have integer coordinates)? – Nico Schertler Sep 18 '19 at 16:05
  • Possible duplicate of [connected component labeling in python](https://stackoverflow.com/questions/46441893/connected-component-labeling-in-python) – Prune Sep 18 '19 at 16:18
  • @NicoSchertler in the case of a 1D example the set {1,2,5,6} contains two group of points. And the lattice points space is like you say uniform and unit-spaced, where all the points to be tested has integer coordinates – Gealber Sep 18 '19 at 16:34

1 Answers1

1

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.

MBo
  • 77,366
  • 5
  • 53
  • 86