1 package org.opentrafficsim.core.geometry;
2
3 import java.awt.geom.Rectangle2D;
4 import java.io.IOException;
5 import java.io.Serializable;
6 import java.util.ArrayList;
7 import java.util.Collection;
8 import java.util.List;
9
10 /**
11 * Measure the performance of the OTSShape intersection method.
12 * <p>
13 * Copyright (c) 2013-2019 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved. <br>
14 * BSD-style license. See <a href="http://opentrafficsim.org/docs/current/license.html">OpenTrafficSim License</a>.
15 * <p>
16 * @version $Revision$, $LastChangedDate$, by $Author$, initial version Apr 5, 2016 <br>
17 * @author <a href="http://www.tbm.tudelft.nl/averbraeck">Alexander Verbraeck</a>
18 * @author <a href="http://www.tudelft.nl/pknoppers">Peter Knoppers</a>
19 */
20 public final class TestIntersectionPerformance
21 {
22
23 /**
24 * Inaccessible constructor to prevent instantiation of this class.
25 */
26 private TestIntersectionPerformance()
27 {
28 // This class cannot be instantiated
29 }
30
31 /**
32 * Create and return an OTSShape.
33 * @param numVertices int; the number of vertices in the constructed OTSShape
34 * @param r double; double radius of the constructed OTSShape
35 * @param cX double; x-coordinate of the center of the constructed OTSShape
36 * @param cY double; y-coordinate of the center of the constructed OTSShape
37 * @return OTSShape
38 * @throws OTSGeometryException when the number of vertices is less than two, or the radius is 0;
39 */
40 static OTSShape makeNGon(final int numVertices, final double r, final double cX, final double cY)
41 throws OTSGeometryException
42 {
43 OTSPoint3D[] points = new OTSPoint3D[numVertices];
44 for (int i = 0; i < numVertices; i++)
45 {
46 double angle = 2 * Math.PI * i / numVertices;
47 points[i] = new OTSPoint3D(cX + r * Math.sin(angle), cY + r * Math.cos(angle));
48 }
49 return new OTSShape(points);
50 }
51
52 /**
53 * Perform a test.
54 * @param numShapes int; number of shapes to construct
55 * @param numVertices int; number of vertices in each constructed shape
56 * @param desiredHitFraction double; intended fraction of shapes that overlap a randomly selected shape
57 * @param numRuns int; number of runs to execute
58 * @param verbose boolean; if true; print details of each run
59 * @param variant int; variant of the collision tester to use
60 * @return Results; collected statistics of this test
61 * @throws OTSGeometryException when the number of vertices iss less than two
62 */
63 public static Results baseTest(final int numShapes, final int numVertices, final double desiredHitFraction,
64 final int numRuns, final boolean verbose, final int variant) throws OTSGeometryException
65 {
66 Results results = new Results(numShapes, numVertices);
67 if (verbose)
68 {
69 System.out.println("Counting collisions among " + numShapes + " shapes with " + numVertices + " vertices");
70 }
71 for (int run = 0; run < numRuns; run++)
72 {
73 double radius = 19;
74 double dx = 6 * radius / desiredHitFraction / numShapes;
75 Collection<OTSShape> shapes = new ArrayList<OTSShape>();
76 OTS2DSet ots2Dset = new OTS2DSet(new Rectangle2D.Double(-20, -20, dx * numShapes / 2 + 40, 4 * radius), 1);
77 for (int i = 0; i < numShapes; i++)
78 {
79 OTSShape shape = makeNGon(numVertices, radius, i % (numShapes / 2) * dx, i > numShapes / 2 ? radius * 1.5 : 0);
80 shapes.add(shape);
81 ots2Dset.add(shape);
82 }
83 long startMillis = System.currentTimeMillis();
84 int hits = 0;
85 int tests = 0;
86 switch (variant)
87 {
88 case 0:
89 for (OTSShape ref : shapes)
90 {
91 for (OTSShape other : shapes)
92 {
93 tests++;
94 if (ref.intersects(other))
95 {
96 hits++;
97 }
98 }
99 }
100 break;
101
102 case 1:
103 for (OTSShape ref : shapes)
104 {
105 tests += shapes.size();
106 hits += ots2Dset.intersectingShapes(ref).size();
107 }
108 break;
109
110 default:
111 throw new Error("Bad variant: " + variant);
112
113 }
114 long endMillis = System.currentTimeMillis();
115 double duration = 0.001 * (endMillis - startMillis);
116 results.addResult(tests, hits, duration);
117 if (verbose)
118 {
119 System.out.println(results.getResult(results.size() - 1));
120 // System.out.println(String.format(
121 // "tests %d, hits %d, fraction hits %f, time %.3fs %10.4f us/test, total time %fs", tests, hits, 1.0
122 // * hits / tests, duration, 1000000 * duration / tests, duration));
123 }
124 }
125 return results;
126 }
127
128 /**
129 * Measure the performance.
130 * @param args String[]; command line arguments (not used)
131 * @throws OTSGeometryException ...
132 * @throws IOException ...
133 */
134 public static void main(final String[] args) throws OTSGeometryException, IOException
135 {
136 System.out.println("Type return to start ...");
137 System.in.read();
138 final int numEdges = 8000;
139 final int numRuns = 10;
140 for (int variant = 0; variant <= 1; variant++)
141 {
142 System.out.println(Results.getHeader());
143 for (int numVertices : new int[] {10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000})
144 {
145 if (numEdges / numVertices > 2)
146 {
147 System.out.println(
148 baseTest(numEdges / numVertices, numVertices, 0.10, numRuns, false, variant).result(true, false));
149 }
150 }
151 }
152 System.out.println("Finished");
153 }
154
155 /**
156 * Storage for the results of a number of runs with identical numbers of shapes and vertices per shape.
157 */
158 static class Results implements Serializable
159 {
160
161 /** */
162 private static final long serialVersionUID = 20160412L;
163
164 /** Number of shapes constructed. */
165 private final int numShapes;
166
167 /** Number of vertices per shape. */
168 private final int numVertices;
169
170 /** Total execution time for all the tests performed. */
171 private List<Result> stats = new ArrayList<Result>();
172
173 /**
174 * Construct a Results object.
175 * @param numShapes int; number of shapes constructed
176 * @param numVertices int; number of vertices per shape
177 */
178 Results(final int numShapes, final int numVertices)
179 {
180 this.numShapes = numShapes;
181 this.numVertices = numVertices;
182 }
183
184 /**
185 * Add the result of one run.
186 * @param numTests int; number of tests executed
187 * @param numHits int; number of hits detected in <cite>numTests</cite> tests
188 * @param executionTime double; total execution time for <cite>numTests</cite> tests
189 */
190 public void addResult(final int numTests, final int numHits, final double executionTime)
191 {
192 if (this.stats.size() > 0)
193 {
194 if (numTests != this.stats.get(0).getNumTests())
195 {
196 System.err.println(
197 "Number of tests per run changed from " + this.stats.get(0).getNumTests() + " to " + numTests);
198 }
199 if (numHits != this.stats.get(0).getNumHits())
200 {
201 System.err.println(
202 "Number of hits per run changed from " + this.stats.get(0).getNumHits() + " to " + numHits);
203 }
204 }
205 this.stats.add(new Result(numTests, numHits, executionTime));
206 }
207
208 /**
209 * Retrieve the number of shapes used in the tests.
210 * @return int; the number of shapes
211 */
212 public int getNumShapes()
213 {
214 return this.numShapes;
215 }
216
217 /**
218 * Retrieve the number of vertices per shape.
219 * @return int; the number of vertices per shape
220 */
221 public int getNumVertices()
222 {
223 return this.numVertices;
224 }
225
226 /**
227 * Report number of statistics collected.
228 * @return int; the number of samples stored
229 */
230 public final int size()
231 {
232 return this.stats.size();
233 }
234
235 /**
236 * Retrieve the Result object at the specified index.
237 * @param index int; the index of the requested result
238 * @return Result
239 */
240 public final Result getResult(final int index)
241 {
242 return this.stats.get(index);
243 }
244
245 /**
246 * Return the results as a String.
247 * @param removeOutliers boolean; if true; remove highest and lowest values
248 * @param verbose boolean; if true; print some diagnostics on the console
249 * @return String; textual representation of this Results
250 */
251 public String result(final boolean removeOutliers, final boolean verbose)
252 {
253 int minimumSize = removeOutliers ? 4 : 2;
254 if (this.size() <= minimumSize)
255 {
256 return ("Not enough results collected");
257 }
258 // Remove lowest and highest value
259 Result lowestRunTime = this.stats.get(0);
260 Result highestRunTime = lowestRunTime;
261 for (Result sample : this.stats)
262 {
263 double runTime = sample.getExecutionTime();
264 if (runTime < highestRunTime.getExecutionTime())
265 {
266 highestRunTime = sample;
267 }
268 if (runTime > lowestRunTime.getExecutionTime())
269 {
270 lowestRunTime = sample;
271 }
272 }
273 if (verbose)
274 {
275 System.out.println(
276 String.format("Removing lowest (%s) and highest (%s) run times", lowestRunTime, highestRunTime));
277 }
278 this.stats.remove(highestRunTime);
279 this.stats.remove(lowestRunTime);
280 double sumRunTime = 0;
281 double sumRunTimeSquared = 0;
282 int totalTestsPerformed = 0;
283 int totalHits = 0;
284 for (Result sample : this.stats)
285 {
286 double runTime = sample.getExecutionTime();
287 sumRunTime += runTime;
288 sumRunTimeSquared += runTime * runTime;
289 totalTestsPerformed += sample.getNumTests();
290 totalHits += sample.getNumHits();
291 }
292 final double meanRunTime = sumRunTime / size();
293 final double sdevRunTime = Math.sqrt(sumRunTimeSquared - sumRunTime * sumRunTime / size()) / (size() - 1);
294 // System.out.println("mean " + meanRunTime + " sdev " + sdevRunTime);
295 return String.format("%7d | %5d |%9d |%11.4f\u00b5s |%11.4f\u00b5s | " + " %5.2f%% | %6.2f%% |%5d |%8.1fs",
296 this.numShapes, this.numVertices, totalTestsPerformed, 1000000 * sumRunTime / totalTestsPerformed,
297 1000000 * sdevRunTime * size() / totalTestsPerformed, 100 * sdevRunTime / meanRunTime,
298 100.0 * totalHits / totalTestsPerformed, size(), sumRunTime);
299 }
300
301 /**
302 * Return header string that matches the output of the <cite>result</cite> method.
303 * @return String
304 */
305 public static String getHeader()
306 {
307 return "# shapes|# vertices| # tests |mean time/test|sdev time/test|sdev/mean|hit fraction|# runs|total time";
308 }
309
310 /**
311 * Storage for execution time, number of tests and number of hits.
312 */
313 static class Result implements Serializable
314 {
315 /** */
316 private static final long serialVersionUID = 20160400L;
317
318 /** Total execution time. */
319 private final double executionTime;
320
321 /** Number of tests executed in total execution timme. */
322 private final int numTests;
323
324 /** Number of hits found in <cite>numTests</cite> tests. */
325 private final int numHits;
326
327 /**
328 * Construct one Result.
329 * @param numTests int; number of tests executed
330 * @param numHits int; number of hits detected in <cite>numTests</cite> tests
331 * @param executionTime double; total execution time for <cite>numTests</cite> tests
332 */
333 Result(final int numTests, final int numHits, final double executionTime)
334 {
335 this.numTests = numTests;
336 this.numHits = numHits;
337 this.executionTime = executionTime;
338 }
339
340 /**
341 * @return int; the number of tests executed
342 */
343 public final int getNumTests()
344 {
345 return this.numTests;
346 }
347
348 /**
349 * @return int; the number of tests executed
350 */
351 public final int getNumHits()
352 {
353 return this.numHits;
354 }
355
356 /**
357 * @return int; the number of tests executed
358 */
359 public final double getExecutionTime()
360 {
361 return this.executionTime;
362 }
363
364 @Override
365 public final String toString()
366 {
367 return String.format(" | | %8d |%11.4f\u00b5s | | | %6.2f%% |",
368 this.numTests, 1000000 * this.executionTime / this.numTests, 100.0 * this.numHits / this.numTests);
369 }
370 }
371
372 /** {@inheritDoc} */
373 @Override
374 public final String toString()
375 {
376 return "Results [numShapes=" + this.numShapes + ", numVertices=" + this.numVertices + ", stats=" + this.stats + "]";
377 }
378
379 }
380
381 }