Файл:GrahamScanDemo.gif

''' Convex Hull Demo (SVG) для Graham's Scan. Сначала используйте этот код для генерации кадров SVG. Затем преобразуйте в растровые изображения и конвертируйте в GIF. '''# размер диапазона N  =  300 поле  =  50def  saveToSVG ( nFrames ,  points ,  firmed ,  trying ):  f  =  open ( 'demo_' + str ( nFrames ) + '.svg' ,  'w' )  f.write ( "<svg xmlns= \" http : //www.w3.org/2000/svg \" version= \" 1.1 \" > \ n " ) для p в точках : f.write ( "<circle cx= \ " " + str ( p [ 0 ] + margin ) + " \" cy = \" " + str ( N - p [ 1 ] + margin ) + " \" r= \" 5 \" fill= \" white \" stroke= \" black \" /> \n " ) для i в диапазоне ( len ( firmed ) - 1 ): f .запись ( "<строка x1= \" " + str ( уст. [ i ][ 0 ] + отступ ) + " \" y1= \" " + str ( N - уст. [ i ][ 1 ] + отступ ) + " \" x2= \" " + str ( уст. [ i + 1 ][ 0 ] + отступ ) + " \" y2= \" " + str ( N - уст. [ i + 1 ][ 1 ] + отступ )                         +  " \" stroke= \" red \" stroke-width= \" 5 \" /> \n " )  for  i  in  range ( len ( trying ) - 1 ):  f . write ( "<line x1= \" "  + str ( trying [ i ][ 0 ] + margin ) +  " \" y1= \" " +  str ( N ​​- trying [ i ][ 1 ] + margin )  + " \" x2= \" "  +  str ( trying [ i + 1 ][ 0 ] + margin )  +  " \" y2= \" "  +  str ( N ​​- trying [ i + 1 ][ 1 ] + margin )  +  " \" stroke= \" blue \" stroke-width= \" 5 \" /> \n " )  f . write ( "</svg> \n " )  f . close ()def  generatePoints ( n ):  импорт  случайных чисел  как  r  r . seed ( 100 )  res  =  []  для  i  в  диапазоне ( n ):  pt  =  [ r . randint ( 0 , N )  для  _  в  [ 0 ,  1 ]]  если  [ pt ]  не  в  res :  res  +=  [ pt ]  вернуть  resdef  norm ( x ,  y ):  return  ( x * x + y * y ) ** .5def  dotProductNormed ( x1 ,  y1 ,  x2 ,  y2 ):  return  ( x1 * x2 + y1 * y2 ) / norm ( x1 ,  y1 ) / norm ( x2 ,  y2 )def  cross ( x1 ,  y1 ,  x2 ,  y2 ):  вернуть  x1 * y2  -  x2 * y1def  graham ( n ,  points ):  если  n < 3 :  return  nframe  =  0 ;  points . sort ( key  =  lambda  x :  x [ 1 ])  first  =  points [ 0 ]  rest  =  points [ 1 :]  rest . сортировка ( ключ  =  лямбда  x :  - dotProductNormed ( x [ 0 ] - баллы [ 0 ][ 0 ],  x [ 1 ] - баллы [ 0 ][ 1 ],  1 ,  0 ))  баллы  =  [ первый ]  +  остаток  стек  =  [ баллы [ 0 ],  баллы [ 1 ]]  saveToSVG ​​( nframe ,  баллы ,  стек ,  [ стек [ - 1 ],  баллы [ 2 ]])  nframe  +=  1  i = 2  пока  i < n :  x0 ,  y0  =  стек [ - 2 ][ 0 ],  стек [ - 2 ][ 1 ]  x1 ,  y1  =  стек [ - 1 ][ 0 ],  стек [ - 1 ][ 1 ]  x2 ,  y2  =  баллы [ i ][ 0 ],  баллы [ i ][ 1 ]  если  крест ( x1 - x0 ,  y1 - y0 ,  x2 - x0 ,  у2 - у0 )< 0 :  стек . pop ()  иначе :  стек  +=  [ points [ i ]]  i += 1  если  i < n :  saveToSVG ​​( nframe ,  points ,  stack ,  [ stack [ - 1 ],  points [ i ]])  иначе :  saveToSVG ​​( nframe ,  points ,  stack + [ points [ 0 ]],  [])  nframe  +=  1  вернуть  стек# тест 30 баллов временно n  =  30 баллов  =  generatePoints ( n ) graham ( n ,  pts )