Удалить лишние точки на линии

Question

Я работаю над алгоритмом, который анализирует форму континента на простой черно-белой карте и возвращает контур его периметра.

Пример может быть следующим: [(1, 0), (2,0), (2,1), (2,2), (3,2) ...]

Пока что алгоритм выдает правильный список, но, как вы можете см., это производит избыточные точки.

В этом примере 3 точки после первой образуют прямую линию от 2,0 до 2,2. (2,1), лишняя точка, должна быть устранена, но я не уверен, как.

К вашему сведению: я работаю в чистом python приложении, единственная библиотека, которую я использую, это Pygame. Я смотрел на подобные вопросы без удачи.

Answer 1

Предполагая, что точки в порядке, вы в основном хотите сбросить точку, если следующая точка находится непосредственно позади нее от предыдущей точки.

from math import isclose


def lined_up(bef, p, aft):
    if p[1] - bef[1] == 0:
        if aft[1] - p[1] == 0:
            # matching signs
            return p[0] - bef[0] < 0 == p[0] - bef[0] < 0
        else:
            return False
    elif aft[1] - p[1] == 0:
        return False
    else:
        return isclose(
            (p[0] - bef[0]) / (p[1] - bef[1]),
            (aft[0] - p[0]) / (aft[1] - p[1]),
            rel_tol=1e-8
        )


def remove_redundant_points(pts):
    # remove redundant end points overlapping with the starting point
    while len(pts) > 1 and pts[-1] == pts[0]:
        pts = pts[:-1]
    return [pts[0]] + [p for bef, p, aft in zip(pts[0:-2], pts[1:-1], pts[2:])
            if not lined_up(bef, p, aft)] + [pts[-1]]


points = [(1, 0), (3, 0), (2, 0), (2, 1), (2, 2), (3, 3), (6, 6), (0, 2), (1, 0)]
print(remove_redundant_points(points))

Обратите внимание на использование math.isclose, чтобы избежать плавающей запятой ошибки деления.

Вывод:

[(1, 0), (2, 0), (2, 2), (6, 6), (0, 2)]

Answer 2

3 балла (x ₁ , y ₁ ), (x ₂ , y ₂ ) и (x ₃ , y ₃ ) являются коллинеарными (в строке), если:

(x ₂ -x ₁ ) ( y ₃ -y ₂ ) - (y ₂ -y ₁ ) (x ₃ -x ₂ ) = 0

Всякий раз, когда 3 последовательных точки на схеме являются коллинеарными, средняя является избыточной и может быть удалена.

Вы можете делать это постепенно по мере добавления точек к списку. Если в списке есть хотя бы 2 точки, то перед добавлением еще одной проверьте, совпадает ли ее коллинеарность с последними 2. Если это так, то удалите последнюю перед добавлением новой.

Когда все готово, проверьте начальную и конечную точки, чтобы увидеть, являются ли они избыточными, и удалите их, если они есть.

Answer 3

Если я правильно понимаю ваш пост, точка является «избыточной», если расстояние между предыдущей и следующей точками совпадает с суммой расстояний между точкой и ее соседями.

Код (непроверенный ):

def diffVector(pointA, pointB):
  # returns a vector representing the path to get from A to B
  return (pointB[0] - pointA[0], pointB[1] - pointA[1])

def distSq(pointA, pointB):
  # returns the square of the distance between two points
  # (more efficient than actual distance, and works for our purposes)
  diff = diffVector(pointA, pointB)
  return diff[0] * diff[0] + diff[1] * diff[1]

def findRedundancy(points):
  # returns a list of redundant point indexes to remove
  redundant = []
  # store the distance in a variable to avoid recalculating
  prevSegmentDist = distSq(points[0], points[1])
  for i, point in enumerate(points[1:-2]):
    prev = points[i-1]
    next = points[i+1]
    nextSegmentDist = distSq(point, next)
    # check if the combined distance is the same
    # as the straight-line distance between prev and next
    if distSq(prev, next) == prevSegmentDist + nextSegmentDist:
      redundant.append(i)
    prevSegmentDist = nextSegmentDist
  return redundant

Этот алгоритм будет подвержен ошибкам с плавающей запятой, поэтому вам следует заменить строгую проверку == на проверку того, что числа достаточно близки друг к другу, чтобы их можно было рассмотреть " то же самое ".