Go语言实现形状边界像素的顺时针连续排序

你遇到的正方形案例死循环问题，核心原因通常有三个：一是邻接检测只用到4方向（上下左右），漏掉了拐角处的8邻接像素；二是起始点选择或方向优先级不对，导致遍历偏离正确路径；三是未标记已访问像素，出现重复遍历或无法闭合的情况。

1. 改用8邻接+顺时针方向优先级 #

顺时针环绕边界时，要从当前点的右下方向开始，按顺时针顺序检查8个邻接方向，确保不会跳过拐角像素。方向优先级顺序为：右下→下→左下→左→左上→上→右上→右，这个顺序能保证始终沿着边界的顺时针方向推进。

2. 锁定正确起始点 #

必须选择边界的最左上角像素（y坐标最小，y相同时x坐标最小）作为起始点，这是顺时针环绕的天然起点，能避免遍历方向混乱。

3. 标记已访问像素 #

用哈希集合或二维数组记录已加入排序列表的像素，每次找到下一个邻接点后立即标记，直到回到起始点完成闭合环绕，彻底避免死循环。

package main

import (
	"image"
	"image/png"
	"os"
)

// Pixel 定义像素坐标结构
type Pixel struct {
	X, Y int
}

// 顺时针8邻接方向优先级（从右下开始顺时针遍历）
var clockwiseDirs = []Pixel{
	{1, 1},   // 右下
	{0, 1},   // 下
	{-1, 1},  // 左下
	{-1, 0},  // 左
	{-1, -1}, // 左上
	{0, -1},  // 上
	{1, -1},  // 右上
	{1, 0},   // 右
}

// SortBoundaryClockwise 将扫描顺序的边界像素转为顺时针环绕顺序
func SortBoundaryClockwise(boundary []Pixel) []Pixel {
	if len(boundary) == 0 {
		return nil
	}

	// 构建快速查找的像素集合
	pixelMap := make(map[Pixel]bool)
	for _, p := range boundary {
		pixelMap[p] = true
	}

	// 确定起始点：最左上角的边界像素
	start := boundary[0]
	for _, p := range boundary {
		if p.Y < start.Y || (p.Y == start.Y && p.X < start.X) {
			start = p
		}
	}

	// 开始顺时针遍历
	sorted := []Pixel{start}
	visited := map[Pixel]bool{start: true}
	current := start

	for {
		foundNext := false
		// 按优先级顺序查找下一个未访问的邻接边界像素
		for _, dir := range clockwiseDirs {
			next := Pixel{current.X + dir.X, current.Y + dir.Y}
			if pixelMap[next] && !visited[next] {
				sorted = append(sorted, next)
				visited[next] = true
				current = next
				foundNext = true
				break
			}
		}

		// 未找到下一个点时，检查是否回到起点完成闭合
		if !foundNext {
			for _, dir := range clockwiseDirs {
				next := Pixel{current.X + dir.X, current.Y + dir.Y}
				if next == start && len(sorted) > 1 {
					return sorted
				}
			}
			break // 处理非闭合边界的异常情况
		}

		// 回到起始点，结束遍历
		if current == start && len(sorted) > 1 {
			break
		}
	}

	return sorted
}

// GetBoundaryPixels 读取图像并提取边界像素（保留你的核心检测逻辑）
func GetBoundaryPixels(img image.Image) []Pixel {
	bounds := img.Bounds()
	boundary := []Pixel{}
	whiteR, whiteG, whiteB, whiteA := uint32(0xFFFF), uint32(0xFFFF), uint32(0xFFFF), uint32(0xFFFF)

	for y := bounds.Min.Y; y < bounds.Max.Y; y++ {
		for x := bounds.Min.X; x < bounds.Max.X; x++ {
			r, g, b, a := img.At(x, y).RGBA()
			// 跳过白色像素
			if r == whiteR && g == whiteG && b == whiteB && a == whiteA {
				continue
			}
			// 检测是否为边界：上下左右有白色像素，或处于图像边缘
			isBoundary := false
			dirs := []Pixel{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
			for _, dir := range dirs {
				nx, ny := x+dir.X, y+dir.Y
				if nx < bounds.Min.X || nx >= bounds.Max.X || ny < bounds.Min.Y || ny >= bounds.Max.Y {
					isBoundary = true
					break
				}
				nr, ng, nb, na := img.At(nx, ny).RGBA()
				if nr == whiteR && ng == whiteG && nb == whiteB && na == whiteA {
					isBoundary = true
					break
				}
			}
			if isBoundary {
				boundary = append(boundary, Pixel{x, y})
			}
		}
	}
	return boundary
}

func main() {
	file, err := os.Open("square.png")
	if err != nil {
		panic(err)
	}
	defer file.Close()

	img, err := png.Decode(file)
	if err != nil {
		panic(err)
	}

	boundary := GetBoundaryPixels(img)
	sortedBoundary := SortBoundaryClockwise(boundary)

	// 输出顺时针排序后的边界像素
	for _, p := range sortedBoundary {
		println(p.X, p.Y)
	}
}

• 去重预处理：提取边界像素时过滤重复点，减少集合冗余数据，提升遍历效率。
• 性能优化：处理大图像时，用二维数组替代哈希集合存储像素和已访问标记，访问速度更快。
• 方向灵活切换：若需要逆时针排序，只需将clockwiseDirs的顺序反转即可。
• 异常处理：增加非闭合边界的判断逻辑，遍历结束后若未回到起点，输出警告或执行容错处理。

内容的提问来源于stack exchange，提问作者Vasily