File:GrahamScanDemo.gif
Wikimedia Commons, 자유로운 미디어 저장소
둘러보기로 이동
검색으로 이동
GrahamScanDemo.gif (344 × 353 픽셀, 파일 크기: 217 KB, MIME 종류: image/gif, 반복됨, 51 프레임, 41 s)
파일 정보
구조화된 데이터
캡션
설명
이 파일이 나타내는 바에 대한 한 줄 설명을 추가합니다
파일 설명
[편집]설명GrahamScanDemo.gif |
English: A demo of Graham's Scan, auto-generated by a Python program. The red lines connect the points in the stack. The blue line connects the observed point with the top of stack. |
날짜 | |
출처 | 자작 |
저자 | Shiyu Ji |
Python 3 Code
[편집]'''
Convex Hull Demo (SVG) for Graham's Scan.
Firstly use this code to generate SVG frames.
Then transform to bitmaps and convert to GIF.
'''
# range size
N = 300
margin = 50
def 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")
for p in points:
f.write("<circle cx=\"" +str(p[0]+margin)+ "\" cy=\""+ str(N-p[1]+margin) +"\" r=\"5\" fill=\"white\" stroke=\"black\"/>\n")
for i in range(len(firmed)-1):
f.write("<line x1=\"" +str(firmed[i][0]+margin)+ "\" y1=\""+ str(N-firmed[i][1]+margin) +"\" x2=\"" + str(firmed[i+1][0]+margin) + "\" y2=\"" + str(N-firmed[i+1][1]+margin) + "\" 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):
import random as r
r.seed(100)
res = []
for i in range(n):
pt = [r.randint(0,N) for _ in [0, 1]]
if [pt] not in res:
res += [pt]
return res
def norm(x, y):
return (x*x+y*y)**.5
def dotProductNormed(x1, y1, x2, y2):
return (x1*x2+y1*y2)/norm(x1, y1)/norm(x2, y2)
def cross(x1, y1, x2, y2):
return x1*y2 - x2*y1
def graham(n, points):
if n<3: return
nframe = 0;
points.sort(key = lambda x: x[1])
first = points[0]
rest = points[1:]
rest.sort(key = lambda x: -dotProductNormed(x[0]-points[0][0], x[1]-points[0][1], 1, 0))
points = [first] + rest
stack = [points[0], points[1]]
saveToSVG(nframe, points, stack, [stack[-1], points[2]])
nframe += 1
i=2
while i<n:
x0, y0 = stack[-2][0], stack[-2][1]
x1, y1 = stack[-1][0], stack[-1][1]
x2, y2 = points[i][0], points[i][1]
if cross(x1-x0, y1-y0, x2-x0, y2-y0)<0:
stack.pop()
else:
stack += [points[i]]
i+=1
if i<n:
saveToSVG(nframe, points, stack, [stack[-1], points[i]])
else:
saveToSVG(nframe, points, stack+[points[0]], [])
nframe += 1
return stack
# test 30 points temporarily
n = 30
pts = generatePoints(n)
graham(n, pts)
라이선스
[편집]나는 아래 작품의 저작권자로서, 이 저작물을 다음과 같은 라이선스로 배포합니다:
![w:ko:크리에이티브 커먼즈](https://upload.wikimedia.org/wikipedia/commons/thumb/7/79/CC_some_rights_reserved.svg/90px-CC_some_rights_reserved.svg.png)
![저작자표시](https://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Cc-by_new_white.svg/24px-Cc-by_new_white.svg.png)
![동일조건변경허락](https://upload.wikimedia.org/wikipedia/commons/thumb/d/df/Cc-sa_white.svg/24px-Cc-sa_white.svg.png)
이 파일은 크리에이티브 커먼즈 저작자표시-동일조건변경허락 4.0 국제 라이선스로 배포됩니다.
- 이용자는 다음의 권리를 갖습니다:
- 공유 및 이용 – 저작물의 복제, 배포, 전시, 공연 및 공중송신
- 재창작 – 저작물의 개작, 수정, 2차적저작물 창작
- 다음과 같은 조건을 따라야 합니다:
- 저작자표시 – 적절한 저작자 표시를 제공하고, 라이센스에 대한 링크를 제공하고, 변경사항이 있는지를 표시해야 합니다. 당신은 합리적인 방식으로 표시할 수 있지만, 어떤 방식으로든 사용권 허가자가 당신 또는 당신의 사용을 지지하는 방식으로 표시할 수 없습니다.
- 동일조건변경허락 – 만약 당신이 이 저작물을 리믹스 또는 변형하거나 이 저작물을 기반으로 제작하는 경우, 당신은 당신의 기여물을 원저작물과 동일하거나 호환 가능한 라이선스에 따라 배포하여야 합니다.
파일 역사
날짜/시간 링크를 클릭하면 해당 시간의 파일을 볼 수 있습니다.
날짜/시간 | 섬네일 | 크기 | 사용자 | 설명 | |
---|---|---|---|---|---|
현재 | 2016년 12월 23일 (금) 10:05 | ![]() | 344 × 353 (217 KB) | Shiyu Ji (토론 | 기여) | User created page with UploadWizard |
이 파일을 덮어쓸 수 없습니다.
이 파일을 사용하는 문서
다음 문서 1개가 이 파일을 사용하고 있습니다:
이 파일을 사용하고 있는 모든 위키의 문서 목록
다음 위키에서 이 파일을 사용하고 있습니다:
- ca.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- de.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- el.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- en.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- es.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- ja.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- ko.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- ro.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록
- uk.wikipedia.org에서 이 파일을 사용하고 있는 문서 목록