Added a new setting for controlling the hierarchy levels of the dart
[blender-addons-contrib.git] / object_physics_meadow / best_candidate.py
1 ### BEGIN GPL LICENSE BLOCK #####
2 #
3 #  This program is free software; you can redistribute it and/or
4 #  modify it under the terms of the GNU General Public License
5 #  as published by the Free Software Foundation; either version 2
6 #  of the License, or (at your option) any later version.
7 #
8 #  This program is distributed in the hope that it will be useful,
9 #  but WITHOUT ANY WARRANTY; without even the implied warranty of
10 #  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 #  GNU General Public License for more details.
12 #
13 #  You should have received a copy of the GNU General Public License
14 #  along with this program; if not, write to the Free Software Foundation,
15 #  Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
16 #
17 # ##### END GPL LICENSE BLOCK #####
18
19 # <pep8 compliant>
20
21 from math import *
22 from mathutils import *
23 from mathutils.kdtree import KDTree
24 import random
25
26 # simple uniform distribution for testing
27 def uniform_2D(num, seed, xmin, xmax, ymin, ymax, radius):
28     for i in range(num):
29         yield (random.uniform(xmin, xmax), random.uniform(ymin, ymax))
30
31 # Mitchell's best candidate algorithm
32 def best_candidate_gen(radius, xmin, xmax, ymin, ymax):
33     def best_candidate(k, tree):
34         best_dist = radius * 2.0
35         best = None
36         
37         for i in range(k):
38             candidate = (random.uniform(xmin, xmax), random.uniform(ymin, ymax))
39             
40             npoint, nindex, ndist = tree.find((candidate[0], candidate[1], 0.0))
41             if not nindex:
42                 return (random.uniform(xmin, xmax), random.uniform(ymin, ymax))
43             
44             if ndist > best_dist:
45                 best_dist = ndist
46                 best = candidate
47         
48         return best
49     
50     num_candidates = 10
51     
52     def gen(seed, num):
53         random.seed(seed)
54         
55         data = []
56         tree = KDTree(0)
57         tree.balance()
58         for i in range(num):
59             best = best_candidate(num_candidates, tree)
60             if not best:
61                 break
62             yield best
63             
64             data.append((best[0], best[1], 0.0))
65             tree = KDTree(len(data))
66             for i, p in enumerate(data):
67                 tree.insert(p, i)
68             tree.balance()
69
70     return gen