Find edge contours around groups of squares in a grid

edgecontour.py

#Find edge contours around groups of squares in a grid
#By Tim Sheerman-Chase, 2016, released under CC0

def FindContourEdges(pts):

	#Find edge fragments of area
	unmergedEdges = {}
	for pt in pts:
		if (pt[0]-1, pt[1]) not in pts:
			unmergedEdges[pt] = (pt[0], pt[1]+1)
		if (pt[0], pt[1]+1) not in pts:
			unmergedEdges[(pt[0], pt[1]+1)] = (pt[0]+1, pt[1]+1)
		if (pt[0]+1, pt[1]) not in pts:
			unmergedEdges[(pt[0]+1, pt[1]+1)] = (pt[0]+1, pt[1])
		if (pt[0], pt[1]-1) not in pts:
			unmergedEdges[(pt[0]+1, pt[1])] = pt
	
	#Merge edges
	contours = []
	while len(unmergedEdges) > 0:
		cursor = list(unmergedEdges)[0]
		contour = [cursor]
		cursor = unmergedEdges[cursor]
		contour.append(cursor)
		while cursor != contour[0]:
			cursor = unmergedEdges[cursor]
			contour.append(cursor)

		filtEdges = {}
		for edgeStart in unmergedEdges:
			if edgeStart in contour: continue
			filtEdges[edgeStart] = unmergedEdges[edgeStart]
		unmergedEdges = filtEdges

		contours.append(contour)

	return contours

if __name__=="__main__":
	import matplotlib.pyplot as plt

	pts = set([(50, 14), (51, 12), (49, 12), (48, 13), (47, 13), (50, 15), (50, 11), (51, 15), (48, 14), (51, 11), (49, 15), (52, 12), (50, 12), (49, 11), (51, 14), (50, 16), (49, 14), (52, 13), (51, 13), (49, 13), (48, 12), (50, 10), (47, 16)])

	contours = FindContourEdges(pts)

	for contour in contours:
		plt.plot([tmp[0]-0.5 for tmp in contour], [tmp[1]-0.5 for tmp in contour])

	plt.plot([tmp[0] for tmp in pts], [tmp[1] for tmp in pts], '.')
	plt.show()