1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 package org.dishevelled.piccolo.venn;
25
26 import java.awt.Shape;
27 import java.awt.geom.Area;
28 import java.awt.geom.Point2D;
29 import java.awt.geom.Rectangle2D;
30 import java.util.ArrayList;
31 import java.util.Collection;
32 import java.util.List;
33 import java.util.Random;
34
35 import org.dishevelled.evolve.EvolutionaryAlgorithm;
36 import org.dishevelled.evolve.ExitStrategy;
37 import org.dishevelled.evolve.Fitness;
38 import org.dishevelled.evolve.Mutation;
39 import org.dishevelled.evolve.Recombination;
40 import org.dishevelled.evolve.Selection;
41 import org.dishevelled.evolve.exit.TimeLimitExitStrategy;
42 import org.dishevelled.evolve.impl.EvolutionaryAlgorithmImpl;
43 import org.dishevelled.evolve.recombine.SexualRecombination;
44 import org.dishevelled.evolve.select.FitnessProportionalSelection;
45
46
47
48
49
50
51
52 final class Centers
53 {
54
55 private static final int INDIVIDUALS = 100;
56
57
58 private static final int GENERATIONS = 75;
59
60
61
62
63
64 private Centers()
65 {
66
67 }
68
69
70
71
72
73
74
75
76 static Point2D centerOf(final Shape shape)
77 {
78 return centerOf(shape, new Point2D.Double());
79 }
80
81
82
83
84
85
86
87
88 static Point2D centerOf(final Shape shape, final Point2D center)
89 {
90 if (shape == null)
91 {
92 throw new IllegalArgumentException("shape must not be null");
93 }
94 return centerOf(shape.getBounds2D(), center);
95 }
96
97
98
99
100
101
102
103 static Point2D centerOf(final Rectangle2D rectangle)
104 {
105 return centerOf(rectangle, new Point2D.Double());
106 }
107
108
109
110
111
112
113
114
115 static Point2D centerOf(final Rectangle2D rectangle, final Point2D center)
116 {
117 if (rectangle == null)
118 {
119 throw new IllegalArgumentException("rectangle must not be null");
120 }
121 if (center == null)
122 {
123 throw new IllegalArgumentException("center must not be null");
124 }
125 center.setLocation(rectangle.getCenterX(), rectangle.getCenterY());
126 return center;
127 }
128
129
130
131
132
133
134
135 static Point2D centerOf(final Area area)
136 {
137 return centerOf(area, new Point2D.Double());
138 }
139
140
141
142
143
144
145
146
147 static Point2D centerOf(final Area area, final Point2D center)
148 {
149 if (area == null)
150 {
151 throw new IllegalArgumentException("area must not be null");
152 }
153 return centerOf(area.getBounds2D(), center);
154 }
155
156
157
158
159
160
161
162
163
164 static Point2D centroidOf(final Area area)
165 {
166 return centroidOf(area, new Point2D.Double());
167 }
168
169
170
171
172
173
174
175
176
177
178 static Point2D centroidOf(final Area area, final Point2D centroid)
179 {
180 return centroidOf(area, centroid, new Random());
181 }
182
183
184
185
186
187
188
189
190
191
192
193 static Point2D centroidOf(final Area area, final Point2D centroid, final Random random)
194 {
195 if (area == null)
196 {
197 throw new IllegalArgumentException("area must not be null");
198 }
199 if (centroid == null)
200 {
201 throw new IllegalArgumentException("centroid must not be null");
202 }
203 if (random == null)
204 {
205 throw new IllegalArgumentException("random must not be null");
206 }
207
208 final Rectangle2D bounds = area.getBounds2D();
209 List<Point2D> individuals = new ArrayList<Point2D>(INDIVIDUALS);
210 for (int i = 0; i < INDIVIDUALS; i++)
211 {
212 double x = bounds.getX() + random.nextDouble() * bounds.getWidth();
213 double y = bounds.getY() + random.nextDouble() * bounds.getHeight();
214 individuals.add(new Point2D.Double(x, y));
215 }
216 ExitStrategy<Point2D> exitStrategy = new TimeLimitExitStrategy<Point2D>(GENERATIONS);
217 Selection<Point2D> selection = new FitnessProportionalSelection<Point2D>();
218
219 Recombination<Point2D> recombination = new SexualRecombination<Point2D>()
220 {
221 private double x = 0.0d;
222 private double y = 0.0d;
223
224 @Override
225 public Point2D recombine(final Point2D individual0, final Point2D individual1)
226 {
227 x = (individual0.getX() + individual1.getX()) / 2.0d;
228 y = (individual0.getY() + individual1.getY()) / 2.0d;
229 return new Point2D.Double(x, y);
230 }
231 };
232
233 Mutation<Point2D> mutation = new Mutation<Point2D>()
234 {
235 private double x = 0.0d;
236 private double y = 0.0d;
237
238 @Override
239 public Collection<Point2D> mutate(final Collection<Point2D> recombined)
240 {
241 for (Point2D point : recombined)
242 {
243 x = point.getX() + random.nextDouble() * 2.0d - random.nextDouble() * 2.0d;
244 y = point.getY() + random.nextDouble() * 2.0d - random.nextDouble() * 2.0d;
245 point.setLocation(x, y);
246 }
247 return recombined;
248 }
249 };
250
251 Fitness<Point2D> fitness = new Fitness<Point2D>()
252 {
253 private double leastXDistance;
254 private double leastYDistance;
255 private final Point2D query = new Point2D.Double();
256 private Area vertical;
257 private Area horizontal;
258 private Rectangle2D horizontalBounds;
259 private Rectangle2D verticalBounds;
260 private final Rectangle2D v = new Rectangle2D.Double();
261 private final Rectangle2D h = new Rectangle2D.Double();
262
263
264 @Override
265 public Double score(final Point2D individual)
266 {
267 if (!area.contains(individual))
268 {
269 return Double.valueOf(0.0d);
270 }
271 query.setLocation(individual.getX(), individual.getY());
272
273 v.setRect(query.getX(), bounds.getY(), 1.0d, bounds.getY() + bounds.getHeight());
274 vertical = new Area(v);
275 vertical.intersect(area);
276 verticalBounds = vertical.getBounds2D();
277 leastYDistance = Math.min(Math.abs(query.getY() - verticalBounds.getY()),
278 Math.abs(verticalBounds.getY() + verticalBounds.getHeight() - query.getY()));
279
280 h.setRect(bounds.getX(), query.getY(), bounds.getX() + bounds.getWidth(), 1.0d);
281 horizontal = new Area(h);
282 horizontal.intersect(area);
283 horizontalBounds = horizontal.getBounds2D();
284 leastXDistance = Math.min(Math.abs(query.getX() - horizontalBounds.getX()),
285 Math.abs(horizontalBounds.getX() + horizontalBounds.getWidth() - query.getX()));
286
287 return Double.valueOf(leastXDistance + leastYDistance);
288 }
289 };
290
291 double maxFitness = 0.0d;
292 Point2D max = null;
293 EvolutionaryAlgorithm<Point2D> ea = new EvolutionaryAlgorithmImpl<Point2D>();
294 for (Point2D point : ea.evolve(individuals, exitStrategy, recombination, mutation, fitness, selection))
295 {
296 double f = fitness.score(point);
297 if (f > maxFitness)
298 {
299 maxFitness = f;
300 max = point;
301 }
302 }
303 centroid.setLocation(max.getX(), max.getY());
304 return centroid;
305 }
306 }