撤销 Bresenham 线的算法

Question

我在网格上有一个点，我想为其创建一个合理的多边形轮廓。这些点将由用户选择，因此我不能指望它们能够“完美”地遵循 Bresenham 的针对具有奇怪斜率的线的算法。然而，我仍然在努力寻找一个明显“漂亮”的倾斜面：

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

我想要的是将这些点变成 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"""<svg
    viewBox="-1 -1 {vbx} {vby}"
    width="{vbx * scale}"
    height="{vbx * scale}">
    <polyline
    fill="none"
    stroke="black"
    stroke-width="0.1"
    points="{" ".join(map(lambda x: f"{x.real},{x.imag}", p))}">
    </polyline></svg>"""


print(example(pts))

这会导致可怕的锯齿状混乱：

<svg
    viewBox="-1 -1 7.0 8.0"
    width="140.0"
    height="140.0">
    <polyline
    fill="none"
    stroke="black"
    stroke-width="0.1"
    points="0.0,3.0 0.0,2.0 0.0,1.0 1.0,2.0 2.0,2.0 2.0,3.0 3.0,3.0 4.0,3.0 4.0,4.0 5.0,4.0 6.0,4.0 4.0,5.0 3.0,5.0 2.0,5.0 2.0,6.0 1.0,6.0 0.0,7.0 0.0,6.0 0.0,5.0 0.0,4.0 0.0,3.0">
    </polyline></svg>

有什么技巧可以让算法更好地响应明确定义的斜率并且仅为此生成三角形吗？

Answer 1

我们可以用相同的方式定义点（pts）。

然后我们可以创建这样的轮廓：

def get_outline_points(pts: List[complex]) -> List[complex]:

    by_y = defaultdict(list)
    for p in pts:
        by_y[p.imag].append(p.real)
    
    # Get leftmost points sorted from bottom to top
    left_side = [
        complex(min(row), y) 
        for y, row in sorted(by_y.items())
    ]
    
    # Get rightmost points sorted from top to bottom
    right_side = [
        complex(max(row), y) 
        for y, row in sorted(by_y.items(), reverse=True)
    ]
    
    # Combine left and right sides to form the outline
    outline = left_side + right_side
    
    return outline

现在你有了一个带有直/平滑边缘的轮廓。

完成 svg 渲染，与您已经做的方式类似，但要考虑轮廓：

def create_svg(pts: list[complex], scale: float = 20) -> str:
    outline = get_outline_points(pts)
    
    # Close the polygon by adding first point again
    if outline and outline[0] != outline[-1]:
        outline.append(outline[0])
    
    vbx = max(p.real for p in outline) + 1
    vby = max(p.imag for p in outline) + 1
    
    points_str = " ".join(f"{p.real},{p.imag}" for p in outline)
    
    return f"""<svg
    viewBox="-1 -1 {vbx} {vby}"
    width="{vbx * scale}"
    height="{vby * scale}">
    <polygon
        fill="none"
        stroke="black"
        stroke-width="0.1"
        points="{points_str}"
    />
    </svg>"""

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

  <svg
      viewBox="-1 -1 7.0 8.0"
      width="140"
      height="160">
      <polygon
          fill="none"
          stroke="black"
          stroke-width="0.1"
          points="0.0,1.0 0.0,1.0 0.0,2.0 0.0,3.0 0.0,4.0 0.0,5.0 0.0,6.0 0.0,7.0 0.0,7.0 6.0,4.0 0.0,1.0"
      />
  </svg>

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

<svg
    viewBox="-1 -1 10.0 7.0"
    width="200.0"
    height="140.0">
    <polygon
        fill="none"
        stroke="black"
        stroke-width="0.1"
        points="0.0,0.0 0.0,1.0 0.0,2.0 0.0,3.0 0.0,4.0 0.0,5.0 0.0,6.0 2.0,5.0 4.0,4.0 9.0,3.0 4.0,2.0 2.0,1.0 0.0,0.0"
    />
    </svg>