Finding N scattered points in a set of given points.

farthest.py

import numpy as np


def points_indices(points: np.ndarray,
                   *,
                   count: int) -> np.ndarray:
    """
    Finds a set of points quite far apart from each other.
    First point in the array is always included.
    Based on:
    https://codereview.stackexchange.com/questions/179561/farthest-point-algorithm-in-python
    :param points: input array
    :param count: number of points to select
    :return: indices of selected points
    """
    indices = np.zeros(count,
                       dtype=int)
    distances = get_distances(points[0],
                              points)

    for index in range(1, count):
        indices[index] = np.argmax(distances)
        distances_to_current_point = get_distances(points[indices[index]],
                                                   points)
        distances = np.minimum(distances,
                               distances_to_current_point)
    return indices


def get_distances(point: np.ndarray,
                  array: np.ndarray) -> np.ndarray:
    """
    Calculates distances from the given point to an array of points.
    :param point: point from which distances are measured
    :param array: array of points
    :return: array of distances
    """
    return ((point - array) ** 2).sum(axis=1)

farthest_v2.py

from itertools import (accumulate,
                       chain,
                       repeat)

import numpy as np


def distances(point: np.ndarray,
              array: np.ndarray) -> np.ndarray:
    """
    Calculates distances from the given point to an array of points.
    :param point: point from which distances are measured
    :param array: array of points
    :return: array of distances
    """
    return ((point - array) ** 2).sum(axis=1)


def min_distances(distances, points):
    """
    Finds from given distances the farthest point.
    Calculates distances between it and a given set of points.
    Returns elementwise minimum of these distances.
    """
    max_distance_index = np.argmax(distances)
    farthest_point = points[max_distance_index]
    distances_to_farthest_point = distances(farthest_point,
                                            points)
    return np.minimum(distances,
                      distances_to_farthest_point)


def points_indices(points: np.ndarray,
                   *,
                   count: int,
                   first_point_index: int = 0) -> np.ndarray:
    """
    Finds a set of points quite far apart from each other.
    First point in the array is always included.
    Based on:
    https://codereview.stackexchange.com/questions/179561/farthest-point-algorithm-in-python
    :param points: input array
    :param count: number of points to select
    :return: indices of selected points
    """
    initial_distances = distances(points[first_point_index],
                                  points)

    iterative_distances = accumulate(chain([initial_distances], 
                                           repeat(points, count - 2)),
                                     min_distances)

    indices_except_first = np.fromiter(map(np.argmax, iterative_distances), 
                                       dtype=int)
    return np.insert(indices_except_first,
                     0,
                     first_point_index)