1. 寫好程式的介面，只要能夠通過編譯即可
2. 增加測試
3. 執行測試，如果有失敗的測試的話就修改程式，然後回到步驟2
回到我們目前的IsQuadrilateral函數，目前的實作非常簡單，只是檢查傳入的多邊形是否有四個頂點，若是的話就傳回真。現在要來處理其他狀況:長的像四角形的五角形(或更多角)。解法如前篇所說，我們先取多邊形的第一個點做為p0，然後找出最遠的點p1，接著找離p1最遠的點p0。我們把這件工作交給FindFarthestPoint，此函數接受一個點p和一個集合S，傳回在集合S中離p最遠的點。這時我們依照TDD的精神，加上個測試先。testFindFarthestPoint利用我們之前定義好的square，測試離左下角最遠的點是否為右上角。
# 要放到 class TestSequenceFunctions 裡面
def testFindFarthestPoint(self):
self.assertTrue( numpy.array_equal(FindFarthestPoint(numpy.array([0,0]), self.square)[0], numpy.array([1,1])) )
self.assertTrue( numpy.array_equal(FindFarthestPoint(numpy.array([0,2]), self.square)[0], numpy.array([1,0])) )
def FindFarthestPoint(p, polygon):
x = polygon[0,]-p[0]
y = polygon[1,]-p[1]
idx = numpy.argmax(x**2 + y**2)
return polygon[:,idx], idx
好了，雖然繞了些路，終於萬事俱備，可以來寫判斷三角形的函數了。由於我們已經把多邊形切成兩半，各自是兩群連續的點的集合。我們可以想像從p1p2的連線，如果途中有一個凸出的點，p1到p2就會是一個三角形(或者更多角)。我使用CountMiddleVertex來計算一群連續的點之中有幾個凸出的點。這會是一個遞迴函數，先找到最突出的點p3，然後用p3切割線段，然後分別呼叫CountMiddleVertex繼續計算。
# 要放到 class TestSequenceFunctions 裡面
def testCountVertex(self):
self.assertEqual(CountMiddleVertex(self.square2), 1)
self.assertEqual(CountMiddleVertex(self.triangle), 1)
self.assertEqual(CountMiddleVertex(self.square), 2)
self.assertEqual(CountMiddleVertex(self.pentagon1), 3)
self.assertEqual(CountMiddleVertex(self.pentagon2), 3)
self.assertEqual(CountMiddleVertex(self.hexagon), 4)
def CountMiddleVertex(pointset, threshold=0.03):
pointnum = pointset.shape[1]
if pointnum <=2:
return 0
p1 = pointset[:, 0]
p2 = pointset[:, -1]
dist2 = (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
triarea = []
for p in range(pointset.shape[1]):
triarea.append(PolygonArea(numpy.column_stack((p1,p2,pointset[:,p]))))
# 如果最突出的點超過門檻值
if max(triarea)*1.0/dist2 > threshold:
midpoint = triarea.index(max(triarea))
vertexnum = 1 + CountMiddleVertex(pointset[:, 0:midpoint+1])
+ CountMiddleVertex(pointset[:, midpoint:], maxnum-vertexnum);
return 0
CountMiddleVertex測試完成後，我們就利用它來判定三角形吧。更新後的IsQuadrilateral以及完整程式如下。為了讓CountMiddleVertex執行快一些，我加了一個參數maxnum，讓它可以早點結束。
import numpy
import unittest
def PolygonArea(polygon):
x,y = numpy.column_stack((polygon, numpy.array([polygon[0,0],polygon[1,0]])))
return abs((numpy.dot(x[0:-1],y[1:]) - numpy.dot(x[1:],y[0:-1])))/2.0
def FindFarthestPoint(p, polygon):
x = polygon[0,]-p[0]
y = polygon[1,]-p[1]
idx = numpy.argmax(x**2 + y**2)
return polygon[:,idx], idx
def CountMiddleVertex(pointset, maxnum=10, threshold=0.03):
pointnum = pointset.shape[1]
if pointnum <=2:
return 0
p1 = pointset[:, 0]
p2 = pointset[:, -1]
dist2 = (p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1])
triarea = []
for p in range(pointset.shape[1]):
triarea.append(PolygonArea(numpy.column_stack((p1,p2,pointset[:,p]))))
if max(triarea)*1.0/dist2 > threshold:
midpoint = triarea.index(max(triarea))
vertexnum = 1 + CountMiddleVertex(pointset[:, 0:midpoint+1]);
if vertexnum >= maxnum:
return maxnum
return vertexnum + CountMiddleVertex(pointset[:, midpoint:], maxnum-vertexnum);
return 0
def IsQuadrilateral(polygon):
x,y = polygon
if len(x) < 4 or len(x)!=len(y):
return False
p1, p1idx = FindFarthestPoint(polygon[:,0], polygon)
p2, p2idx = FindFarthestPoint(p1, polygon)
if p1idx > p2idx:
p1idx,p2idx = p2idx,p1idx
p1,p2 = p2,p1
if CountMiddleVertex(polygon[:, p1idx:p2idx+1], 2)==1 and \
CountMiddleVertex(numpy.column_stack((polygon[:, p2idx:], polygon[:, :p1idx+1])), 2)==1:
return True
else:
return False
class TestSequenceFunctions(unittest.TestCase):
def setUp(self):
self.triangle = numpy.array( [ (0,10,0),(0,0,10) ] )
self.square = numpy.array( [ (0,1,1,0),(0,0,1,1) ] )
self.square2 = numpy.array( [ (0,0.5,1,0),(0,-0.01,0,1) ] )
self.pentagon1 = numpy.array( [ (0,1,1,0,-1),(0,0,1,1,0.5) ] )
self.pentagon2 = numpy.array( [ (0,1,1,0,-0.01),(0,0,1,1,0.5) ] )
self.pentagon3 = numpy.array( [ (0,1,1,0,-0.21),(0,0,1,1,0.5) ] )
self.hexagon = numpy.array( [ (1,1,0,-1,-1,0),(1,-1,-2,-1,1,2) ] )
def testFindFarthestPoint(self):
self.assertTrue( numpy.array_equal(FindFarthestPoint(numpy.array([0,0]), self.square)[0], numpy.array([1,1])) )
self.assertTrue( numpy.array_equal(FindFarthestPoint(numpy.array([0,2]), self.square)[0], numpy.array([1,0])) )
def testCountVertex(self):
self.assertEqual(CountMiddleVertex(self.square2), 1)
self.assertEqual(CountMiddleVertex(self.triangle), 1)
self.assertEqual(CountMiddleVertex(self.square), 2)
self.assertEqual(CountMiddleVertex(self.pentagon1), 3)
self.assertEqual(CountMiddleVertex(self.pentagon2), 3)
self.assertEqual(CountMiddleVertex(self.hexagon), 4)
def testIsQuadrilateral(self):
self.assertEqual(IsQuadrilateral(self.triangle), False)
self.assertEqual(IsQuadrilateral(self.square), True)
self.assertEqual(IsQuadrilateral(self.pentagon1), False)
self.assertEqual(IsQuadrilateral(self.pentagon2), True)
self.assertEqual(IsQuadrilateral(self.pentagon3), False)
self.assertEqual(IsQuadrilateral(self.hexagon), False)
if __name__ == '__main__':
unittest.main()
