Tập tin:GrahamScanDemo.gif
GrahamScanDemo.gif (344×353 điểm ảnh, kích thước tập tin: 217 kB, kiểu MIME: image/gif, có lặp, 51 khung ảnh, 41 s)
Tập tin này đặt tại kho lưu trữ dùng chung và các dự án khác có thể sử dụng chúng. Lời miêu tả tại trang mô tả tập tin tại đấy được hiển thị dưới đây.
Miêu tả
Miêu tả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. |
Ngày | |
Nguồn gốc | Tác phẩm được tạo bởi người tải lên |
Tác giả | 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)
Giấy phép
Tôi, người giữ bản quyền tác phẩm này, từ đây phát hành nó theo giấy phép sau:
Tập tin này được phát hành theo Giấy phép Creative Commons Ghi công–Chia sẻ tương tự 4.0 Quốc tế.
- Bạn được phép:
- chia sẻ – sao chép, phân phối và chuyển giao tác phẩm
- pha trộn – để chuyển thể tác phẩm
- Theo các điều kiện sau:
- ghi công – Bạn phải ghi lại tác giả và nguồn, liên kết đến giấy phép, và các thay đổi đã được thực hiện, nếu có. Bạn có thể làm các điều trên bằng bất kỳ cách hợp lý nào, miễn sao không ám chỉ rằng người cho giấy phép ủng hộ bạn hay việc sử dụng của bạn.
- chia sẻ tương tự – Nếu bạn biến tấu, biến đổi, hoặc làm tác phẩm khác dựa trên tác phẩm này, bạn chỉ được phép phân phối tác phẩm mới theo giấy phép y hệt hoặc tương thích với tác phẩm gốc.
Khoản mục được tả trong tập tin này
mô tả
Giá trị nào đó không có khoản mục Wikidata
23 12 2016
Lịch sử tập tin
Nhấn vào một ngày/giờ để xem nội dung tập tin tại thời điểm đó.
Ngày/Giờ | Hình nhỏ | Kích cỡ | Thành viên | Miêu tả | |
---|---|---|---|---|---|
hiện | 17:05, ngày 23 tháng 12 năm 2016 | 344×353 (217 kB) | Shiyu Ji | User created page with UploadWizard |
Các trang sử dụng tập tin
Tập tin sau là bản sao của tập tin này (chi tiết):
- Tập tin:GrahamScanDemo.gif tại Wikimedia Commons
Trang sau sử dụng tập tin này: