diff --git a/exp/board_detect.py b/exp/board_detect.py --- a/exp/board_detect.py +++ b/exp/board_detect.py @@ -13,7 +13,7 @@ import scipy.cluster import scipy.ndimage import scipy.signal -from geometry import Line, point2lineDistance +from geometry import Line from polar_hough import PolarHough from annotations import DataFile,computeBoundingBox from hough import show,prepareEdgeImg,HoughTransform diff --git a/exp/geometry.py b/exp/geometry.py --- a/exp/geometry.py +++ b/exp/geometry.py @@ -1,59 +1,47 @@ import math -import numpy as np - -from analyzer.epoint import EPoint, homogenize -from analyzer.grid import transformPoint +from analyzer.epoint import EPoint -class Line(): - def __init__(self,a,b): - self.a=a - self.b=b - self.points={a,b} +class Line: + def __init__(self,alpha,d): + self._alpha=alpha + self._d=d + self._sin=math.sin(alpha) + self._cos=math.cos(alpha) - def getSortedPoints(self): - return tuple(sorted(self.points)) + @staticmethod + def fromNormal(a,b,c): + """ax + by + c = 0""" + norm=-c/abs(c)*math.sqrt(a**2+b**2) + (a_,b_,c_)=(a/norm,b/norm,c/norm) + alpha=math.acos(a_) if b_>=0 else 2*math.pi-math.acos(a_) + return Line(alpha,-c_) - def computeAngle(self,line): - ab=self.a-self.b - cd=line.a-line.b - alpha=math.atan(ab.y/ab.x) - gamma=math.atan(cd.y/cd.x) - fi=max(alpha,gamma)-min(alpha,gamma) - return min(fi,math.pi-fi) + @staticmethod + def fromPoints(a,b): + return Line.fromNormal(a.y-b.y, b.x-a.x, (b.y-a.y)*a.x+(a.x-b.x)*a.y) + + def toNormal(self): + # https://en.wikipedia.org/wiki/Line_(mathematics)#In_normal_form + """ax + by + c = 0""" + return (self._cos, self._sin, -self._d) def intersect(self,line): - p=self.toProjective() - q=line.toProjective() - return EPoint.fromProjective(np.cross(p,q)) - - def toProjective(self): - return homogenize(np.cross(self.a.toProjective(),self.b.toProjective())) - - def transform(self,matrix): - a=EPoint.fromProjective(transformPoint(self.a.toProjective(),matrix)) - b=EPoint.fromProjective(transformPoint(self.b.toProjective(),matrix)) - if a is None or b is None: return None - return Line(a,b) + if self._alpha==line._alpha: return None + (a,b,c)=self.toNormal() + (d,e,f)=line.toNormal() + x=(b*f-c*e)/(a*e-b*d) + y=(c*d-a*f)/(a*e-b*d) + return EPoint(x,y) - def score(self,points): - score=len(self.points) - for a in self.points: - closest=sorted(points,key=lambda b: a.dist(b))[:4] - score+=sum(0.01 for b in closest if b in self.points) - return score + def distanceTo(self,point): + # https://en.wikipedia.org/wiki/Point-line_distance#Line_defined_by_an_equation + (a,b,c)=self.toNormal() + return abs(a*point.x+b*point.y+c) # a**2 + b**2 == 1 for Hesse normal form - def __str__(self): return "({0},{1})".format(self.a,self.b) - def __repr__(self): return "Line({0},{1})".format(repr(self.a),repr(self.b)) - - -def point2lineDistance(a,b,p): - # https://en.wikipedia.org/wiki/Point-line_distance#Line_defined_by_two_points - ab=b-a - num=abs(ab.y*p.x - ab.x*p.y + b.x*a.y - a.x*b.y) - denum=math.sqrt(ab.y**2+ab.x**2) - return num/denum # double_area / side_length == height + def __str__(self): return "({0},{1})".format(self._alpha,self._d) + def __repr__(self): return "Line({0},{1})".format(repr(self._alpha),repr(self._d)) def angleDiff(alpha,beta): diff --git a/exp/tests/__init__.py b/exp/tests/__init__.py new file mode 100644 diff --git a/exp/tests/test_geometry.py b/exp/tests/test_geometry.py new file mode 100644 --- /dev/null +++ b/exp/tests/test_geometry.py @@ -0,0 +1,67 @@ +import math +import random +from unittest import TestCase + +from geometry import Line,EPoint + +random.seed(361) + + +class TestLine(TestCase): + def testFromNormal(self): + p=Line.fromNormal(1,0,-1) # x-1=0 + self.assertEqual(p._alpha,0) + self.assertEqual(p._d,1) + + q=Line.fromNormal(1,1,-2) # x+y-2=0 + self.assertAlmostEqual(q._alpha,math.pi/4) + self.assertAlmostEqual(q._d,math.sqrt(2)) + + r=Line.fromNormal(0,1,1) # y+1=0 + self.assertAlmostEqual(r._alpha,math.pi*3/2) + self.assertEqual(r._d,1) + + def testFromPoints(self): + ab=Line.fromPoints(EPoint(1,3),EPoint(1,-1)) + self.assertEqual(ab._alpha,0) + self.assertEqual(ab._d,1) + + cd=Line.fromPoints(EPoint(0,2),EPoint(-1,3)) + self.assertAlmostEqual(cd._alpha,math.pi/4) + self.assertAlmostEqual(cd._d,math.sqrt(2)) + + ef=Line.fromPoints(EPoint(-2,-1),EPoint(-4,-1)) + self.assertAlmostEqual(ef._alpha,math.pi*3/2) + self.assertEqual(ef._d,1) + + def testIntersect(self): + for i in range(10): + a=EPoint(random.randint(-100,100),random.randint(-100,100)) + b=EPoint(random.randint(-100,100),random.randint(-100,100)) + c=EPoint(random.randint(-100,100),random.randint(-100,100)) + ab=Line.fromPoints(a,b) + ac=Line.fromPoints(a,c) + a_=ab.intersect(ac) + self.assertAlmostEqual(a.x,a_.x) + self.assertAlmostEqual(a.y,a_.y) + + def testDistanceTo(self): + p=Line(0,1) + q=Line(math.pi/4,math.sqrt(2)) + r=Line(math.pi*3/2,1) + + a=EPoint(0,0) + b=EPoint(1,0) + c=EPoint(-1,-1) + + self.assertAlmostEqual(p.distanceTo(a),1) + self.assertAlmostEqual(p.distanceTo(b),0) + self.assertAlmostEqual(p.distanceTo(c),2) + + self.assertAlmostEqual(q.distanceTo(a),math.sqrt(2)) + self.assertAlmostEqual(q.distanceTo(b),math.sqrt(2)/2) + self.assertAlmostEqual(q.distanceTo(c),2*math.sqrt(2)) + + self.assertAlmostEqual(r.distanceTo(a),1) + self.assertAlmostEqual(r.distanceTo(b),1) + self.assertAlmostEqual(r.distanceTo(c),0)