Download code

Jump to: navigation, search

Back to Quickhull_(Python,_arrays)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

quickhull2d.py

 1 # The authors of this work have released all rights to it and placed it
 2 # in the public domain under the Creative Commons CC0 1.0 waiver
 3 # (http://creativecommons.org/publicdomain/zero/1.0/).
 4 # 
 5 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 6 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 7 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 8 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 9 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
10 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
11 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
12 # 
13 # Retrieved from: http://en.literateprograms.org/Quickhull_(Python,_arrays)?oldid=16555
14 
15 from numpy import *
16 
17 link = lambda a,b: concatenate((a,b[1:]))
18 edge = lambda a,b: concatenate(([a],[b]))
19 def qhull(sample):
20     def dome(sample,base): 
21         h, t = base
22         dists = dot(sample-h, dot(((0,-1),(1,0)),(t-h)))
23         outer = repeat(sample, dists>0, 0)
24 
25         if len(outer):
26             pivot = sample[argmax(dists)]
27             return link(dome(outer, edge(h, pivot)),
28                         dome(outer, edge(pivot, t)))
29         else:
30             return base
31     if len(sample) > 2:
32     	axis = sample[:,0]
33     	base = take(sample, [argmin(axis), argmax(axis)], 0)
34     	return link(dome(sample, base),
35                     dome(sample, base[::-1]))
36     else:
37 	return sample
38 
39 if __name__ == "__main__":
40     #sample = 10*array([(x,y) for x in arange(10) for y in arange(10)])
41     sample = 100*random.random((32,2))
42     hull = qhull(sample)
43 	
44     print "%!"
45     print "100 500 translate 2 2 scale 0 0 moveto"
46     print "/tick {moveto 0 2 rlineto 0 -4 rlineto 0 2 rlineto"
47     print "              2 0 rlineto -4 0 rlineto 2 0 rlineto} def"
48     for (x,y) in sample:
49 	print x, y, "tick"
50     print "stroke"
51     print hull[0,0], hull[0,1], "moveto"
52     for (x,y) in hull[1:]:
53 	print x, y, "lineto"
54     print "closepath stroke showpage"


hijacker
hijacker
hijacker
hijacker