Original file (918 × 324 pixels, file size: 1.06 MB, MIME type: image/gif, looped, 61 frames, 49 s)
This is a file from the
Wikimedia Commons. Information from its
description page there is shown below. Commons is a freely licensed media file repository. You can help. |
DescriptionChanAlgDemo.gif |
English: A demo of Chan's algorithm to find a 2D convex hull. |
Date | |
Source | Own work |
Author | Shiyu Ji |
'''
Convex Hull Demo (SVG) for Chan's algorithm.
Firstly use this code to generate SVG frames.
Then transform to bitmaps and convert to GIF.
'''
# range size
N, M = 300, 900
margin = 20
def saveToSVG(nFrames, points, partitions, firmed, trying):
f = open('demo_'+'0'*(3-len(str(nFrames)))+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(p0+margin)+ "\" cy=\""+ str(N-p1+margin) +"\" r=\"5\" fill=\"white\" stroke=\"black\"/>\n")
for par in partitions:
for i in range(len(par)-1):
f.write("<line x1=\"" +str(pari][0+margin)+ "\" y1=\""+ str(N-pari][1+margin) +"\" x2=\"" + str(pari+1][0+margin) + "\" y2=\"" + str(N-pari+1][1+margin) + "\" stroke=\"grey\" stroke-width=\"3\"/>\n")
f.write("<line x1=\"" +str(par-1][0+margin)+ "\" y1=\""+ str(N-par-1][1+margin) +"\" x2=\"" + str(par0][0+margin) + "\" y2=\"" + str(N-par0][1+margin) + "\" stroke=\"grey\" stroke-width=\"3\"/>\n")
for i in range(len(firmed)-1):
f.write("<line x1=\"" +str(firmedi][0+margin)+ "\" y1=\""+ str(N-firmedi][1+margin) +"\" x2=\"" + str(firmedi+1][0+margin) + "\" y2=\"" + str(N-firmedi+1][1+margin) + "\" stroke=\"red\" stroke-width=\"5\"/>\n")
for i in range(len(trying)-1):
f.write("<line x1=\"" +str(tryingi][0+margin)+ "\" y1=\""+ str(N-tryingi][1+margin) +"\" x2=\"" + str(tryingi+1][0+margin) + "\" y2=\"" + str(N-tryingi+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,M), r.randint(0,N)]
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
points.sort(key = lambda x: x1])
first = points0
rest = points1:]
rest.sort(key = lambda x: -dotProductNormed(x0-points0][0], x1-points0][1], 1, 0))
points = first + rest
stack = points0], points1]]
i=2
while i<n:
x0, y0 = stack-2][0], stack-2][1
x1, y1 = stack-1][0], stack-1][1
x2, y2 = pointsi][0], pointsi][1
if cross(x1-x0, y1-y0, x2-x0, y2-y0)<0:
stack.pop()
else:
stack += pointsi]]
i+=1
return stack
# TODO: may be improved.
def tangentPoint(t, hull):
n = len(hull)
if t in hull:
for i in range(len(hull)):
if hulli == t:
return hull[(i+1)%n
if cross(hull0][0-t0], hull0][1-t1], hull-1][0-t0], hull-1][1-t1])>=0 and cross(hull1][0-t0], hull1][1-t1], hull0][0-t0], hull0][1-t1])<=0:
return hull0
if cross(hull0][0-t0], hull0][1-t1], hull-1][0-t0], hull-1][1-t1])<=0 and cross(hull-1][0-t0], hull-1][1-t1], hull-2][0-t0], hull-2][1-t1])>=0:
return hull-1
low, high = 1, n-2
while low+1<high:
i = low + (high-low)//2
if cross(hulli][0-t0], hulli][1-t1], hulli-1][0-t0], hulli-1][1-t1])>=0 and cross(hulli+1][0-t0], hulli+1][1-t1], hulli][0-t0], hulli][1-t1])<=0:
return hulli
if cross(hulli][0-t0], hulli][1-t1], hulli-1][0-t0], hulli-1][1-t1])>=0 and cross(hulli+1][0-t0], hulli+1][1-t1], hulli][0-t0], hulli][1-t1])>=0:
if cross(hulli][0-t0], hulli][1-t1], hulllow][0-t0], hulllow][1-t1])<=0:
if cross(hullhigh+1][0-t0], hullhigh+1][1-t1], hullhigh][0-t0], hullhigh][1-t1])>=0 and cross(hullhigh][0-t0], hullhigh][1-t1], hullhigh-1][0-t0], hullhigh-1][1-t1])>=0:
high = i
else: low = i
else: low = i
else:
if cross(hulli][0-t0], hulli][1-t1], hulllow][0-t0], hulllow][1-t1])>=0:
if cross(hulllow+1][0-t0], hulllow+1][1-t1], hulllow][0-t0], hulllow][1-t1])<=0 and cross(hulllow][0-t0], hulllow][1-t1], hulllow-1][0-t0], hulllow-1][1-t1])<=0:
low = i
else: high = i
else: high = i
for i in range(n):
j = (low+i)%n
if cross(hullj][0-t0], hullj][1-t1], hullj-1][0-t0], hullj-1][1-t1])>=0 and cross(hullj+1][0-t0], hullj+1][1-t1], hullj][0-t0], hullj][1-t1])<=0:
return hullj
def javis(s, hulls):
n = len(hulls)
t = s
res = s
nframe = 1
while True:
next_pt = t
for hull in hulls:
p = tangentPoint(t, hull)
saveToSVG(nframe, pts, hulls, res, res-1], p])
nframe+=1
if next_pt == t or cross(p0-t0], p1-t1], next_pt0-t0], next_pt1-t1])>0 :
next_pt = p
if next_pt == s:
res += s
break
else:
t = next_pt
res += next_pt
saveToSVG(nframe, pts, hulls, res, [])
nframe+=1
saveToSVG(nframe, pts, hulls, res, [])
return res
# test 120 points temporarily
n = 120
pts = generatePoints(n)
pts.sort(key = lambda x: x0])
nPartition = 4
hulls = []
for i in range(nPartition):
hulls.append(graham(n//nPartition, ptsi*n//nPartition:(i+1)*n//nPartition]))
saveToSVG(0, pts, hulls, [], [])
start = hulls0][0
for hull in hulls:
for pt in hull:
if pt1<start1 or (pt1==start1 and pt0 < start0]):
start = pt
javis(start, hulls)
Click on a date/time to view the file as it appeared at that time.
Date/Time | Thumbnail | Dimensions | User | Comment | |
---|---|---|---|---|---|
current | 12:52, 24 December 2016 | 918 × 324 (1.06 MB) | Shiyu Ji | User created page with UploadWizard |
The following other wikis use this file: