import random

class Accumulator:

	NEIGHBOURHOOD=2

	def __init__(self):

		self._acc=[]

		self._hits=[]

	def add(self,line):

		(d,k)=self._findClosest(line)

		if d<=self.NEIGHBOURHOOD:

			self._acc=self._averageLines(self._acc[k],line,self._hits[k],1)

			self._hits[k]+=1

		else:

			k=-1

			self._acc.append(line)

			self._hits.append(1)

		return (self._hits[k],k)

	def pop(self,k):

		acc=self._acc

		(acc[k],acc[-1])=(acc[-1],acc[k])

		hits=self._hits

		(hits[k],hits[-1])=(hits[-1],hits[k])

		hits.pop()

		return acc.pop()

	def _findClosest(self,line):

		def dist(p,q):

			alpha=p.alpha*180/math.pi

			beta=q.alpha*180/math.pi

			gamma=abs(alpha-beta)

			if gamma>180: gamma=360-gamma

			return math.sqrt(gamma**2+(p.d-q.d)**2)

		(d,key)=min(zip((dist(line,p) for p in self._acc), range(len(self._acc))))

		return (d,key)

	def _averageLines(self,ab,cd,w1,w2):

		w=w1+w2

		(a,b)=ab.toPoints()

		(c,d)=cd.toPoints()

		e=(a*w1+c*w2)/w

		f=(b*w1+c*w2)/w

		return Line.fromPoints(e,f)

class RandomizedHoughTransform:

	HIT_LIMIT=10

	CANDIDATE_LIMIT=10

	MIN_SCORE=50

	def __init__(self,img):

		self._img=np.copy(img)

		(self._h,self._w)=img.shape[:2]

		self._acc=Accumulator()

		self._candidates=[]

		self._res=[]

	def _sampleLine(self):

		""":return: (Line) p"""

		a=self._chooseRandomPixel()

		b=self._chooseRandomPixel()

		while b==a: b=self._chooseRandomPixel()

		return Line.fromPoints(a,b)

	def _updateAcc(self,line):

		(hits,k)=self._acc.add(line)

		if hits>=self.HIT_LIMIT:

			self._addCandidate(self._acc.pop(k))

	def _addCandidate(self,line):

		self._candidates.append(line)

		if len(self._candidates)>=self.CANDIDATE_LIMIT:

			for p in self._candidates:

				p_=self._confirmLine(p)

				if p_: self._res.append(p_)

			self._candidates=[]

	def _chooseRandomPixel(self):

		val=0

		while not val:

			x=random.randrange(0,self._w)

			y=random.randrange(0,self._h)

			val=self._img[y,x]

		return EPoint(x,y)

	def _confirmLine(self,line):

		score=0

		for point in self._walkLine(line):

			if self._img[point]==1:

				score+=1

		if score>self.MIN_SCORE:

			for point in self._walkLine(line): # erase the line

				self._img[point]=0

			return line

		else: return None

	def _walkLine(self,line):

		(a,b,c)=line.toNormal()

		if abs(line.alpha-math.pi/2)<math.pi/4 or abs(line.alpha-3*math.pi/2)<math.pi/4: # vertical normal ~ horizontal line

			for x in range(self._w):

				y=int((-c-a*x)/b)

				if 0<=y<self.h:

					yield (y,x)

		else: # a predominantly vertical line

			for y in range(self._h):

				x=int((-c-b*y)/a)

				if 0<=x<self.w:

					yield (y,x)