import logging

logging.basicConfig(format='%(asctime)s %(levelname)s: %(message)s', level=logging.DEBUG)

class misc:

class gui:

	showBigPoints=True

	showGrid=False

class Corners:

	def __init__(self):

		self.corners=[]

	## Adds a new corner if there are less than four, replaces the closest otherwise.

	def add(self,x,y):

		a=EPoint(x,y)

		# for i,c in enumerate(self.corners): # move an improperly placed point

			# if a.dist(c)<20:

				# self.corners[i]=a

				# return

		if len(self.corners)<4: # add a new corner

			self.corners.append(a)

		if len(self.corners)<4:

			return

		index,minDist=0,float('inf') # replace the corner closest to the clicked point

		for i,c in enumerate(self.corners):

			if a.dist(c)<minDist:

				index,minDist=i,a.dist(c)

		self.corners[index]=a

	## Computes twice the area of the triangle formed by points a,b,c.

	#

	#  @return positive value for points oriented counter-clockwise, negative for clockwise, zero for degenerate cases.

	def _doubleTriangleArea(a,b,c):

		return (a.x-b.x)*(c.y-a.y)-(c.x-a.x)*(a.y-b.y)

	def _slope(a,b):

		if(b.x==a.x): return float("inf")

		return (b.y-a.y)/(b.x-a.x)

	## Order the corners (0,1,2,3) so they make a quadrangle with vertices KLMN in counter-clockwise order, K being in the upper left.

	#

	#  For four points ABCD, there are 24 possible permutations corresponding to the desired KLMN.

	#  When we relax the condition of K being the upper left one, we get six groups of four equivalent permutations. KLMN ~ LMNK ~ MNKL ~ NKLM.

	#

	#  We determine which of the points' triplets are oriented clockwise and which counter-clockwise (minus/plus in the table below)

	#  and swap them so that all triangles turn counter-clockwise.

	#

	#  xxxx -> KLMN | ABC | ABD | ACD | BCD | index | swap

	#  ------------ | :-: | :-: | :-: | :-: | ----: | ----

	#  A BCD        |  +  |  +  |  +  |  +  |    15 | 0

	#  A BDC        |  +  |  +  |  -  |  -  |    12 | CD

	#  A CBD        |  -  |  +  |  +  |  -  |     6 | BC

	#  A CDB        |  -  |  -  |  +  |  +  |     3 | AB

	#  A DBC        |  +  |  -  |  -  |  +  |     9 | AD

	#  A DCB        |  -  |  -  |  -  |  -  |     0 | BD

	#

	#  For every non-degenerate quadrangle, there must be 1-3 edges going right-left (from a higher to a lower x coordinate).

	#  From these pick the one with the lowest slope (dy/dx) and declare its ending point the upper left corner. For the same slope pick the one further left.

	#

	#  @return True for a convex quadrangle, False for concave and degenerate cases.

	def canonizeOrder(self):

		if len(self.corners)!=4: return False # erroneus call

		a,b,c,d=self.corners

		abc=Corners._doubleTriangleArea(a,b,c)

		abd=Corners._doubleTriangleArea(a,b,d)

		acd=Corners._doubleTriangleArea(a,c,d)

		bcd=Corners._doubleTriangleArea(b,c,d)

		if any(x==0 for x in (abc,abd,acd,bcd)): return False # collinear degenerate

		swaps=[(1,3),(0,1),(1,2),(0,3),(2,3),(0,0)]

		index=(8 if abc>0 else 0)|(4 if abd>0 else 0)|(2 if acd>0 else 0)|(1 if bcd>0 else 0)

		if index%3!=0: return False # concave degenerate

		swap=swaps[index//3]

		self.corners[swap[0]], self.corners[swap[1]] = self.corners[swap[1]], self.corners[swap[0]] # counter-clockwise order

		kIndex=None

		lowestSlope=float("inf")

		for i,corner in enumerate(self.corners): # find the NK edge: going right-left with the lowest slope, secondarily the one going down

			ii=(i+1)%4

			slope=abs(Corners._slope(corner,self.corners[ii]))

			if corner.x>self.corners[ii].x and (slope<lowestSlope or (slope==lowestSlope and corner.y<self.corners[ii].y)):

				kIndex=ii

				lowestSlope=slope

		self.corners=self.corners[kIndex:]+self.corners[:kIndex] # rotate the upper left corner to the first place

		return True # success

import numpy

## Projective transformation of a point with a matrix A.

#  

#  Takes a point as a horizontal vector and multiplies it transposed with A from left.

#  

#  @return transformed point as a numpy.array

def transformPoint(point,A):

	return (A*numpy.matrix(point).transpose()).getA1()

class Grid:

	## Creates a Grid from the provided Corners object.

	#

	#  Finds the vanishing points of the board lines (corner points define perspectively transformed parallel lines). The vanishing points define the image horizon.

	#

	#  The horizon can be used to construct a matrix for affine rectification of the image (restoring parallel lines parallelism). We transform the corner points by this matrix,

	#  interpolate them to get proper intersections' coordinates and then transform these back to get their placement at the original image.

	#

	#  The result is stored in grid.intersections, a boardSize*boardSize list with [row][column] coordinates.

	#

	#  @param corners a properly initialized Corners object. !! Needs a check for the proper initialization.

	def __init__(self,corners):

		# ad

		# bc

		a,b,c,d=[c.toProjective() for c in corners.corners]

		p1=numpy.cross(a,b)

		p2=numpy.cross(c,d)

		vanish1=numpy.cross(p1,p2)

		# !! 32 bit int can overflow. keeping it reasonably small. might want to use a cleaner solution

		vanish1=EPoint.fromProjective(vanish1).toProjective() # !! EPoint fails with point in infinity

		p3=numpy.cross(a,d)

		p4=numpy.cross(b,c)

		vanish2=numpy.cross(p3,p4)

		vanish2=EPoint.fromProjective(vanish2).toProjective()

		horizon=numpy.cross(vanish1,vanish2)

		horizon=EPoint.fromProjective(horizon).toProjective()

		rectiMatrix=numpy.matrix([horizon,[0,1,0],[0,0,1]])

		rectiMatrixInv=numpy.linalg.inv(rectiMatrix)

		affineCorners=[EPoint.fromProjective(transformPoint(x,rectiMatrix)) for x in (a,b,c,d)]

		x=[affineCorners[0]-affineCorners[3],affineCorners[1]-affineCorners[2],affineCorners[0]-affineCorners[1],affineCorners[3]-affineCorners[2]]

		self.intersections=[]

		boardSize=19

		for r in range(boardSize):

			self.intersections.append([None]*boardSize)

			rowStart=(affineCorners[0]*(boardSize-1-r)+affineCorners[1]*r) / (boardSize-1)

			rowEnd=(affineCorners[3]*(boardSize-1-r)+affineCorners[2]*r) / (boardSize-1)

			for c in range(boardSize):

				affineIntersection=(rowStart*(boardSize-1-c)+rowEnd*c) / (boardSize-1)

				self.intersections[r][c]=EPoint.fromProjective(transformPoint(affineIntersection.toProjective(),rectiMatrixInv))

	def stoneSizeAt(self,r,c,sizeCoef):

		intersection=self.intersections[r][c]

		if c>0: width=sizeCoef*(intersection.x-self.intersections[r][c-1].x)

		else: width=sizeCoef*(self.intersections[r][c+1].x-intersection.x)

		if r>0: height=sizeCoef*(intersection.y-self.intersections[r-1][c].y)

		else: height=sizeCoef*(self.intersections[r+1][c].y-intersection.y)

		return (width,height)

from PIL import ImageTk

import PIL

import config

		self.corners=Corners()

		self.boardGrid=None

		tk.Frame.__init__(self, master)

		self.grid(column=0,row=0)

		# a captured frame with overlay graphics

		self.imgView=tk.Canvas(self)

		self.imgView.configure(width=480,height=360)

		self.imgView.bind('<1>',lambda e: self.addCorner(e.x,e.y))

		self.imgView.grid(column=0,row=0)

		# board with detected stones

		self.boardView=BoardView(self)

		self.boardView.grid(column=1,row=0)

		# more controls below the board

		self.scaleTresW.set(60.0)

		self.scaleTresB.grid(column=0,row=1,columnspan=2)

		self.scaleTresW.grid(column=0,row=2,columnspan=2)

		# render everything

		self.redrawImgView()

	## Stores a grid corner located at x,y coordinates.

	def addCorner(self,x,y):

		self.corners.add(x,y)

		if self.corners.canonizeOrder():

		self.redrawImgView()

	## Redraws the current image and its overlay.

	def redrawImgView(self):

		self.imgView.create_image(2,2,anchor="nw",image=self.img)

		widthRatio=origWidth/self.img.width()

		heightRatio=origHeight/self.img.height()

		sizeCoef=max(widthRatio,heightRatio)

		for corner in self.corners.corners:

			self.markPoint(corner.x,corner.y)

		if self.boardGrid!=None and config.gui.showGrid:

			for r in range(19):

				a=self.boardGrid.intersections[r][0]

				b=self.boardGrid.intersections[r][-1]

				self.imgView.create_line(a.x,a.y,b.x,b.y,fill='#00ff00')

			for c in range(19):

				a=self.boardGrid.intersections[0][c]

				b=self.boardGrid.intersections[-1][c]

				self.imgView.create_line(a.x,a.y,b.x,b.y,fill='#00ff00')

		if self.boardGrid!=None and config.gui.showBigPoints:

			for r in range(19):

				for c in range(19):

					self.imgView.create_rectangle(r1,c1,r2,c2,outline="#00ffff")

		self.imgView.grid()

	## Marks a point at the image with a green cross. Used for corners.

	def markPoint(self,x,y):

		self.imgView.create_line(x-3,y-3,x+4,y+4,fill="#00ff00")

		self.imgView.create_line(x-3,y+3,x+4,y-4,fill="#00ff00")

		self.imgView.grid()

## Handles and presents the game state as detected by the program.

class BoardView(tk.Canvas):

	def __init__(self, master=None):

		self.boardGrid=None

		tk.Canvas.__init__(self, master)

		self.configure(width=360,height=360,background="#ffcc00")

		self.drawGrid()

		self.grid()

			for c,point in enumerate(row):

				self.drawStone(r,c,point)

		self.grid()

	def drawGrid(self):

		for i in range(19):

			self.create_line(18,18*(i+1),360-18,18*(i+1),fill="#000000") # rows

			self.create_line(18*(i+1),18,18*(i+1),360-18,fill="#000000") # cols

		self.drawStars()

	def drawStars(self):

		for r in range(4,19,6):

			for c in range(4,19,6):

				self.create_oval(r*18-2,c*18-2,r*18+2,c*18+2,fill='#000000')

	## Draws a stone at provided coordinates.

	#

	#  For an unknown color draws nothing and returns False.

	#

	#  @param r row coordinate, [0-18], counted from top

	#  @param c column coordinate, [0-18], counted from left

	#  @param color color indicator, Go.BLACK or Go.WHITE

	def drawStone(self,r,c,color):

		if color==Go.BLACK: hexCode='#000000'

		elif color==Go.WHITE: hexCode='#ffffff'

		else: return False

		r+=1

		c+=1

		self.create_oval(c*18-9,r*18-9,c*18+9,r*18+9,fill=hexCode)

import logging

class ImageAnalyzer:

	def __init__(self,tresB=30,tresW=60):

		self.board=[[Go.EMPTY]*19 for r in range(19)]

		self.grid=None

		self.tresB=tresB

		self.tresW=tresW

	def analyze(self,image,sizeCoef,shift):

		if self.grid==None: return False

		for r in range(19):

			for c in range(19):

				intersection=self.grid.intersections[r][c]

				self.board[r][c]=self.analyzePoint(image,r,c,intersection*sizeCoef+shift,*(self.grid.stoneSizeAt(r,c,sizeCoef)))

	def analyzePoint(self,image,row,col,imageCoords,stoneWidth,stoneHeight):

		b=w=e=0

		for y in range(y1,y2+1):

			for x in range(x1,x2+1):

				red,green,blue=image.getpixel((x,y))

				I=(red+green+blue)/255/3

				m=min(red,green,blue)

				S=1-m/I

				if 100*I<self.tresB: b+=1

				elif 100*I>self.tresW: w+=1

				else: e+=1

		logging.debug("(%d,%d) ... (b=%d,w=%d,e=%d)", row, col, b, w, e)

		if b>=w and b>=e: return Go.BLACK

		if w>=b and w>=e: return Go.WHITE

		return Go.EMPTY

		x=int(imageCoords.x)

		y=int(imageCoords.y)

		xmax=max(int(stoneWidth*2//7), 2) # !! optimal parameters subject to further research

		ymax=max(int(stoneHeight*2//7), 2)

		return ((x-xmax,y-ymax), (x+xmax,y+ymax))