Алгоритм отмены линий Брезенхема ⇐ Python

[Anonymous]

У меня есть набор точек на сетке, для которого я хочу создать разумный контур многоугольника. Точки будут выбираться пользователем, поэтому я не могу ожидать, что они будут точно соответствовать алгоритму Брезенхэма для линий со странным наклоном. Тем не менее, я все еще изо всех сил пытаюсь заставить что-то работать для очевидной «красивой» наклонной стороны:

Код: Выделить всё

#
###
#####
#######
#####
###
#

Я хочу превратить эти точки в многоугольник SVG (или путь, или ломаную линию и т. д.). Как и следовало ожидать, это должен быть красивый аккуратный треугольник.
Вот код, который я пробовал:

Код: Выделить всё

import cmath

s = """
#
###
#####
#######
#####
###
#
"""
pts = [complex(c, r)
for (r, rt) in enumerate(s.splitlines())
for (c, ch) in enumerate(rt)
if ch == "#"]

def centroid(pts: list[complex]) -> complex:
return sum(pts) / len(pts)

def sort_counterclockwise(pts: list[complex],
center: complex | None = None) -> list[complex]:
if center is None:
center = centroid(pts)
return sorted(pts, key=lambda p: cmath.phase(p - center))

def perimeter(pts: list[complex]) -> list[complex]:
out = []
for pt in pts:
for d in (-1, 1, -1j, 1j, -1+1j, 1+1j, -1-1j, 1-1j):
xp = pt + d
if xp not in pts:
out.append(pt)
break
return sort_counterclockwise(out, centroid(pts))

def example(all_points: list[complex], scale: float = 20) -> str:
p = perimeter(all_points)
p.append(p[0])
vbx = max(map(lambda x: x.real, p)) + 1
vby = max(map(lambda x: x.imag, p)) + 1
return f"""

"""

print(example(pts))

Это приводит к ужасному беспорядку:

Код: Выделить всё

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

Подробнее здесь: https://stackoverflow.com/questions/791 ... nham-lines