The Cohen and Sutherland 2D Line-Clipping Algorithm

#!/usr/bin/python2.6

from PIL import Image, ImageDraw, ImageFont
from subprocess import call
import math

left_region 	= 1
right_region 	= 2
bottom_region 	= 4
top_region 		= 8

class Line:
	def __init__(self, _x1, _y1, _x2, _y2):
		self.x = (_x1, _x2)
		self.y = (_y1, _y2)

	# Used for printing
	def __repr__(self):
		return "(%.2f, %.2f), (%.2f, %.2f)" % (self.x[0], self.x[1], self.y[0], self.y[1])

	def draw(self, _draw, _colour = (64,64,64,255), _width = 1):
		_draw.line((self.x[0], self.y[0], self.x[1], self.y[1]), fill=_colour, width=_width)



class SquareBound:
	def __init__(self, _pos, _size):
		self.leftX 		= _pos[0] - (_size[0] / 2)
		self.bottomY 	= _pos[1] - (_size[1] / 2)
		self.rightX 	= _pos[0] + (_size[0] / 2)
		self.topY 		= _pos[1] + (_size[1] / 2)

	def draw(self, _draw):
		_draw.line( (self.leftX, self.bottomY, 	self.rightX, self.bottomY), fill=(0, 0, 0, 255), width=2)	# Top Line
		_draw.line( (self.leftX, self.topY, 	self.rightX, self.topY), 	fill=(0, 0, 0, 255), width=2) 	# Bottom Line
		_draw.line( (self.leftX, self.bottomY, 	self.leftX, self.topY), 	fill=(0, 0, 0, 255), width=2)	# Left line
		_draw.line( (self.rightX, self.bottomY, self.rightX, self.topY), 	fill=(0, 0, 0, 255), width=2)	# Right Line

	def drawText(self, _draw):
		fnt = ImageFont.truetype("/usr/share/fonts/dejavu/DejaVuSans.ttf", 15)

		width = self.rightX - self.leftX
		height = self.topY - self.bottomY
		halfWidth = width / 2.0
		halfHeight = height / 2.0
		halfFontWidth = 20

		topHeight = self.bottomY - halfHeight
		_draw.text( (self.leftX + halfWidth - halfFontWidth, topHeight), 		  "1000", font=fnt, fill=(255, 0, 0, 255))	# Top 
		_draw.text( (self.leftX - halfWidth - halfFontWidth, topHeight), 		  "1001", font=fnt, fill=(255, 0, 0, 255))	# Top Left
		_draw.text( (self.leftX + halfWidth - halfFontWidth + width,  topHeight), "1010", font=fnt, fill=(255, 0, 0, 255))	# Top Right

		middleHeight = height + halfHeight + halfFontWidth
		_draw.text( (self.leftX + halfWidth - halfFontWidth, 		 middleHeight), "0000", font=fnt, fill=(255, 0, 0, 255)) # Middle
		_draw.text( (self.leftX - halfWidth - halfFontWidth, 		 middleHeight), "0001", font=fnt, fill=(255, 0, 0, 255)) # Middle Left
		_draw.text( (self.leftX + halfWidth - halfFontWidth + width, middleHeight), "0010", font=fnt, fill=(255, 0, 0, 255)) # Middle Right

		bottomHeight = self.topY + halfHeight
		_draw.text( (self.leftX + halfWidth - halfFontWidth, 		 bottomHeight), "0100", font=fnt, fill=(255, 0, 0, 255)) # Bottom 
		_draw.text( (self.leftX - halfWidth - halfFontWidth, 		 bottomHeight), "0101", font=fnt, fill=(255, 0, 0, 255)) # Bottom Left
		_draw.text( (self.leftX + halfWidth + width - halfFontWidth, bottomHeight), "0110", font=fnt, fill=(255, 0, 0, 255)) # Bottom Right

