View Javadoc

1   /*
2   
3       dsh-piccolo-venn  Piccolo2D venn diagram nodes and supporting classes.
4       Copyright (c) 2009-2013 held jointly by the individual authors.
5   
6       This library is free software; you can redistribute it and/or modify it
7       under the terms of the GNU Lesser General Public License as published
8       by the Free Software Foundation; either version 3 of the License, or (at
9       your option) any later version.
10  
11      This library is distributed in the hope that it will be useful, but WITHOUT
12      ANY WARRANTY; with out even the implied warranty of MERCHANTABILITY or
13      FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
14      License for more details.
15  
16      You should have received a copy of the GNU Lesser General Public License
17      along with this library;  if not, write to the Free Software Foundation,
18      Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA.
19  
20      > http://www.fsf.org/licensing/licenses/lgpl.html
21      > http://www.opensource.org/licenses/lgpl-license.php
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   * Utility methods for finding the center of areas.
48   *
49   * @author  Michael Heuer
50   * @version $Revision$ $Date$
51   */
52  final class Centers
53  {
54      /** Number of individuals, <code>100</code>. */
55      private static final int INDIVIDUALS = 100;
56  
57      /** Time limit in generations, <code>75</code>. */
58      private static final int GENERATIONS = 75;
59  
60  
61      /**
62       * Private no-arg constructor.
63       */
64      private Centers()
65      {
66          // empty
67      }
68  
69  
70      /**
71       * Find and return the center of the specified shape using its bounds rectangle.
72       *
73       * @param shape shape, must not be null
74       * @return the center of the specified shape using its bounds rectangle
75       */
76      static Point2D centerOf(final Shape shape)
77      {
78          return centerOf(shape, new Point2D.Double());
79      }
80  
81      /**
82       * Find and return the specified center of the specified shape using its bounds rectangle.
83       *
84       * @param shape shape, must not be null
85       * @param center center, must not be null
86       * @return the specified center of the specified shape using its bounds rectangle
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       * Find and return the center of the specified rectangle.
99       *
100      * @param rectangle rectangle, must not be null
101      * @return the center of the specified rectangle
102      */
103     static Point2D centerOf(final Rectangle2D rectangle)
104     {
105         return centerOf(rectangle, new Point2D.Double());
106     }
107 
108     /**
109      * Find and return the specified center of the specified rectangle.
110      *
111      * @param rectangle rectangle, must not be null
112      * @param center center, must not be null
113      * @return the specified center of the specified rectangle
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      * Find and return the center of the specified area using its bounds rectangle.
131      *
132      * @param area area, must not be null
133      * @return the center of the specified area using its bounds rectangle
134      */
135     static Point2D centerOf(final Area area)
136     {
137         return centerOf(area, new Point2D.Double());
138     }
139 
140     /**
141      * Find and return the specified center of the specified area using its bounds rectangle.
142      *
143      * @param area area, must not be null
144      * @param center center, must not be null
145      * @return the specified center of the specified area using its bounds rectangle
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      * Find and return an approximate centroid of the specified area using
158      * an evolutionary algorithm.
159      *
160      * @param area area, must not be null
161      * @return an approximate centroid of the specified area using an
162      *    evolutionary algorithm
163      */
164     static Point2D centroidOf(final Area area)
165     {
166         return centroidOf(area, new Point2D.Double());
167     }
168 
169     /**
170      * Find and return the specified approximate centroid of the specified area using
171      * an evolutionary algorithm.
172      *
173      * @param area area, must not be null
174      * @param centroid centroid, must not be null
175      * @return the specified approximate centroid of the specified area using an
176      *    evolutionary algorithm
177      */
178     static Point2D centroidOf(final Area area, final Point2D centroid)
179     {
180         return centroidOf(area, centroid, new Random());
181     }
182 
183     /**
184      * Find and return the specified approximate centroid of the specified area using
185      * an evolutionary algorithm.
186      *
187      * @param area area, must not be null
188      * @param centroid centroid, must not be null
189      * @param random source of randomness
190      * @return the specified approximate centroid of the specified area using an
191      *    evolutionary algorithm
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 }