View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one or more
3    * contributor license agreements.  See the NOTICE file distributed with
4    * this work for additional information regarding copyright ownership.
5    * The ASF licenses this file to You under the Apache License, Version 2.0
6    * (the "License"); you may not use this file except in compliance with
7    * the License.  You may obtain a copy of the License at
8    *
9    *      https://www.apache.org/licenses/LICENSE-2.0
10   *
11   * Unless required by applicable law or agreed to in writing, software
12   * distributed under the License is distributed on an "AS IS" BASIS,
13   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14   * See the License for the specific language governing permissions and
15   * limitations under the License.
16   */
17  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  package org.hipparchus.geometry.euclidean.threed;
23  
24  import java.io.IOException;
25  import java.io.InputStream;
26  import java.io.InputStreamReader;
27  import java.io.Reader;
28  import java.text.ParseException;
29  import java.util.ArrayList;
30  import java.util.Arrays;
31  import java.util.List;
32  
33  import org.hipparchus.exception.Localizable;
34  import org.hipparchus.exception.LocalizedCoreFormats;
35  import org.hipparchus.exception.MathIllegalArgumentException;
36  import org.hipparchus.exception.MathRuntimeException;
37  import org.hipparchus.geometry.LocalizedGeometryFormats;
38  import org.hipparchus.geometry.Vector;
39  import org.hipparchus.geometry.euclidean.twod.Euclidean2D;
40  import org.hipparchus.geometry.euclidean.twod.PolygonsSet;
41  import org.hipparchus.geometry.euclidean.twod.SubLine;
42  import org.hipparchus.geometry.euclidean.twod.Vector2D;
43  import org.hipparchus.geometry.partitioning.BSPTree;
44  import org.hipparchus.geometry.partitioning.BSPTreeVisitor;
45  import org.hipparchus.geometry.partitioning.BoundaryAttribute;
46  import org.hipparchus.geometry.partitioning.Region;
47  import org.hipparchus.geometry.partitioning.RegionDumper;
48  import org.hipparchus.geometry.partitioning.RegionFactory;
49  import org.hipparchus.geometry.partitioning.RegionParser;
50  import org.hipparchus.geometry.partitioning.SubHyperplane;
51  import org.hipparchus.random.RandomGenerator;
52  import org.hipparchus.random.Well1024a;
53  import org.hipparchus.util.FastMath;
54  import org.junit.Assert;
55  import org.junit.Test;
56  
57  public class PolyhedronsSetTest {
58  
59      @Test
60      public void testBox() {
61          PolyhedronsSet tree = new PolyhedronsSet(0, 1, 0, 1, 0, 1, 1.0e-10);
62          Assert.assertEquals(1.0, tree.getSize(), 1.0e-10);
63          Assert.assertEquals(6.0, tree.getBoundarySize(), 1.0e-10);
64          Vector3D barycenter = (Vector3D) tree.getBarycenter();
65          Assert.assertEquals(0.5, barycenter.getX(), 1.0e-10);
66          Assert.assertEquals(0.5, barycenter.getY(), 1.0e-10);
67          Assert.assertEquals(0.5, barycenter.getZ(), 1.0e-10);
68          for (double x = -0.25; x < 1.25; x += 0.1) {
69              boolean xOK = (x >= 0.0) && (x <= 1.0);
70              for (double y = -0.25; y < 1.25; y += 0.1) {
71                  boolean yOK = (y >= 0.0) && (y <= 1.0);
72                  for (double z = -0.25; z < 1.25; z += 0.1) {
73                      boolean zOK = (z >= 0.0) && (z <= 1.0);
74                      Region.Location expected =
75                          (xOK && yOK && zOK) ? Region.Location.INSIDE : Region.Location.OUTSIDE;
76                      Assert.assertEquals(expected, tree.checkPoint(new Vector3D(x, y, z)));
77                  }
78              }
79          }
80          checkPoints(Region.Location.BOUNDARY, tree, new Vector3D[] {
81              new Vector3D(0.0, 0.5, 0.5),
82              new Vector3D(1.0, 0.5, 0.5),
83              new Vector3D(0.5, 0.0, 0.5),
84              new Vector3D(0.5, 1.0, 0.5),
85              new Vector3D(0.5, 0.5, 0.0),
86              new Vector3D(0.5, 0.5, 1.0)
87          });
88          checkPoints(Region.Location.OUTSIDE, tree, new Vector3D[] {
89              new Vector3D(0.0, 1.2, 1.2),
90              new Vector3D(1.0, 1.2, 1.2),
91              new Vector3D(1.2, 0.0, 1.2),
92              new Vector3D(1.2, 1.0, 1.2),
93              new Vector3D(1.2, 1.2, 0.0),
94              new Vector3D(1.2, 1.2, 1.0)
95          });
96      }
97  
98      @Test
99      public void testBRepExtractor() {
100         double x = 1.0;
101         double y = 2.0;
102         double z = 3.0;
103         double w = 0.1;
104         double l = 1.0;
105         PolyhedronsSet polyhedron =
106             new PolyhedronsSet(x - l, x + l, y - w, y + w, z - w, z + w, 1.0e-10);
107         PolyhedronsSet.BRep brep = polyhedron.getBRep();
108         Assert.assertEquals(6, brep.getFacets().size());
109         Assert.assertEquals(8, brep.getVertices().size());
110     }
111 
112     @Test
113     public void testEmptyBRepIfEmpty() {
114         PolyhedronsSet empty = (PolyhedronsSet) new RegionFactory<Euclidean3D>().getComplement(new PolyhedronsSet(1.0e-10));
115         Assert.assertTrue(empty.isEmpty());
116         Assert.assertEquals(0.0, empty.getSize(), 1.0e-10);
117         PolyhedronsSet.BRep brep = empty.getBRep();
118         Assert.assertEquals(0, brep.getFacets().size());
119         Assert.assertEquals(0, brep.getVertices().size());
120     }
121 
122     @Test
123     public void testNoBRepHalfSpace() {
124         BSPTree<Euclidean3D> bsp = new BSPTree<>();
125         bsp.insertCut(new Plane(Vector3D.PLUS_K, 1.0e-10));
126         bsp.getPlus().setAttribute(Boolean.FALSE);
127         bsp.getMinus().setAttribute(Boolean.TRUE);
128         PolyhedronsSet polyhedron = new PolyhedronsSet(bsp, 1.0e-10);
129         Assert.assertEquals(Double.POSITIVE_INFINITY, polyhedron.getSize(), 1.0e-10);
130         try {
131             polyhedron.getBRep();
132             Assert.fail("an exception should have been thrown");
133         } catch (MathRuntimeException mre) {
134             Assert.assertEquals(LocalizedGeometryFormats.OUTLINE_BOUNDARY_LOOP_OPEN, mre.getSpecifier());
135         }
136     }
137 
138     @Test
139     public void testNoBRepUnboundedOctant() {
140         BSPTree<Euclidean3D> bsp = new BSPTree<>();
141         bsp.insertCut(new Plane(Vector3D.PLUS_K, 1.0e-10));
142         bsp.getPlus().setAttribute(Boolean.FALSE);
143         bsp.getMinus().insertCut(new Plane(Vector3D.PLUS_I, 1.0e-10));
144         bsp.getMinus().getPlus().setAttribute(Boolean.FALSE);
145         bsp.getMinus().getMinus().insertCut(new Plane(Vector3D.PLUS_J, 1.0e-10));
146         bsp.getMinus().getMinus().getPlus().setAttribute(Boolean.FALSE);
147         bsp.getMinus().getMinus().getMinus().setAttribute(Boolean.TRUE);
148         PolyhedronsSet polyhedron = new PolyhedronsSet(bsp, 1.0e-10);
149         Assert.assertEquals(Double.POSITIVE_INFINITY, polyhedron.getSize(), 1.0e-10);
150         try {
151             polyhedron.getBRep();
152             Assert.fail("an exception should have been thrown");
153         } catch (MathRuntimeException mre) {
154             Assert.assertEquals(LocalizedGeometryFormats.OUTLINE_BOUNDARY_LOOP_OPEN, mre.getSpecifier());
155         }
156     }
157 
158     @Test
159     public void testNoBRepHolesInFacet() {
160         double tolerance = 1.0e-10;
161         PolyhedronsSet cube       = new PolyhedronsSet(-1.0, 1.0, -1.0, 1.0, -1.0, 1.0, tolerance);
162         PolyhedronsSet tubeAlongX = new PolyhedronsSet(-2.0, 2.0, -0.5, 0.5, -0.5, 0.5, tolerance);
163         PolyhedronsSet tubeAlongY = new PolyhedronsSet(-0.5, 0.5, -2.0, 2.0, -0.5, 0.5, tolerance);
164         PolyhedronsSet tubeAlongZ = new PolyhedronsSet(-0.5, 0.5, -0.5, 0.5, -2.0, 2.0, tolerance);
165         RegionFactory<Euclidean3D> factory = new RegionFactory<>();
166         PolyhedronsSet cubeWithHoles = (PolyhedronsSet) factory.difference(cube,
167                                                                            factory.union(tubeAlongX,
168                                                                                          factory.union(tubeAlongY, tubeAlongZ)));
169         Assert.assertEquals(4.0, cubeWithHoles.getSize(), 1.0e-10);
170         try {
171             cubeWithHoles.getBRep();
172             Assert.fail("an exception should have been thrown");
173         } catch (MathRuntimeException mre) {
174             Assert.assertEquals(LocalizedGeometryFormats.FACET_WITH_SEVERAL_BOUNDARY_LOOPS, mre.getSpecifier());
175         }
176     }
177 
178     @Test
179     public void testTetrahedron() throws MathRuntimeException {
180         Vector3D vertex1 = new Vector3D(1, 2, 3);
181         Vector3D vertex2 = new Vector3D(2, 2, 4);
182         Vector3D vertex3 = new Vector3D(2, 3, 3);
183         Vector3D vertex4 = new Vector3D(1, 3, 4);
184         PolyhedronsSet tree =
185             (PolyhedronsSet) new RegionFactory<Euclidean3D>().buildConvex(
186                 new Plane(vertex3, vertex2, vertex1, 1.0e-10),
187                 new Plane(vertex2, vertex3, vertex4, 1.0e-10),
188                 new Plane(vertex4, vertex3, vertex1, 1.0e-10),
189                 new Plane(vertex1, vertex2, vertex4, 1.0e-10));
190         Assert.assertEquals(1.0 / 3.0, tree.getSize(), 1.0e-10);
191         Assert.assertEquals(2.0 * FastMath.sqrt(3.0), tree.getBoundarySize(), 1.0e-10);
192         Vector3D barycenter = (Vector3D) tree.getBarycenter();
193         Assert.assertEquals(1.5, barycenter.getX(), 1.0e-10);
194         Assert.assertEquals(2.5, barycenter.getY(), 1.0e-10);
195         Assert.assertEquals(3.5, barycenter.getZ(), 1.0e-10);
196         double third = 1.0 / 3.0;
197         checkPoints(Region.Location.BOUNDARY, tree, new Vector3D[] {
198             vertex1, vertex2, vertex3, vertex4,
199             new Vector3D(third, vertex1, third, vertex2, third, vertex3),
200             new Vector3D(third, vertex2, third, vertex3, third, vertex4),
201             new Vector3D(third, vertex3, third, vertex4, third, vertex1),
202             new Vector3D(third, vertex4, third, vertex1, third, vertex2)
203         });
204         checkPoints(Region.Location.OUTSIDE, tree, new Vector3D[] {
205             new Vector3D(1, 2, 4),
206             new Vector3D(2, 2, 3),
207             new Vector3D(2, 3, 4),
208             new Vector3D(1, 3, 3)
209         });
210     }
211 
212     @Test
213     public void testIsometry() throws MathRuntimeException, MathIllegalArgumentException {
214         Vector3D vertex1 = new Vector3D(1.1, 2.2, 3.3);
215         Vector3D vertex2 = new Vector3D(2.0, 2.4, 4.2);
216         Vector3D vertex3 = new Vector3D(2.8, 3.3, 3.7);
217         Vector3D vertex4 = new Vector3D(1.0, 3.6, 4.5);
218         PolyhedronsSet tree =
219             (PolyhedronsSet) new RegionFactory<Euclidean3D>().buildConvex(
220                 new Plane(vertex3, vertex2, vertex1, 1.0e-10),
221                 new Plane(vertex2, vertex3, vertex4, 1.0e-10),
222                 new Plane(vertex4, vertex3, vertex1, 1.0e-10),
223                 new Plane(vertex1, vertex2, vertex4, 1.0e-10));
224         Vector3D barycenter = (Vector3D) tree.getBarycenter();
225         Vector3D s = new Vector3D(10.2, 4.3, -6.7);
226         Vector3D c = new Vector3D(-0.2, 2.1, -3.2);
227         Rotation r = new Rotation(new Vector3D(6.2, -4.4, 2.1), 0.12, RotationConvention.VECTOR_OPERATOR);
228 
229         tree = tree.rotate(c, r).translate(s);
230 
231         Vector3D newB =
232             new Vector3D(1.0, s,
233                          1.0, c,
234                          1.0, r.applyTo(barycenter.subtract(c)));
235         Assert.assertEquals(0.0,
236                             newB.subtract((Vector<Euclidean3D, Vector3D>) tree.getBarycenter()).getNorm(),
237                             1.0e-10);
238 
239         final Vector3D[] expectedV = new Vector3D[] {
240             new Vector3D(1.0, s,
241                          1.0, c,
242                          1.0, r.applyTo(vertex1.subtract(c))),
243                          new Vector3D(1.0, s,
244                                       1.0, c,
245                                       1.0, r.applyTo(vertex2.subtract(c))),
246                                       new Vector3D(1.0, s,
247                                                    1.0, c,
248                                                    1.0, r.applyTo(vertex3.subtract(c))),
249                                                    new Vector3D(1.0, s,
250                                                                 1.0, c,
251                                                                 1.0, r.applyTo(vertex4.subtract(c)))
252         };
253         tree.getTree(true).visit(new BSPTreeVisitor<Euclidean3D>() {
254 
255             public Order visitOrder(BSPTree<Euclidean3D> node) {
256                 return Order.MINUS_SUB_PLUS;
257             }
258 
259             public void visitInternalNode(BSPTree<Euclidean3D> node) {
260                 @SuppressWarnings("unchecked")
261                 BoundaryAttribute<Euclidean3D> attribute =
262                     (BoundaryAttribute<Euclidean3D>) node.getAttribute();
263                 if (attribute.getPlusOutside() != null) {
264                     checkFacet((SubPlane) attribute.getPlusOutside());
265                 }
266                 if (attribute.getPlusInside() != null) {
267                     checkFacet((SubPlane) attribute.getPlusInside());
268                 }
269             }
270 
271             public void visitLeafNode(BSPTree<Euclidean3D> node) {
272             }
273 
274             private void checkFacet(SubPlane facet) {
275                 Plane plane = (Plane) facet.getHyperplane();
276                 Vector2D[][] vertices =
277                     ((PolygonsSet) facet.getRemainingRegion()).getVertices();
278                 Assert.assertEquals(1, vertices.length);
279                 for (int i = 0; i < vertices[0].length; ++i) {
280                     Vector3D v = plane.toSpace(vertices[0][i]);
281                     double d = Double.POSITIVE_INFINITY;
282                     for (int k = 0; k < expectedV.length; ++k) {
283                         d = FastMath.min(d, v.subtract(expectedV[k]).getNorm());
284                     }
285                     Assert.assertEquals(0, d, 1.0e-10);
286                 }
287             }
288 
289         });
290 
291     }
292 
293     @Test
294     public void testBuildBox() {
295         double x = 1.0;
296         double y = 2.0;
297         double z = 3.0;
298         double w = 0.1;
299         double l = 1.0;
300         PolyhedronsSet tree =
301             new PolyhedronsSet(x - l, x + l, y - w, y + w, z - w, z + w, 1.0e-10);
302         Vector3D barycenter = (Vector3D) tree.getBarycenter();
303         Assert.assertEquals(x, barycenter.getX(), 1.0e-10);
304         Assert.assertEquals(y, barycenter.getY(), 1.0e-10);
305         Assert.assertEquals(z, barycenter.getZ(), 1.0e-10);
306         Assert.assertEquals(8 * l * w * w, tree.getSize(), 1.0e-10);
307         Assert.assertEquals(8 * w * (2 * l + w), tree.getBoundarySize(), 1.0e-10);
308     }
309 
310     @Test
311     public void testCross() {
312 
313         double x = 1.0;
314         double y = 2.0;
315         double z = 3.0;
316         double w = 0.1;
317         double l = 1.0;
318         PolyhedronsSet xBeam =
319             new PolyhedronsSet(x - l, x + l, y - w, y + w, z - w, z + w, 1.0e-10);
320         PolyhedronsSet yBeam =
321             new PolyhedronsSet(x - w, x + w, y - l, y + l, z - w, z + w, 1.0e-10);
322         PolyhedronsSet zBeam =
323             new PolyhedronsSet(x - w, x + w, y - w, y + w, z - l, z + l, 1.0e-10);
324         RegionFactory<Euclidean3D> factory = new RegionFactory<Euclidean3D>();
325         PolyhedronsSet tree = (PolyhedronsSet) factory.union(xBeam, factory.union(yBeam, zBeam));
326         Vector3D barycenter = (Vector3D) tree.getBarycenter();
327 
328         Assert.assertEquals(x, barycenter.getX(), 1.0e-10);
329         Assert.assertEquals(y, barycenter.getY(), 1.0e-10);
330         Assert.assertEquals(z, barycenter.getZ(), 1.0e-10);
331         Assert.assertEquals(8 * w * w * (3 * l - 2 * w), tree.getSize(), 1.0e-10);
332         Assert.assertEquals(24 * w * (2 * l - w), tree.getBoundarySize(), 1.0e-10);
333 
334     }
335 
336     @Test
337     public void testIssue780() throws MathRuntimeException {
338         float[] coords = {
339             1.000000f, -1.000000f, -1.000000f,
340             1.000000f, -1.000000f, 1.000000f,
341             -1.000000f, -1.000000f, 1.000000f,
342             -1.000000f, -1.000000f, -1.000000f,
343             1.000000f, 1.000000f, -1f,
344             0.999999f, 1.000000f, 1.000000f,   // 1.000000f, 1.000000f, 1.000000f,
345             -1.000000f, 1.000000f, 1.000000f,
346             -1.000000f, 1.000000f, -1.000000f};
347         int[] indices = {
348             0, 1, 2, 0, 2, 3,
349             4, 7, 6, 4, 6, 5,
350             0, 4, 5, 0, 5, 1,
351             1, 5, 6, 1, 6, 2,
352             2, 6, 7, 2, 7, 3,
353             4, 0, 3, 4, 3, 7};
354         ArrayList<SubHyperplane<Euclidean3D>> subHyperplaneList = new ArrayList<SubHyperplane<Euclidean3D>>();
355         for (int idx = 0; idx < indices.length; idx += 3) {
356             int idxA = indices[idx] * 3;
357             int idxB = indices[idx + 1] * 3;
358             int idxC = indices[idx + 2] * 3;
359             Vector3D v_1 = new Vector3D(coords[idxA], coords[idxA + 1], coords[idxA + 2]);
360             Vector3D v_2 = new Vector3D(coords[idxB], coords[idxB + 1], coords[idxB + 2]);
361             Vector3D v_3 = new Vector3D(coords[idxC], coords[idxC + 1], coords[idxC + 2]);
362             Vector3D[] vertices = {v_1, v_2, v_3};
363             Plane polyPlane = new Plane(v_1, v_2, v_3, 1.0e-10);
364             ArrayList<SubHyperplane<Euclidean2D>> lines = new ArrayList<SubHyperplane<Euclidean2D>>();
365 
366             Vector2D[] projPts = new Vector2D[vertices.length];
367             for (int ptIdx = 0; ptIdx < projPts.length; ptIdx++) {
368                 projPts[ptIdx] = polyPlane.toSubSpace(vertices[ptIdx]);
369             }
370 
371             SubLine lineInPlane = null;
372             for (int ptIdx = 0; ptIdx < projPts.length; ptIdx++) {
373                 lineInPlane = new SubLine(projPts[ptIdx], projPts[(ptIdx + 1) % projPts.length], 1.0e-10);
374                 lines.add(lineInPlane);
375             }
376             Region<Euclidean2D> polyRegion = new PolygonsSet(lines, 1.0e-10);
377             SubPlane polygon = new SubPlane(polyPlane, polyRegion);
378             subHyperplaneList.add(polygon);
379         }
380         PolyhedronsSet polyhedronsSet = new PolyhedronsSet(subHyperplaneList, 1.0e-10);
381         Assert.assertEquals( 8.0, polyhedronsSet.getSize(), 3.0e-6);
382         Assert.assertEquals(24.0, polyhedronsSet.getBoundarySize(), 5.0e-6);
383     }
384 
385     @Test
386     public void testTooThinBox() {
387         Assert.assertEquals(0.0,
388                             new PolyhedronsSet(0.0, 0.0, 0.0, 1.0, 0.0, 1.0, 1.0e-10).getSize(),
389                             1.0e-10);
390     }
391 
392     @Test
393     public void testWrongUsage() {
394         // the following is a wrong usage of the constructor.
395         // as explained in the javadoc, the failure is NOT detected at construction
396         // time but occurs later on
397         PolyhedronsSet ps = new PolyhedronsSet(new BSPTree<Euclidean3D>(), 1.0e-10);
398         Assert.assertNotNull(ps);
399         try {
400             ps.checkPoint(Vector3D.ZERO);
401             Assert.fail("an exception should have been thrown");
402         } catch (NullPointerException npe) {
403             // this is expected
404         }
405     }
406 
407     @Test
408     public void testDumpParse() throws IOException, ParseException {
409         double tol=1e-8;
410 
411             Vector3D[] verts=new Vector3D[8];
412             double xmin=-1,xmax=1;
413             double ymin=-1,ymax=1;
414             double zmin=-1,zmax=1;
415             verts[0]=new Vector3D(xmin,ymin,zmin);
416             verts[1]=new Vector3D(xmax,ymin,zmin);
417             verts[2]=new Vector3D(xmax,ymax,zmin);
418             verts[3]=new Vector3D(xmin,ymax,zmin);
419             verts[4]=new Vector3D(xmin,ymin,zmax);
420             verts[5]=new Vector3D(xmax,ymin,zmax);
421             verts[6]=new Vector3D(xmax,ymax,zmax);
422             verts[7]=new Vector3D(xmin,ymax,zmax);
423             //
424             int[][] faces=new int[12][];
425             faces[0]=new int[]{3,1,0};  // bottom (-z)
426             faces[1]=new int[]{1,3,2};  // bottom (-z)
427             faces[2]=new int[]{5,7,4};  // top (+z)
428             faces[3]=new int[]{7,5,6};  // top (+z)
429             faces[4]=new int[]{2,5,1};  // right (+x)
430             faces[5]=new int[]{5,2,6};  // right (+x)
431             faces[6]=new int[]{4,3,0};  // left (-x)
432             faces[7]=new int[]{3,4,7};  // left (-x)
433             faces[8]=new int[]{4,1,5};  // front (-y)
434             faces[9]=new int[]{1,4,0};  // front (-y)
435             faces[10]=new int[]{3,6,2}; // back (+y)
436             faces[11]=new int[]{6,3,7}; // back (+y)
437             PolyhedronsSet polyset = new PolyhedronsSet(Arrays.asList(verts), Arrays.asList(faces), tol);
438             Assert.assertEquals(8.0, polyset.getSize(), 1.0e-10);
439             Assert.assertEquals(24.0, polyset.getBoundarySize(), 1.0e-10);
440             String dump = RegionDumper.dump(polyset);
441             PolyhedronsSet parsed = RegionParser.parsePolyhedronsSet(dump);
442             Assert.assertEquals(8.0, parsed.getSize(), 1.0e-10);
443             Assert.assertEquals(24.0, parsed.getBoundarySize(), 1.0e-10);
444             Assert.assertTrue(new RegionFactory<Euclidean3D>().difference(polyset, parsed).isEmpty());
445     }
446 
447     @Test
448     public void testConnectedFacets() throws IOException, ParseException {
449         InputStream stream = getClass().getResourceAsStream("pentomino-N.ply");
450         PLYParser   parser = new PLYParser(stream);
451         stream.close();
452         PolyhedronsSet polyhedron = new PolyhedronsSet(parser.getVertices(), parser.getFaces(), 1.0e-10);
453         Assert.assertEquals( 5.0, polyhedron.getSize(), 1.0e-10);
454         Assert.assertEquals(22.0, polyhedron.getBoundarySize(), 1.0e-10);
455     }
456 
457     @Test
458     public void testTooClose() throws IOException, ParseException {
459         checkError("pentomino-N-too-close.ply", LocalizedGeometryFormats.CLOSE_VERTICES);
460     }
461 
462     @Test
463     public void testHole() throws IOException, ParseException {
464         checkError("pentomino-N-hole.ply", LocalizedGeometryFormats.EDGE_CONNECTED_TO_ONE_FACET);
465     }
466 
467     @Test
468     public void testNonPlanar() throws IOException, ParseException {
469         checkError("pentomino-N-out-of-plane.ply", LocalizedGeometryFormats.OUT_OF_PLANE);
470     }
471 
472     @Test
473     public void testOrientation() throws IOException, ParseException {
474         checkError("pentomino-N-bad-orientation.ply", LocalizedGeometryFormats.FACET_ORIENTATION_MISMATCH);
475     }
476 
477     @Test
478     public void testFacet2Vertices() throws IOException, ParseException {
479         checkError(Arrays.asList(Vector3D.ZERO, Vector3D.PLUS_I, Vector3D.PLUS_J, Vector3D.PLUS_K),
480                    Arrays.asList(new int[] { 0, 1, 2 }, new int[] {2, 3}),
481                    LocalizedCoreFormats.WRONG_NUMBER_OF_POINTS);
482     }
483 
484     private void checkError(final String resourceName, final Localizable expected) {
485         try {
486             InputStream stream = getClass().getResourceAsStream(resourceName);
487             PLYParser   parser = new PLYParser(stream);
488             stream.close();
489             checkError(parser.getVertices(), parser.getFaces(), expected);
490         } catch (IOException ioe) {
491             Assert.fail(ioe.getLocalizedMessage());
492         } catch (ParseException pe) {
493             Assert.fail(pe.getLocalizedMessage());
494         }
495     }
496 
497     private void checkError(final List<Vector3D> vertices, final List<int[]> facets,
498                             final Localizable expected) {
499         try {
500             new PolyhedronsSet(vertices, facets, 1.0e-10);
501             Assert.fail("an exception should have been thrown");
502         } catch (MathIllegalArgumentException miae) {
503             Assert.assertEquals(expected, miae.getSpecifier());
504         }
505     }
506 
507     // issue GEOMETRY-38
508     @Test
509     public void testFirstIntersectionLinesPassThroughBoundaries() {
510         // arrange
511         Vector3D lowerCorner = Vector3D.ZERO;
512         Vector3D upperCorner = new Vector3D(1, 1, 1);
513         Vector3D center = new Vector3D(0.5, lowerCorner, 0.5, upperCorner);
514 
515         PolyhedronsSet polySet = new PolyhedronsSet(0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 1.0e-15);
516 
517         Line upDiagonal = new Line(lowerCorner, upperCorner, 1.0e-15);
518         Line downDiagonal = upDiagonal.revert();
519 
520         // act/assert
521         SubPlane upFromOutsideResult = (SubPlane) polySet.firstIntersection(new Vector3D(-1, -1, -1), upDiagonal);
522         Assert.assertNotNull(upFromOutsideResult);
523         Assert.assertEquals(0.0,
524                             Vector3D.distance(lowerCorner,
525                                               ((Plane) upFromOutsideResult.getHyperplane()).intersection(upDiagonal)),
526                             1.0e-15);
527 
528         SubPlane upFromCenterResult = (SubPlane) polySet.firstIntersection(center, upDiagonal);
529         Assert.assertNotNull(upFromCenterResult);
530         Assert.assertEquals(0.0,
531                             Vector3D.distance(upperCorner,
532                                               ((Plane) upFromCenterResult.getHyperplane()).intersection(upDiagonal)),
533                             1.0e-15);
534 
535         SubPlane downFromOutsideResult = (SubPlane) polySet.firstIntersection(new Vector3D(2, 2, 2), downDiagonal);
536         Assert.assertNotNull(downFromOutsideResult);
537         Assert.assertEquals(0.0,
538                             Vector3D.distance(upperCorner,
539                             ((Plane) downFromOutsideResult.getHyperplane()).intersection(downDiagonal)),
540                             1.0e-15);
541 
542         SubPlane downFromCenterResult = (SubPlane) polySet.firstIntersection(center, downDiagonal);
543         Assert.assertNotNull(downFromCenterResult);
544         Assert.assertEquals(0.0,
545                             Vector3D.distance(lowerCorner,
546                                               ((Plane) downFromCenterResult.getHyperplane()).intersection(downDiagonal)),
547                             1.0e-15);
548     }
549 
550     @Test
551     public void testIssue1211() throws IOException, ParseException {
552 
553         PolyhedronsSet polyset = RegionParser.parsePolyhedronsSet(loadTestData("issue-1211.bsp"));
554         RandomGenerator random = new Well1024a(0xb97c9d1ade21e40al);
555         int nrays = 1000;
556         for (int i = 0; i < nrays; i++) {
557             Vector3D origin    = Vector3D.ZERO;
558             Vector3D direction = new Vector3D(2 * random.nextDouble() - 1,
559                                               2 * random.nextDouble() - 1,
560                                               2 * random.nextDouble() - 1).normalize();
561             Line line = new Line(origin, origin.add(direction), polyset.getTolerance());
562             SubHyperplane<Euclidean3D> plane = polyset.firstIntersection(origin, line);
563             if (plane != null) {
564                 Vector3D intersectionPoint = ((Plane)plane.getHyperplane()).intersection(line);
565                 double dotProduct = direction.dotProduct(intersectionPoint.subtract(origin));
566                 Assert.assertTrue(dotProduct > 0);
567             }
568         }
569     }
570 
571     private String loadTestData(final String resourceName)
572             throws IOException {
573             InputStream stream = getClass().getResourceAsStream(resourceName);
574             Reader reader = new InputStreamReader(stream, "UTF-8");
575             StringBuilder builder = new StringBuilder();
576             for (int c = reader.read(); c >= 0; c = reader.read()) {
577                 builder.append((char) c);
578             }
579             return builder.toString();
580         }
581 
582     private void checkPoints(Region.Location expected, PolyhedronsSet tree, Vector3D[] points) {
583         for (int i = 0; i < points.length; ++i) {
584             Assert.assertEquals(expected, tree.checkPoint(points[i]));
585         }
586     }
587 
588 }