def getRegionCode(_x, _y, _bounds):
	region = 0

	if   _x < _bounds.leftX:	region |= left_region
	elif _x > _bounds.rightX:	region |= right_region

	if   _y > _bounds.bottomY:	region |= bottom_region
	elif _y < _bounds.topY:		region |= top_region

	return region

def getIntersection(_a, _b):
	pass

def sutherland(_lines, _bounds):
	clippedLines = []

	for line in _lines:
		clipLine(line, _bounds, clippedLines)

	return clippedLines


def clipLine(_line, _bounds, clippedLines):
	x = 0
	y = 0

	x1 = _line.x[0]
	y1 = _line.y[0]
	x2 = _line.x[1]
	y2 = _line.y[1]

	c = 0
	c2 = getRegionCode(x1, y1, _bounds)
	c1 = getRegionCode(x2, y2, _bounds)

	print format(c1, '#006b')[2:], format(c2, '#006b')[2:]

	small_t = 0.000000005

	while( (c1 != 0) or (c2 != 0) ):
		if( c1 & c2 != 0 ):
			# Trivial reject
			return False

		# Why do we choose stuff here??
		c = c2 if (c1 == 0) else c1

		xleft = _bounds.leftX
		xright = _bounds.rightX
		ytop = _bounds.topY
		ybottom = _bounds.bottomY

		print format(c, '#006b')[2:], bool(c&top_region), bool(c&bottom_region), bool(c&right_region), bool(c&left_region)

		if c & top_region:
			# Compute intersection with the left x boundary
			t = x2 - x1

			if( math.fabs(t) < small_t ):
				t = small_t

			y = ((xleft - x1) / t) * (y2 - y1) + y1
			x = xleft
		elif c & bottom_region:
			# Compute intersection with the right x boundary
			t = x2 - x1

			if( math.fabs(t) < small_t ):
				t = small_t

			y = ((xright - x1) / t) * (y2 - y1) + y1
			x = xright
		elif c & right_region:
			# Compute intersection with the bottom y boundary
			t = y2 - y1

			if( math.fabs(t) < small_t ):
				t = small_t

			x = ((ybottom - y1) / t) * (x2 - x1) + x1
			y = ybottom
		elif c & left_region:
			# Compute intersection with the top y boundary
			t = y2 - y1

			if( math.fabs(t) < small_t ):
				t = small_t

			x = ((ytop - y1) / t) * (x2 - x1) + x1
			y = ytop

		if(c == c1):
			x1 = x
			y1 = y
			c1 = getRegionCode(x1, y1, _bounds)
		else:
			x2 = x
			y2 = y
			c2 = getRegionCode(x2, y2, _bounds)

		draw.ellipse( (x, y, x + 8, y + 8), fill=(0, 0, 255, 255) )
		#draw.ellipse( (x2, y2, x2 + 8, y2 + 8), fill=(0, 0, 255, 255) )
		print c1, c2

		newLine = Line( x1, y1, x2, y2 )
		newLine.draw(draw, _colour = (0, 255, 0, 255), _width = 1)
		#end while

	newLine = Line( x1, y1, x2, y2 )
	clippedLines.append( newLine )
	return True



filename = "tmp.tif"
im = Image.new('RGBA', (512, 512), (255, 255, 255, 255)) 
draw = ImageDraw.Draw(im) 

bound = SquareBound( (256, 256), (200, 150))
bound.draw(draw)

lines = []
#lines.append( Line(16, 16, 500, 500) )
#lines.append( Line(64, 128, 256, 128) )
#lines.append( Line(64, 64, 256, 512) )
#lines.append( Line(12, 300, 300, 128) )
lines.append( Line(300, 203, 43, 53) )
#lines.append( Line(256, 256, 300, 300) )

for line in lines:
	line.draw(draw)

clippedLines = sutherland(lines, bound)

for line in clippedLines:
	line.draw(draw, _colour = (0, 255, 0, 255), _width = 1)

bound.drawText(draw)

im.save(filename)
call(["display", filename])