001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.geometry.euclidean.twod;
018
019 import java.util.ArrayList;
020 import java.util.List;
021
022 import org.apache.commons.math3.geometry.euclidean.oned.Interval;
023 import org.apache.commons.math3.geometry.euclidean.oned.IntervalsSet;
024 import org.apache.commons.math3.geometry.euclidean.oned.Vector1D;
025 import org.apache.commons.math3.geometry.partitioning.BSPTree;
026 import org.apache.commons.math3.geometry.partitioning.Region;
027 import org.apache.commons.math3.geometry.partitioning.Region.Location;
028 import org.apache.commons.math3.geometry.partitioning.RegionFactory;
029 import org.apache.commons.math3.geometry.partitioning.SubHyperplane;
030 import org.apache.commons.math3.util.FastMath;
031 import org.junit.Assert;
032 import org.junit.Test;
033
034 public class PolygonsSetTest {
035
036 @Test
037 public void testSimplyConnected() {
038 Vector2D[][] vertices = new Vector2D[][] {
039 new Vector2D[] {
040 new Vector2D(36.0, 22.0),
041 new Vector2D(39.0, 32.0),
042 new Vector2D(19.0, 32.0),
043 new Vector2D( 6.0, 16.0),
044 new Vector2D(31.0, 10.0),
045 new Vector2D(42.0, 16.0),
046 new Vector2D(34.0, 20.0),
047 new Vector2D(29.0, 19.0),
048 new Vector2D(23.0, 22.0),
049 new Vector2D(33.0, 25.0)
050 }
051 };
052 PolygonsSet set = buildSet(vertices);
053 Assert.assertEquals(Region.Location.OUTSIDE, set.checkPoint(new Vector2D(50.0, 30.0)));
054 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
055 new Vector2D(30.0, 15.0),
056 new Vector2D(15.0, 20.0),
057 new Vector2D(24.0, 25.0),
058 new Vector2D(35.0, 30.0),
059 new Vector2D(19.0, 17.0)
060 });
061 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
062 new Vector2D(50.0, 30.0),
063 new Vector2D(30.0, 35.0),
064 new Vector2D(10.0, 25.0),
065 new Vector2D(10.0, 10.0),
066 new Vector2D(40.0, 10.0),
067 new Vector2D(50.0, 15.0),
068 new Vector2D(30.0, 22.0)
069 });
070 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
071 new Vector2D(30.0, 32.0),
072 new Vector2D(34.0, 20.0)
073 });
074 checkVertices(set.getVertices(), vertices);
075 }
076
077 @Test
078 public void testStair() {
079 Vector2D[][] vertices = new Vector2D[][] {
080 new Vector2D[] {
081 new Vector2D( 0.0, 0.0),
082 new Vector2D( 0.0, 2.0),
083 new Vector2D(-0.1, 2.0),
084 new Vector2D(-0.1, 1.0),
085 new Vector2D(-0.3, 1.0),
086 new Vector2D(-0.3, 1.5),
087 new Vector2D(-1.3, 1.5),
088 new Vector2D(-1.3, 2.0),
089 new Vector2D(-1.8, 2.0),
090 new Vector2D(-1.8 - 1.0 / FastMath.sqrt(2.0),
091 2.0 - 1.0 / FastMath.sqrt(2.0))
092 }
093 };
094
095 PolygonsSet set = buildSet(vertices);
096 checkVertices(set.getVertices(), vertices);
097
098 Assert.assertEquals(1.1 + 0.95 * FastMath.sqrt(2.0), set.getSize(), 1.0e-10);
099
100 }
101
102 @Test
103 public void testHole() {
104 Vector2D[][] vertices = new Vector2D[][] {
105 new Vector2D[] {
106 new Vector2D(0.0, 0.0),
107 new Vector2D(3.0, 0.0),
108 new Vector2D(3.0, 3.0),
109 new Vector2D(0.0, 3.0)
110 }, new Vector2D[] {
111 new Vector2D(1.0, 2.0),
112 new Vector2D(2.0, 2.0),
113 new Vector2D(2.0, 1.0),
114 new Vector2D(1.0, 1.0)
115 }
116 };
117 PolygonsSet set = buildSet(vertices);
118 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
119 new Vector2D(0.5, 0.5),
120 new Vector2D(1.5, 0.5),
121 new Vector2D(2.5, 0.5),
122 new Vector2D(0.5, 1.5),
123 new Vector2D(2.5, 1.5),
124 new Vector2D(0.5, 2.5),
125 new Vector2D(1.5, 2.5),
126 new Vector2D(2.5, 2.5),
127 new Vector2D(0.5, 1.0)
128 });
129 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
130 new Vector2D(1.5, 1.5),
131 new Vector2D(3.5, 1.0),
132 new Vector2D(4.0, 1.5),
133 new Vector2D(6.0, 6.0)
134 });
135 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
136 new Vector2D(1.0, 1.0),
137 new Vector2D(1.5, 0.0),
138 new Vector2D(1.5, 1.0),
139 new Vector2D(1.5, 2.0),
140 new Vector2D(1.5, 3.0),
141 new Vector2D(3.0, 3.0)
142 });
143 checkVertices(set.getVertices(), vertices);
144 }
145
146 @Test
147 public void testDisjointPolygons() {
148 Vector2D[][] vertices = new Vector2D[][] {
149 new Vector2D[] {
150 new Vector2D(0.0, 1.0),
151 new Vector2D(2.0, 1.0),
152 new Vector2D(1.0, 2.0)
153 }, new Vector2D[] {
154 new Vector2D(4.0, 0.0),
155 new Vector2D(5.0, 1.0),
156 new Vector2D(3.0, 1.0)
157 }
158 };
159 PolygonsSet set = buildSet(vertices);
160 Assert.assertEquals(Region.Location.INSIDE, set.checkPoint(new Vector2D(1.0, 1.5)));
161 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
162 new Vector2D(1.0, 1.5),
163 new Vector2D(4.5, 0.8)
164 });
165 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
166 new Vector2D(1.0, 0.0),
167 new Vector2D(3.5, 1.2),
168 new Vector2D(2.5, 1.0),
169 new Vector2D(3.0, 4.0)
170 });
171 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
172 new Vector2D(1.0, 1.0),
173 new Vector2D(3.5, 0.5),
174 new Vector2D(0.0, 1.0)
175 });
176 checkVertices(set.getVertices(), vertices);
177 }
178
179 @Test
180 public void testOppositeHyperplanes() {
181 Vector2D[][] vertices = new Vector2D[][] {
182 new Vector2D[] {
183 new Vector2D(1.0, 0.0),
184 new Vector2D(2.0, 1.0),
185 new Vector2D(3.0, 1.0),
186 new Vector2D(2.0, 2.0),
187 new Vector2D(1.0, 1.0),
188 new Vector2D(0.0, 1.0)
189 }
190 };
191 PolygonsSet set = buildSet(vertices);
192 checkVertices(set.getVertices(), vertices);
193 }
194
195 @Test
196 public void testSingularPoint() {
197 Vector2D[][] vertices = new Vector2D[][] {
198 new Vector2D[] {
199 new Vector2D( 0.0, 0.0),
200 new Vector2D( 1.0, 0.0),
201 new Vector2D( 1.0, 1.0),
202 new Vector2D( 0.0, 1.0),
203 new Vector2D( 0.0, 0.0),
204 new Vector2D(-1.0, 0.0),
205 new Vector2D(-1.0, -1.0),
206 new Vector2D( 0.0, -1.0)
207 }
208 };
209 PolygonsSet set = buildSet(vertices);
210 checkVertices(set.getVertices(), vertices);
211 }
212
213 @Test
214 public void testLineIntersection() {
215 Vector2D[][] vertices = new Vector2D[][] {
216 new Vector2D[] {
217 new Vector2D( 0.0, 0.0),
218 new Vector2D( 2.0, 0.0),
219 new Vector2D( 2.0, 1.0),
220 new Vector2D( 3.0, 1.0),
221 new Vector2D( 3.0, 3.0),
222 new Vector2D( 1.0, 3.0),
223 new Vector2D( 1.0, 2.0),
224 new Vector2D( 0.0, 2.0)
225 }
226 };
227 PolygonsSet set = buildSet(vertices);
228
229 Line l1 = new Line(new Vector2D(-1.5, 0.0), FastMath.PI / 4);
230 SubLine s1 = (SubLine) set.intersection(l1.wholeHyperplane());
231 List<Interval> i1 = ((IntervalsSet) s1.getRemainingRegion()).asList();
232 Assert.assertEquals(2, i1.size());
233 Interval v10 = i1.get(0);
234 Vector2D p10Lower = l1.toSpace(new Vector1D(v10.getInf()));
235 Assert.assertEquals(0.0, p10Lower.getX(), 1.0e-10);
236 Assert.assertEquals(1.5, p10Lower.getY(), 1.0e-10);
237 Vector2D p10Upper = l1.toSpace(new Vector1D(v10.getSup()));
238 Assert.assertEquals(0.5, p10Upper.getX(), 1.0e-10);
239 Assert.assertEquals(2.0, p10Upper.getY(), 1.0e-10);
240 Interval v11 = i1.get(1);
241 Vector2D p11Lower = l1.toSpace(new Vector1D(v11.getInf()));
242 Assert.assertEquals(1.0, p11Lower.getX(), 1.0e-10);
243 Assert.assertEquals(2.5, p11Lower.getY(), 1.0e-10);
244 Vector2D p11Upper = l1.toSpace(new Vector1D(v11.getSup()));
245 Assert.assertEquals(1.5, p11Upper.getX(), 1.0e-10);
246 Assert.assertEquals(3.0, p11Upper.getY(), 1.0e-10);
247
248 Line l2 = new Line(new Vector2D(-1.0, 2.0), 0);
249 SubLine s2 = (SubLine) set.intersection(l2.wholeHyperplane());
250 List<Interval> i2 = ((IntervalsSet) s2.getRemainingRegion()).asList();
251 Assert.assertEquals(1, i2.size());
252 Interval v20 = i2.get(0);
253 Vector2D p20Lower = l2.toSpace(new Vector1D(v20.getInf()));
254 Assert.assertEquals(1.0, p20Lower.getX(), 1.0e-10);
255 Assert.assertEquals(2.0, p20Lower.getY(), 1.0e-10);
256 Vector2D p20Upper = l2.toSpace(new Vector1D(v20.getSup()));
257 Assert.assertEquals(3.0, p20Upper.getX(), 1.0e-10);
258 Assert.assertEquals(2.0, p20Upper.getY(), 1.0e-10);
259
260 }
261
262 @Test
263 public void testUnlimitedSubHyperplane() {
264 Vector2D[][] vertices1 = new Vector2D[][] {
265 new Vector2D[] {
266 new Vector2D(0.0, 0.0),
267 new Vector2D(4.0, 0.0),
268 new Vector2D(1.4, 1.5),
269 new Vector2D(0.0, 3.5)
270 }
271 };
272 PolygonsSet set1 = buildSet(vertices1);
273 Vector2D[][] vertices2 = new Vector2D[][] {
274 new Vector2D[] {
275 new Vector2D(1.4, 0.2),
276 new Vector2D(2.8, -1.2),
277 new Vector2D(2.5, 0.6)
278 }
279 };
280 PolygonsSet set2 = buildSet(vertices2);
281
282 PolygonsSet set =
283 (PolygonsSet) new RegionFactory<Euclidean2D>().union(set1.copySelf(),
284 set2.copySelf());
285 checkVertices(set1.getVertices(), vertices1);
286 checkVertices(set2.getVertices(), vertices2);
287 checkVertices(set.getVertices(), new Vector2D[][] {
288 new Vector2D[] {
289 new Vector2D(0.0, 0.0),
290 new Vector2D(1.6, 0.0),
291 new Vector2D(2.8, -1.2),
292 new Vector2D(2.6, 0.0),
293 new Vector2D(4.0, 0.0),
294 new Vector2D(1.4, 1.5),
295 new Vector2D(0.0, 3.5)
296 }
297 });
298
299 }
300
301 @Test
302 public void testUnion() {
303 Vector2D[][] vertices1 = new Vector2D[][] {
304 new Vector2D[] {
305 new Vector2D( 0.0, 0.0),
306 new Vector2D( 2.0, 0.0),
307 new Vector2D( 2.0, 2.0),
308 new Vector2D( 0.0, 2.0)
309 }
310 };
311 PolygonsSet set1 = buildSet(vertices1);
312 Vector2D[][] vertices2 = new Vector2D[][] {
313 new Vector2D[] {
314 new Vector2D( 1.0, 1.0),
315 new Vector2D( 3.0, 1.0),
316 new Vector2D( 3.0, 3.0),
317 new Vector2D( 1.0, 3.0)
318 }
319 };
320 PolygonsSet set2 = buildSet(vertices2);
321 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().union(set1.copySelf(),
322 set2.copySelf());
323 checkVertices(set1.getVertices(), vertices1);
324 checkVertices(set2.getVertices(), vertices2);
325 checkVertices(set.getVertices(), new Vector2D[][] {
326 new Vector2D[] {
327 new Vector2D( 0.0, 0.0),
328 new Vector2D( 2.0, 0.0),
329 new Vector2D( 2.0, 1.0),
330 new Vector2D( 3.0, 1.0),
331 new Vector2D( 3.0, 3.0),
332 new Vector2D( 1.0, 3.0),
333 new Vector2D( 1.0, 2.0),
334 new Vector2D( 0.0, 2.0)
335 }
336 });
337 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
338 new Vector2D(1.0, 1.0),
339 new Vector2D(0.5, 0.5),
340 new Vector2D(2.0, 2.0),
341 new Vector2D(2.5, 2.5),
342 new Vector2D(0.5, 1.5),
343 new Vector2D(1.5, 1.5),
344 new Vector2D(1.5, 0.5),
345 new Vector2D(1.5, 2.5),
346 new Vector2D(2.5, 1.5),
347 new Vector2D(2.5, 2.5)
348 });
349 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
350 new Vector2D(-0.5, 0.5),
351 new Vector2D( 0.5, 2.5),
352 new Vector2D( 2.5, 0.5),
353 new Vector2D( 3.5, 2.5)
354 });
355 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
356 new Vector2D(0.0, 0.0),
357 new Vector2D(0.5, 2.0),
358 new Vector2D(2.0, 0.5),
359 new Vector2D(2.5, 1.0),
360 new Vector2D(3.0, 2.5)
361 });
362
363 }
364
365 @Test
366 public void testIntersection() {
367 Vector2D[][] vertices1 = new Vector2D[][] {
368 new Vector2D[] {
369 new Vector2D( 0.0, 0.0),
370 new Vector2D( 2.0, 0.0),
371 new Vector2D( 2.0, 2.0),
372 new Vector2D( 0.0, 2.0)
373 }
374 };
375 PolygonsSet set1 = buildSet(vertices1);
376 Vector2D[][] vertices2 = new Vector2D[][] {
377 new Vector2D[] {
378 new Vector2D( 1.0, 1.0),
379 new Vector2D( 3.0, 1.0),
380 new Vector2D( 3.0, 3.0),
381 new Vector2D( 1.0, 3.0)
382 }
383 };
384 PolygonsSet set2 = buildSet(vertices2);
385 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().intersection(set1.copySelf(),
386 set2.copySelf());
387 checkVertices(set1.getVertices(), vertices1);
388 checkVertices(set2.getVertices(), vertices2);
389 checkVertices(set.getVertices(), new Vector2D[][] {
390 new Vector2D[] {
391 new Vector2D( 1.0, 1.0),
392 new Vector2D( 2.0, 1.0),
393 new Vector2D( 2.0, 2.0),
394 new Vector2D( 1.0, 2.0)
395 }
396 });
397 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
398 new Vector2D(1.5, 1.5)
399 });
400 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
401 new Vector2D(0.5, 1.5),
402 new Vector2D(2.5, 1.5),
403 new Vector2D(1.5, 0.5),
404 new Vector2D(0.5, 0.5)
405 });
406 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
407 new Vector2D(1.0, 1.0),
408 new Vector2D(2.0, 2.0),
409 new Vector2D(1.0, 1.5),
410 new Vector2D(1.5, 2.0)
411 });
412 }
413
414 @Test
415 public void testXor() {
416 Vector2D[][] vertices1 = new Vector2D[][] {
417 new Vector2D[] {
418 new Vector2D( 0.0, 0.0),
419 new Vector2D( 2.0, 0.0),
420 new Vector2D( 2.0, 2.0),
421 new Vector2D( 0.0, 2.0)
422 }
423 };
424 PolygonsSet set1 = buildSet(vertices1);
425 Vector2D[][] vertices2 = new Vector2D[][] {
426 new Vector2D[] {
427 new Vector2D( 1.0, 1.0),
428 new Vector2D( 3.0, 1.0),
429 new Vector2D( 3.0, 3.0),
430 new Vector2D( 1.0, 3.0)
431 }
432 };
433 PolygonsSet set2 = buildSet(vertices2);
434 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().xor(set1.copySelf(),
435 set2.copySelf());
436 checkVertices(set1.getVertices(), vertices1);
437 checkVertices(set2.getVertices(), vertices2);
438 checkVertices(set.getVertices(), new Vector2D[][] {
439 new Vector2D[] {
440 new Vector2D( 0.0, 0.0),
441 new Vector2D( 2.0, 0.0),
442 new Vector2D( 2.0, 1.0),
443 new Vector2D( 3.0, 1.0),
444 new Vector2D( 3.0, 3.0),
445 new Vector2D( 1.0, 3.0),
446 new Vector2D( 1.0, 2.0),
447 new Vector2D( 0.0, 2.0)
448 },
449 new Vector2D[] {
450 new Vector2D( 1.0, 1.0),
451 new Vector2D( 1.0, 2.0),
452 new Vector2D( 2.0, 2.0),
453 new Vector2D( 2.0, 1.0)
454 }
455 });
456 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
457 new Vector2D(0.5, 0.5),
458 new Vector2D(2.5, 2.5),
459 new Vector2D(0.5, 1.5),
460 new Vector2D(1.5, 0.5),
461 new Vector2D(1.5, 2.5),
462 new Vector2D(2.5, 1.5),
463 new Vector2D(2.5, 2.5)
464 });
465 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
466 new Vector2D(-0.5, 0.5),
467 new Vector2D( 0.5, 2.5),
468 new Vector2D( 2.5, 0.5),
469 new Vector2D( 1.5, 1.5),
470 new Vector2D( 3.5, 2.5)
471 });
472 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
473 new Vector2D(1.0, 1.0),
474 new Vector2D(2.0, 2.0),
475 new Vector2D(1.5, 1.0),
476 new Vector2D(2.0, 1.5),
477 new Vector2D(0.0, 0.0),
478 new Vector2D(0.5, 2.0),
479 new Vector2D(2.0, 0.5),
480 new Vector2D(2.5, 1.0),
481 new Vector2D(3.0, 2.5)
482 });
483 }
484
485 @Test
486 public void testDifference() {
487 Vector2D[][] vertices1 = new Vector2D[][] {
488 new Vector2D[] {
489 new Vector2D( 0.0, 0.0),
490 new Vector2D( 2.0, 0.0),
491 new Vector2D( 2.0, 2.0),
492 new Vector2D( 0.0, 2.0)
493 }
494 };
495 PolygonsSet set1 = buildSet(vertices1);
496 Vector2D[][] vertices2 = new Vector2D[][] {
497 new Vector2D[] {
498 new Vector2D( 1.0, 1.0),
499 new Vector2D( 3.0, 1.0),
500 new Vector2D( 3.0, 3.0),
501 new Vector2D( 1.0, 3.0)
502 }
503 };
504 PolygonsSet set2 = buildSet(vertices2);
505 PolygonsSet set = (PolygonsSet) new RegionFactory<Euclidean2D>().difference(set1.copySelf(),
506 set2.copySelf());
507 checkVertices(set1.getVertices(), vertices1);
508 checkVertices(set2.getVertices(), vertices2);
509 checkVertices(set.getVertices(), new Vector2D[][] {
510 new Vector2D[] {
511 new Vector2D( 0.0, 0.0),
512 new Vector2D( 2.0, 0.0),
513 new Vector2D( 2.0, 1.0),
514 new Vector2D( 1.0, 1.0),
515 new Vector2D( 1.0, 2.0),
516 new Vector2D( 0.0, 2.0)
517 }
518 });
519 checkPoints(Region.Location.INSIDE, set, new Vector2D[] {
520 new Vector2D(0.5, 0.5),
521 new Vector2D(0.5, 1.5),
522 new Vector2D(1.5, 0.5)
523 });
524 checkPoints(Region.Location.OUTSIDE, set, new Vector2D[] {
525 new Vector2D( 2.5, 2.5),
526 new Vector2D(-0.5, 0.5),
527 new Vector2D( 0.5, 2.5),
528 new Vector2D( 2.5, 0.5),
529 new Vector2D( 1.5, 1.5),
530 new Vector2D( 3.5, 2.5),
531 new Vector2D( 1.5, 2.5),
532 new Vector2D( 2.5, 1.5),
533 new Vector2D( 2.0, 1.5),
534 new Vector2D( 2.0, 2.0),
535 new Vector2D( 2.5, 1.0),
536 new Vector2D( 2.5, 2.5),
537 new Vector2D( 3.0, 2.5)
538 });
539 checkPoints(Region.Location.BOUNDARY, set, new Vector2D[] {
540 new Vector2D(1.0, 1.0),
541 new Vector2D(1.5, 1.0),
542 new Vector2D(0.0, 0.0),
543 new Vector2D(0.5, 2.0),
544 new Vector2D(2.0, 0.5)
545 });
546 }
547
548 @Test
549 public void testEmptyDifference() {
550 Vector2D[][] vertices1 = new Vector2D[][] {
551 new Vector2D[] {
552 new Vector2D( 0.5, 3.5),
553 new Vector2D( 0.5, 4.5),
554 new Vector2D(-0.5, 4.5),
555 new Vector2D(-0.5, 3.5)
556 }
557 };
558 PolygonsSet set1 = buildSet(vertices1);
559 Vector2D[][] vertices2 = new Vector2D[][] {
560 new Vector2D[] {
561 new Vector2D( 1.0, 2.0),
562 new Vector2D( 1.0, 8.0),
563 new Vector2D(-1.0, 8.0),
564 new Vector2D(-1.0, 2.0)
565 }
566 };
567 PolygonsSet set2 = buildSet(vertices2);
568 Assert.assertTrue(new RegionFactory<Euclidean2D>().difference(set1.copySelf(), set2.copySelf()).isEmpty());
569 }
570
571 @Test
572 public void testChoppedHexagon() {
573 double pi6 = FastMath.PI / 6.0;
574 double sqrt3 = FastMath.sqrt(3.0);
575 SubLine[] hyp = {
576 new Line(new Vector2D( 0.0, 1.0), 5 * pi6).wholeHyperplane(),
577 new Line(new Vector2D(-sqrt3, 1.0), 7 * pi6).wholeHyperplane(),
578 new Line(new Vector2D(-sqrt3, 1.0), 9 * pi6).wholeHyperplane(),
579 new Line(new Vector2D(-sqrt3, 0.0), 11 * pi6).wholeHyperplane(),
580 new Line(new Vector2D( 0.0, 0.0), 13 * pi6).wholeHyperplane(),
581 new Line(new Vector2D( 0.0, 1.0), 3 * pi6).wholeHyperplane(),
582 new Line(new Vector2D(-5.0 * sqrt3 / 6.0, 0.0), 9 * pi6).wholeHyperplane()
583 };
584 hyp[1] = (SubLine) hyp[1].split(hyp[0].getHyperplane()).getMinus();
585 hyp[2] = (SubLine) hyp[2].split(hyp[1].getHyperplane()).getMinus();
586 hyp[3] = (SubLine) hyp[3].split(hyp[2].getHyperplane()).getMinus();
587 hyp[4] = (SubLine) hyp[4].split(hyp[3].getHyperplane()).getMinus().split(hyp[0].getHyperplane()).getMinus();
588 hyp[5] = (SubLine) hyp[5].split(hyp[4].getHyperplane()).getMinus().split(hyp[0].getHyperplane()).getMinus();
589 hyp[6] = (SubLine) hyp[6].split(hyp[3].getHyperplane()).getMinus().split(hyp[1].getHyperplane()).getMinus();
590 BSPTree<Euclidean2D> tree = new BSPTree<Euclidean2D>(Boolean.TRUE);
591 for (int i = hyp.length - 1; i >= 0; --i) {
592 tree = new BSPTree<Euclidean2D>(hyp[i], new BSPTree<Euclidean2D>(Boolean.FALSE), tree, null);
593 }
594 PolygonsSet set = new PolygonsSet(tree);
595 SubLine splitter =
596 new Line(new Vector2D(-2.0 * sqrt3 / 3.0, 0.0), 9 * pi6).wholeHyperplane();
597 PolygonsSet slice =
598 new PolygonsSet(new BSPTree<Euclidean2D>(splitter,
599 set.getTree(false).split(splitter).getPlus(),
600 new BSPTree<Euclidean2D>(Boolean.FALSE), null));
601 Assert.assertEquals(Region.Location.OUTSIDE,
602 slice.checkPoint(new Vector2D(0.1, 0.5)));
603 Assert.assertEquals(11.0 / 3.0, slice.getBoundarySize(), 1.0e-10);
604
605 }
606
607 @Test
608 public void testConcentric() {
609 double h = FastMath.sqrt(3.0) / 2.0;
610 Vector2D[][] vertices1 = new Vector2D[][] {
611 new Vector2D[] {
612 new Vector2D( 0.00, 0.1 * h),
613 new Vector2D( 0.05, 0.1 * h),
614 new Vector2D( 0.10, 0.2 * h),
615 new Vector2D( 0.05, 0.3 * h),
616 new Vector2D(-0.05, 0.3 * h),
617 new Vector2D(-0.10, 0.2 * h),
618 new Vector2D(-0.05, 0.1 * h)
619 }
620 };
621 PolygonsSet set1 = buildSet(vertices1);
622 Vector2D[][] vertices2 = new Vector2D[][] {
623 new Vector2D[] {
624 new Vector2D( 0.00, 0.0 * h),
625 new Vector2D( 0.10, 0.0 * h),
626 new Vector2D( 0.20, 0.2 * h),
627 new Vector2D( 0.10, 0.4 * h),
628 new Vector2D(-0.10, 0.4 * h),
629 new Vector2D(-0.20, 0.2 * h),
630 new Vector2D(-0.10, 0.0 * h)
631 }
632 };
633 PolygonsSet set2 = buildSet(vertices2);
634 Assert.assertTrue(set2.contains(set1));
635 }
636
637 @Test
638 public void testBug20040520() {
639 BSPTree<Euclidean2D> a0 =
640 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.85, -0.05),
641 new Vector2D(0.90, -0.10)),
642 new BSPTree<Euclidean2D>(Boolean.FALSE),
643 new BSPTree<Euclidean2D>(Boolean.TRUE),
644 null);
645 BSPTree<Euclidean2D> a1 =
646 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.85, -0.10),
647 new Vector2D(0.90, -0.10)),
648 new BSPTree<Euclidean2D>(Boolean.FALSE), a0, null);
649 BSPTree<Euclidean2D> a2 =
650 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.90, -0.05),
651 new Vector2D(0.85, -0.05)),
652 new BSPTree<Euclidean2D>(Boolean.FALSE), a1, null);
653 BSPTree<Euclidean2D> a3 =
654 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.82, -0.05),
655 new Vector2D(0.82, -0.08)),
656 new BSPTree<Euclidean2D>(Boolean.FALSE),
657 new BSPTree<Euclidean2D>(Boolean.TRUE),
658 null);
659 BSPTree<Euclidean2D> a4 =
660 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.85, -0.05),
661 new Vector2D(0.80, -0.05),
662 false),
663 new BSPTree<Euclidean2D>(Boolean.FALSE), a3, null);
664 BSPTree<Euclidean2D> a5 =
665 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.82, -0.08),
666 new Vector2D(0.82, -0.18)),
667 new BSPTree<Euclidean2D>(Boolean.FALSE),
668 new BSPTree<Euclidean2D>(Boolean.TRUE),
669 null);
670 BSPTree<Euclidean2D> a6 =
671 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.82, -0.18),
672 new Vector2D(0.85, -0.15),
673 true),
674 new BSPTree<Euclidean2D>(Boolean.FALSE), a5, null);
675 BSPTree<Euclidean2D> a7 =
676 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.85, -0.05),
677 new Vector2D(0.82, -0.08),
678 false),
679 a4, a6, null);
680 BSPTree<Euclidean2D> a8 =
681 new BSPTree<Euclidean2D>(buildLine(new Vector2D(0.85, -0.25),
682 new Vector2D(0.85, 0.05)),
683 a2, a7, null);
684 BSPTree<Euclidean2D> a9 =
685 new BSPTree<Euclidean2D>(buildLine(new Vector2D(0.90, 0.05),
686 new Vector2D(0.90, -0.50)),
687 a8, new BSPTree<Euclidean2D>(Boolean.FALSE), null);
688
689 BSPTree<Euclidean2D> b0 =
690 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.92, -0.12),
691 new Vector2D(0.92, -0.08)),
692 new BSPTree<Euclidean2D>(Boolean.FALSE), new BSPTree<Euclidean2D>(Boolean.TRUE),
693 null);
694 BSPTree<Euclidean2D> b1 =
695 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.92, -0.08),
696 new Vector2D(0.90, -0.10),
697 true),
698 new BSPTree<Euclidean2D>(Boolean.FALSE), b0, null);
699 BSPTree<Euclidean2D> b2 =
700 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.92, -0.18),
701 new Vector2D(0.92, -0.12)),
702 new BSPTree<Euclidean2D>(Boolean.FALSE), new BSPTree<Euclidean2D>(Boolean.TRUE),
703 null);
704 BSPTree<Euclidean2D> b3 =
705 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.85, -0.15),
706 new Vector2D(0.90, -0.20)),
707 new BSPTree<Euclidean2D>(Boolean.FALSE), b2, null);
708 BSPTree<Euclidean2D> b4 =
709 new BSPTree<Euclidean2D>(buildSegment(new Vector2D(0.95, -0.15),
710 new Vector2D(0.85, -0.05)),
711 b1, b3, null);
712 BSPTree<Euclidean2D> b5 =
713 new BSPTree<Euclidean2D>(buildHalfLine(new Vector2D(0.85, -0.05),
714 new Vector2D(0.85, -0.25),
715 true),
716 new BSPTree<Euclidean2D>(Boolean.FALSE), b4, null);
717 BSPTree<Euclidean2D> b6 =
718 new BSPTree<Euclidean2D>(buildLine(new Vector2D(0.0, -1.10),
719 new Vector2D(1.0, -0.10)),
720 new BSPTree<Euclidean2D>(Boolean.FALSE), b5, null);
721
722 PolygonsSet c =
723 (PolygonsSet) new RegionFactory<Euclidean2D>().union(new PolygonsSet(a9),
724 new PolygonsSet(b6));
725
726 checkPoints(Region.Location.INSIDE, c, new Vector2D[] {
727 new Vector2D(0.83, -0.06),
728 new Vector2D(0.83, -0.15),
729 new Vector2D(0.88, -0.15),
730 new Vector2D(0.88, -0.09),
731 new Vector2D(0.88, -0.07),
732 new Vector2D(0.91, -0.18),
733 new Vector2D(0.91, -0.10)
734 });
735
736 checkPoints(Region.Location.OUTSIDE, c, new Vector2D[] {
737 new Vector2D(0.80, -0.10),
738 new Vector2D(0.83, -0.50),
739 new Vector2D(0.83, -0.20),
740 new Vector2D(0.83, -0.02),
741 new Vector2D(0.87, -0.50),
742 new Vector2D(0.87, -0.20),
743 new Vector2D(0.87, -0.02),
744 new Vector2D(0.91, -0.20),
745 new Vector2D(0.91, -0.08),
746 new Vector2D(0.93, -0.15)
747 });
748
749 checkVertices(c.getVertices(),
750 new Vector2D[][] {
751 new Vector2D[] {
752 new Vector2D(0.85, -0.15),
753 new Vector2D(0.90, -0.20),
754 new Vector2D(0.92, -0.18),
755 new Vector2D(0.92, -0.08),
756 new Vector2D(0.90, -0.10),
757 new Vector2D(0.90, -0.05),
758 new Vector2D(0.82, -0.05),
759 new Vector2D(0.82, -0.18),
760 }
761 });
762
763 }
764
765 @Test
766 public void testBug20041003() {
767
768 Line[] l = {
769 new Line(new Vector2D(0.0, 0.625000007541172),
770 new Vector2D(1.0, 0.625000007541172)),
771 new Line(new Vector2D(-0.19204433621902645, 0.0),
772 new Vector2D(-0.19204433621902645, 1.0)),
773 new Line(new Vector2D(-0.40303524786887, 0.4248364535319128),
774 new Vector2D(-1.12851149797877, -0.2634107480798909)),
775 new Line(new Vector2D(0.0, 2.0),
776 new Vector2D(1.0, 2.0))
777 };
778
779 BSPTree<Euclidean2D> node1 =
780 new BSPTree<Euclidean2D>(new SubLine(l[0],
781 new IntervalsSet(intersectionAbscissa(l[0], l[1]),
782 intersectionAbscissa(l[0], l[2]))),
783 new BSPTree<Euclidean2D>(Boolean.TRUE), new BSPTree<Euclidean2D>(Boolean.FALSE),
784 null);
785 BSPTree<Euclidean2D> node2 =
786 new BSPTree<Euclidean2D>(new SubLine(l[1],
787 new IntervalsSet(intersectionAbscissa(l[1], l[2]),
788 intersectionAbscissa(l[1], l[3]))),
789 node1, new BSPTree<Euclidean2D>(Boolean.FALSE), null);
790 BSPTree<Euclidean2D> node3 =
791 new BSPTree<Euclidean2D>(new SubLine(l[2],
792 new IntervalsSet(intersectionAbscissa(l[2], l[3]),
793 Double.POSITIVE_INFINITY)),
794 node2, new BSPTree<Euclidean2D>(Boolean.FALSE), null);
795 BSPTree<Euclidean2D> node4 =
796 new BSPTree<Euclidean2D>(l[3].wholeHyperplane(), node3, new BSPTree<Euclidean2D>(Boolean.FALSE), null);
797
798 PolygonsSet set = new PolygonsSet(node4);
799 Assert.assertEquals(0, set.getVertices().length);
800
801 }
802
803 @Test
804 public void testSqueezedHexa() {
805 PolygonsSet set = new PolygonsSet(1.0e-10,
806 new Vector2D(-6, -4), new Vector2D(-8, -8), new Vector2D( 8, -8),
807 new Vector2D( 6, -4), new Vector2D(10, 4), new Vector2D(-10, 4));
808 Assert.assertEquals(Location.OUTSIDE, set.checkPoint(new Vector2D(0, 6)));
809 }
810
811 @Test
812 public void testIssue880Simplified() {
813
814 Vector2D[] vertices1 = new Vector2D[] {
815 new Vector2D( 90.13595870833188, 38.33604606376991),
816 new Vector2D( 90.14047850603913, 38.34600084496253),
817 new Vector2D( 90.11045289492762, 38.36801537312368),
818 new Vector2D( 90.10871471476526, 38.36878044144294),
819 new Vector2D( 90.10424901707671, 38.374300101757),
820 new Vector2D( 90.0979455456843, 38.373578376172475),
821 new Vector2D( 90.09081227075944, 38.37526295920463),
822 new Vector2D( 90.09081378927135, 38.375193883266434)
823 };
824 PolygonsSet set1 = new PolygonsSet(1.0e-10, vertices1);
825 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.12, 38.32)));
826 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.135, 38.355)));
827
828 }
829
830 @Test
831 public void testIssue880Complete() {
832 Vector2D[] vertices1 = new Vector2D[] {
833 new Vector2D( 90.08714908223715, 38.370299337260235),
834 new Vector2D( 90.08709517675004, 38.3702895991413),
835 new Vector2D( 90.08401538704919, 38.368849330127944),
836 new Vector2D( 90.08258210430711, 38.367634558585564),
837 new Vector2D( 90.08251455106665, 38.36763409247078),
838 new Vector2D( 90.08106599752608, 38.36761621664249),
839 new Vector2D( 90.08249585300035, 38.36753627557965),
840 new Vector2D( 90.09075743352184, 38.35914647644972),
841 new Vector2D( 90.09099945896571, 38.35896264724079),
842 new Vector2D( 90.09269383800086, 38.34595756121246),
843 new Vector2D( 90.09638631543191, 38.3457988093121),
844 new Vector2D( 90.09666417351019, 38.34523360999418),
845 new Vector2D( 90.1297082145872, 38.337670454923625),
846 new Vector2D( 90.12971687748956, 38.337669827794684),
847 new Vector2D( 90.1240820219179, 38.34328502001131),
848 new Vector2D( 90.13084259656404, 38.34017811765017),
849 new Vector2D( 90.13378567942857, 38.33860579180606),
850 new Vector2D( 90.13519557833206, 38.33621054663689),
851 new Vector2D( 90.13545616732307, 38.33614965452864),
852 new Vector2D( 90.13553111202748, 38.33613962818305),
853 new Vector2D( 90.1356903436448, 38.33610227127048),
854 new Vector2D( 90.13576283227428, 38.33609255422783),
855 new Vector2D( 90.13595870833188, 38.33604606376991),
856 new Vector2D( 90.1361556630693, 38.3360024198866),
857 new Vector2D( 90.13622408795709, 38.335987048115726),
858 new Vector2D( 90.13696189099994, 38.33581914328681),
859 new Vector2D( 90.13746655304897, 38.33616706665265),
860 new Vector2D( 90.13845973716064, 38.33650776167099),
861 new Vector2D( 90.13950901827667, 38.3368469456463),
862 new Vector2D( 90.14393814424852, 38.337591835857495),
863 new Vector2D( 90.14483839716831, 38.337076122362475),
864 new Vector2D( 90.14565474433601, 38.33769000964429),
865 new Vector2D( 90.14569421179482, 38.3377117256905),
866 new Vector2D( 90.14577067124333, 38.33770883625908),
867 new Vector2D( 90.14600350631684, 38.337714326520995),
868 new Vector2D( 90.14600355139731, 38.33771435193319),
869 new Vector2D( 90.14600369112401, 38.33771443882085),
870 new Vector2D( 90.14600382486884, 38.33771453466096),
871 new Vector2D( 90.14600395205912, 38.33771463904344),
872 new Vector2D( 90.14600407214999, 38.337714751520764),
873 new Vector2D( 90.14600418462749, 38.337714871611695),
874 new Vector2D( 90.14600422249327, 38.337714915811034),
875 new Vector2D( 90.14867838361471, 38.34113888210675),
876 new Vector2D( 90.14923750157374, 38.341582537502575),
877 new Vector2D( 90.14877083250991, 38.34160685841391),
878 new Vector2D( 90.14816667319519, 38.34244232585684),
879 new Vector2D( 90.14797696744586, 38.34248455284745),
880 new Vector2D( 90.14484318014337, 38.34385573215269),
881 new Vector2D( 90.14477919958296, 38.3453797747614),
882 new Vector2D( 90.14202393306448, 38.34464324839456),
883 new Vector2D( 90.14198920640195, 38.344651155237216),
884 new Vector2D( 90.14155207025175, 38.34486424263724),
885 new Vector2D( 90.1415196143314, 38.344871730519),
886 new Vector2D( 90.14128611910814, 38.34500196593859),
887 new Vector2D( 90.14047850603913, 38.34600084496253),
888 new Vector2D( 90.14045907000337, 38.34601860032171),
889 new Vector2D( 90.14039496493928, 38.346223030432384),
890 new Vector2D( 90.14037626063737, 38.346240203360026),
891 new Vector2D( 90.14030005823724, 38.34646920000705),
892 new Vector2D( 90.13799164754806, 38.34903093011013),
893 new Vector2D( 90.11045289492762, 38.36801537312368),
894 new Vector2D( 90.10871471476526, 38.36878044144294),
895 new Vector2D( 90.10424901707671, 38.374300101757),
896 new Vector2D( 90.10263482039932, 38.37310041316073),
897 new Vector2D( 90.09834601753448, 38.373615053823414),
898 new Vector2D( 90.0979455456843, 38.373578376172475),
899 new Vector2D( 90.09086514328669, 38.37527884194668),
900 new Vector2D( 90.09084931407364, 38.37590801712463),
901 new Vector2D( 90.09081227075944, 38.37526295920463),
902 new Vector2D( 90.09081378927135, 38.375193883266434)
903 };
904 PolygonsSet set1 = new PolygonsSet(1.0e-8, vertices1);
905 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.0905, 38.3755)));
906 Assert.assertEquals(Location.INSIDE, set1.checkPoint(new Vector2D(90.09084, 38.3755)));
907 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.0913, 38.3755)));
908 Assert.assertEquals(Location.INSIDE, set1.checkPoint(new Vector2D(90.1042, 38.3739)));
909 Assert.assertEquals(Location.INSIDE, set1.checkPoint(new Vector2D(90.1111, 38.3673)));
910 Assert.assertEquals(Location.OUTSIDE, set1.checkPoint(new Vector2D(90.0959, 38.3457)));
911
912 Vector2D[] vertices2 = new Vector2D[] {
913 new Vector2D( 90.13067558880044, 38.36977255037573),
914 new Vector2D( 90.12907570488, 38.36817308242706),
915 new Vector2D( 90.1342774136516, 38.356886880294724),
916 new Vector2D( 90.13090330629757, 38.34664392676211),
917 new Vector2D( 90.13078571364593, 38.344904617518466),
918 new Vector2D( 90.1315602208914, 38.3447185040846),
919 new Vector2D( 90.1316336226821, 38.34470643148342),
920 new Vector2D( 90.134020944832, 38.340936644972885),
921 new Vector2D( 90.13912536387306, 38.335497255122334),
922 new Vector2D( 90.1396178806582, 38.334878075552126),
923 new Vector2D( 90.14083049696671, 38.33316530644106),
924 new Vector2D( 90.14145252901329, 38.33152722916191),
925 new Vector2D( 90.1404779335565, 38.32863516047786),
926 new Vector2D( 90.14282712131586, 38.327504432532066),
927 new Vector2D( 90.14616669875488, 38.3237354115015),
928 new Vector2D( 90.14860976050608, 38.315714862457924),
929 new Vector2D( 90.14999277782437, 38.3164932507504),
930 new Vector2D( 90.15005207194997, 38.316534677663356),
931 new Vector2D( 90.15508513859612, 38.31878731691609),
932 new Vector2D( 90.15919938519221, 38.31852743183782),
933 new Vector2D( 90.16093758658837, 38.31880662005153),
934 new Vector2D( 90.16099420184912, 38.318825953291594),
935 new Vector2D( 90.1665411125756, 38.31859497874757),
936 new Vector2D( 90.16999653861313, 38.32505772048029),
937 new Vector2D( 90.17475243391698, 38.32594398441148),
938 new Vector2D( 90.17940844844992, 38.327427213761325),
939 new Vector2D( 90.20951909541378, 38.330616833491774),
940 new Vector2D( 90.2155400467941, 38.331746223670336),
941 new Vector2D( 90.21559881391778, 38.33175551425302),
942 new Vector2D( 90.21916646426041, 38.332584299620805),
943 new Vector2D( 90.23863749852285, 38.34778978875795),
944 new Vector2D( 90.25459855175802, 38.357790570608984),
945 new Vector2D( 90.25964298227257, 38.356918010203174),
946 new Vector2D( 90.26024593994703, 38.361692743151366),
947 new Vector2D( 90.26146187570015, 38.36311080550837),
948 new Vector2D( 90.26614159359622, 38.36510808579902),
949 new Vector2D( 90.26621342936448, 38.36507942500333),
950 new Vector2D( 90.26652190211962, 38.36494042196722),
951 new Vector2D( 90.26621240678867, 38.365113172030874),
952 new Vector2D( 90.26614057102057, 38.365141832826794),
953 new Vector2D( 90.26380080055299, 38.3660381760273),
954 new Vector2D( 90.26315345241, 38.36670658276421),
955 new Vector2D( 90.26251574942881, 38.367490323488084),
956 new Vector2D( 90.26247873448426, 38.36755266444749),
957 new Vector2D( 90.26234628016698, 38.36787989125406),
958 new Vector2D( 90.26214559424784, 38.36945909356126),
959 new Vector2D( 90.25861728442555, 38.37200753430875),
960 new Vector2D( 90.23905557537864, 38.375405314295904),
961 new Vector2D( 90.22517251874075, 38.38984691662256),
962 new Vector2D( 90.22549955153215, 38.3911564273979),
963 new Vector2D( 90.22434386063355, 38.391476432092134),
964 new Vector2D( 90.22147729457276, 38.39134652252034),
965 new Vector2D( 90.22142070120117, 38.391349167741964),
966 new Vector2D( 90.20665060751588, 38.39475580900313),
967 new Vector2D( 90.20042268367109, 38.39842558622888),
968 new Vector2D( 90.17423771242085, 38.402727751805344),
969 new Vector2D( 90.16756796257476, 38.40913898597597),
970 new Vector2D( 90.16728283954308, 38.411255399912875),
971 new Vector2D( 90.16703538220418, 38.41136059866693),
972 new Vector2D( 90.16725865657685, 38.41013618805954),
973 new Vector2D( 90.16746107640665, 38.40902614307544),
974 new Vector2D( 90.16122795307462, 38.39773101873203)
975 };
976 PolygonsSet set2 = new PolygonsSet(1.0e-8, vertices2);
977 PolygonsSet set = (PolygonsSet) new
978 RegionFactory<Euclidean2D>().difference(set1.copySelf(),
979 set2.copySelf());
980
981 Vector2D[][] verticies = set.getVertices();
982 Assert.assertTrue(verticies[0][0] != null);
983 Assert.assertEquals(1, verticies.length);
984 }
985
986 private PolygonsSet buildSet(Vector2D[][] vertices) {
987 ArrayList<SubHyperplane<Euclidean2D>> edges = new ArrayList<SubHyperplane<Euclidean2D>>();
988 for (int i = 0; i < vertices.length; ++i) {
989 int l = vertices[i].length;
990 for (int j = 0; j < l; ++j) {
991 edges.add(buildSegment(vertices[i][j], vertices[i][(j + 1) % l]));
992 }
993 }
994 return new PolygonsSet(edges);
995 }
996
997 private SubHyperplane<Euclidean2D> buildLine(Vector2D start, Vector2D end) {
998 return new Line(start, end).wholeHyperplane();
999 }
1000
1001 private double intersectionAbscissa(Line l0, Line l1) {
1002 Vector2D p = l0.intersection(l1);
1003 return (l0.toSubSpace(p)).getX();
1004 }
1005
1006 private SubHyperplane<Euclidean2D> buildHalfLine(Vector2D start, Vector2D end,
1007 boolean startIsVirtual) {
1008 Line line = new Line(start, end);
1009 double lower = startIsVirtual
1010 ? Double.NEGATIVE_INFINITY
1011 : (line.toSubSpace(start)).getX();
1012 double upper = startIsVirtual
1013 ? (line.toSubSpace(end)).getX()
1014 : Double.POSITIVE_INFINITY;
1015 return new SubLine(line, new IntervalsSet(lower, upper));
1016 }
1017
1018 private SubHyperplane<Euclidean2D> buildSegment(Vector2D start, Vector2D end) {
1019 Line line = new Line(start, end);
1020 double lower = (line.toSubSpace(start)).getX();
1021 double upper = (line.toSubSpace(end)).getX();
1022 return new SubLine(line, new IntervalsSet(lower, upper));
1023 }
1024
1025 private void checkPoints(Region.Location expected, PolygonsSet set,
1026 Vector2D[] points) {
1027 for (int i = 0; i < points.length; ++i) {
1028 Assert.assertEquals(expected, set.checkPoint(points[i]));
1029 }
1030 }
1031
1032 private boolean checkInSegment(Vector2D p,
1033 Vector2D p1, Vector2D p2,
1034 double tolerance) {
1035 Line line = new Line(p1, p2);
1036 if (line.getOffset(p) < tolerance) {
1037 double x = (line.toSubSpace(p)).getX();
1038 double x1 = (line.toSubSpace(p1)).getX();
1039 double x2 = (line.toSubSpace(p2)).getX();
1040 return (((x - x1) * (x - x2) <= 0.0)
1041 || (p1.distance(p) < tolerance)
1042 || (p2.distance(p) < tolerance));
1043 } else {
1044 return false;
1045 }
1046 }
1047
1048 private void checkVertices(Vector2D[][] rebuiltVertices,
1049 Vector2D[][] vertices) {
1050
1051 // each rebuilt vertex should be in a segment joining two original vertices
1052 for (int i = 0; i < rebuiltVertices.length; ++i) {
1053 for (int j = 0; j < rebuiltVertices[i].length; ++j) {
1054 boolean inSegment = false;
1055 Vector2D p = rebuiltVertices[i][j];
1056 for (int k = 0; k < vertices.length; ++k) {
1057 Vector2D[] loop = vertices[k];
1058 int length = loop.length;
1059 for (int l = 0; (! inSegment) && (l < length); ++l) {
1060 inSegment = checkInSegment(p, loop[l], loop[(l + 1) % length], 1.0e-10);
1061 }
1062 }
1063 Assert.assertTrue(inSegment);
1064 }
1065 }
1066
1067 // each original vertex should have a corresponding rebuilt vertex
1068 for (int k = 0; k < vertices.length; ++k) {
1069 for (int l = 0; l < vertices[k].length; ++l) {
1070 double min = Double.POSITIVE_INFINITY;
1071 for (int i = 0; i < rebuiltVertices.length; ++i) {
1072 for (int j = 0; j < rebuiltVertices[i].length; ++j) {
1073 min = FastMath.min(vertices[k][l].distance(rebuiltVertices[i][j]),
1074 min);
1075 }
1076 }
1077 Assert.assertEquals(0.0, min, 1.0e-10);
1078 }
1079 }
1080
1081 }
1082
1083 }