1 /*
2 * Copyright (C) 2012 Alberto Irurueta Carro (alberto@irurueta.com)
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16 package com.irurueta.geometry;
17
18 import java.io.Serializable;
19 import java.util.ArrayList;
20 import java.util.List;
21
22 /**
23 * This class defines a triangle in the 3D space.
24 */
25 @SuppressWarnings("DuplicatedCode")
26 public class Triangle3D implements Serializable {
27 /**
28 * Default threshold value. Thresholds are used to determine whether a point
29 * lies inside the triangle or not, or if its locus or not, etc.
30 */
31 public static final double DEFAULT_THRESHOLD = 1e-9;
32
33 /**
34 * Minimum allowed threshold value
35 */
36 public static final double MIN_THRESHOLD = 0.0;
37
38 /**
39 * Constant defining number of coordinates
40 */
41 public static final int INHOM_COORDS = 3;
42
43 /**
44 * Constant defining number of vertices on a triangle
45 */
46 public static final int NUM_VERTICES = 3;
47
48 /**
49 * 1st vertex of this triangle.
50 */
51 private Point3D vertex1;
52
53 /**
54 * 2nd vertex of this triangle.
55 */
56 private Point3D vertex2;
57
58 /**
59 * 3rd vertex of this triangle.
60 */
61 private Point3D vertex3;
62
63 /**
64 * Constructor.
65 *
66 * @param vertex1 1st vertex.
67 * @param vertex2 2nd vertex.
68 * @param vertex3 3rd vertex.
69 * @throws NullPointerException Raised if any of the vertices is null.
70 */
71 public Triangle3D(final Point3D vertex1, final Point3D vertex2, final Point3D vertex3) {
72 setVertices(vertex1, vertex2, vertex3);
73 }
74
75 /**
76 * Returns 1st vertex of this triangle.
77 *
78 * @return 1st vertex.
79 */
80 public Point3D getVertex1() {
81 return vertex1;
82 }
83
84 /**
85 * Sets 1st vertex of this triangle.
86 *
87 * @param vertex1 1st vertex.
88 * @throws NullPointerException Raised if provided vertex is null.
89 */
90 public void setVertex1(final Point3D vertex1) {
91 if (vertex1 == null) {
92 throw new NullPointerException();
93 }
94 this.vertex1 = vertex1;
95 }
96
97 /**
98 * Returns 2nd vertex of this triangle.
99 *
100 * @return 2nd vertex.
101 */
102 public Point3D getVertex2() {
103 return vertex2;
104 }
105
106 /**
107 * Sets 2nd vertex of this triangle.
108 *
109 * @param vertex2 2nd vertex.
110 * @throws NullPointerException Raised if provided vertex is null.
111 */
112 public void setVertex2(final Point3D vertex2) {
113 if (vertex2 == null) {
114 throw new NullPointerException();
115 }
116 this.vertex2 = vertex2;
117 }
118
119 /**
120 * Returns 3rd vertex of this triangle.
121 *
122 * @return 3rd vertex.
123 */
124 public Point3D getVertex3() {
125 return vertex3;
126 }
127
128 /**
129 * Sets 3rd vertex of this triangle.
130 *
131 * @param vertex3 3rd vertex.
132 * @throws NullPointerException Raised if provided vertex is null.
133 */
134 public void setVertex3(final Point3D vertex3) {
135 if (vertex3 == null) {
136 throw new NullPointerException();
137 }
138 this.vertex3 = vertex3;
139 }
140
141 /**
142 * Returns vertices of this triangle as a list of points.
143 *
144 * @return Vertices of this triangle.
145 */
146 public List<Point3D> getVertices() {
147 final var vertices = new ArrayList<Point3D>(NUM_VERTICES);
148 vertices(vertices);
149 return vertices;
150 }
151
152 /**
153 * Stores vertices of this triangle in provided list. Note that content of
154 * list will be cleared before storing this triangle's vertices.
155 *
156 * @param result list where vertices will be stored.
157 */
158 public void vertices(final List<Point3D> result) {
159 result.clear();
160 result.add(vertex1);
161 result.add(vertex2);
162 result.add(vertex3);
163 }
164
165 /**
166 * Sets all vertices of this triangle.
167 *
168 * @param vertex1 1st vertex.
169 * @param vertex2 2nd vertex.
170 * @param vertex3 3rd vertex.
171 * @throws NullPointerException Raised if any of the vertices is null.
172 */
173 public final void setVertices(final Point3D vertex1, final Point3D vertex2, final Point3D vertex3) {
174 if (vertex1 == null || vertex2 == null || vertex3 == null) {
175 throw new NullPointerException();
176 }
177
178 this.vertex1 = vertex1;
179 this.vertex2 = vertex2;
180 this.vertex3 = vertex3;
181 }
182
183 /**
184 * Returns area of provided triangle.
185 *
186 * @param triangle Triangle to be evaluated.
187 * @return Area of triangle.
188 */
189 public static double area(final Triangle3D triangle) {
190 return area(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3());
191 }
192
193 /**
194 * Returns area of the triangle formed by provided vertices.
195 *
196 * @param vertex1 1st vertex of a triangle.
197 * @param vertex2 2nd vertex of a triangle.
198 * @param vertex3 3rd vertex of a triangle.
199 * @return Area of a triangle.
200 */
201 public static double area(final Point3D vertex1, final Point3D vertex2, final Point3D vertex3) {
202 // The signed area of a triangle is half the determinant of its vectors,
203 // or half the modulus of the cross product of its vectors
204
205 // Hence, having the vectors of the triangle defined as:
206 // v1 = vertex2 - vertex1, and v2 = vertex3 - vertex1, then:
207 final var inhomX1 = vertex1.getInhomX();
208 final var inhomY1 = vertex1.getInhomY();
209 final var inhomZ1 = vertex1.getInhomZ();
210
211 // given triangle ABC made by vectors ab and ac
212 final var abX = vertex2.getInhomX() - inhomX1;
213 final var abY = vertex2.getInhomY() - inhomY1;
214 final var abZ = vertex2.getInhomZ() - inhomZ1;
215
216 final var acX = vertex3.getInhomX() - inhomX1;
217 final var acY = vertex3.getInhomY() - inhomY1;
218 final var acZ = vertex3.getInhomZ() - inhomZ1;
219
220 // the area of ABC is half the modulus of the cross product of
221 // vectors ab and ac
222 final var crossX = abY * acZ - abZ * acY;
223 final var crossY = abZ * acX - abX * acZ;
224 final var crossZ = abX * acY - abY * acX;
225
226 return 0.5 * Math.sqrt(crossX * crossX + crossY * crossY + crossZ * crossZ);
227 }
228
229 /**
230 * Returns area of this triangle.
231 *
232 * @return Area of this triangle.
233 */
234 public double getArea() {
235 return area(vertex1, vertex2, vertex3);
236 }
237
238 /**
239 * Determines whether vertices of this triangle are considered to be
240 * co-linear. Points are considered to be colinear when area of triangle is
241 * very small.
242 *
243 * @return True if vertices are colinear, false otherwise.
244 */
245 public boolean areVerticesColinear() {
246 return areVerticesColinear(DEFAULT_THRESHOLD);
247 }
248
249 /**
250 * Determines whether vertices of this triangle are considered to be
251 * co-linear up to certain threshold. Points are considered to be colinear
252 * when are of triangle is very small.
253 *
254 * @param threshold Threshold to determine whether vertices are colinear.
255 * Vertices will be colinear when area of triangle is smaller than provided
256 * threshold.
257 * @return True if vertices are colinear, false otherwise.
258 * @throws IllegalArgumentException Raised if provided threshold is negative.
259 */
260 public boolean areVerticesColinear(final double threshold) {
261 if (threshold < MIN_THRESHOLD) {
262 throw new IllegalArgumentException();
263 }
264 return getArea() <= threshold;
265 }
266
267 /**
268 * Returns perimeter of provided triangle.
269 *
270 * @param triangle Perimeter of provided triangle.
271 * @return Perimeter of provided triangle.
272 */
273 public static double perimeter(final Triangle3D triangle) {
274 return perimeter(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3());
275 }
276
277 /**
278 * Returns perimeter of triangle formed by provided vertices.
279 *
280 * @param vertex1 1st vertex of a triangle.
281 * @param vertex2 2nd vertex of a triangle.
282 * @param vertex3 3rd vertex of a triangle.
283 * @return Perimeter of a triangle.
284 */
285 public static double perimeter(final Point3D vertex1, final Point3D vertex2, final Point3D vertex3) {
286 return vertex1.distanceTo(vertex2) + vertex2.distanceTo(vertex3) + vertex3.distanceTo(vertex1);
287 }
288
289 /**
290 * Returns perimeter of this triangle.
291 *
292 * @return Perimeter of this triangle.
293 */
294 public double getPerimeter() {
295 return perimeter(this);
296 }
297
298 /**
299 * Indicates whether provided point lies inside this triangle or not.
300 * To lie inside point must be on the same plane formed by this triangle and
301 * within triangle boundaries.
302 *
303 * @param point Point to be checked.
304 * @return True if point lies inside this triangle, false otherwise.
305 */
306 public boolean isInside(final Point3D point) {
307 return isInside(point, DEFAULT_THRESHOLD);
308 }
309
310 /**
311 * Indicates whether provided point lies inside this triangle or not up to
312 * a certain threshold.
313 * To lie inside point must be on the same plane formed by this triangle and
314 * within triangle boundaries up to a certain threshold.
315 *
316 * @param point Point to be checked.
317 * @param threshold Threshold to determine whether point is inside this
318 * triangle, or not. This should usually be a small value.
319 * @return True if point lies inside this triangle, false otherwise.
320 * @throws IllegalArgumentException Raised if provided threshold is negative.
321 */
322 public boolean isInside(final Point3D point, final double threshold) {
323 return isInside(vertex1, vertex2, vertex3, point, threshold);
324 }
325
326 /**
327 * Indicates whether provided point lies inside provided triangle or not
328 * To lie inside point must be on the same plane formed by provided triangle
329 * and within triangle boundaries.
330 *
331 * @param triangle A triangle.
332 * @param point Point to be checked.
333 * @return True if point lies inside provided triangle, false otherwise.
334 */
335 public static boolean isInside(final Triangle3D triangle, final Point3D point) {
336 return isInside(triangle, point, DEFAULT_THRESHOLD);
337 }
338
339 /**
340 * Indicates whether provided point lies inside provided triangle or not up
341 * to a certain threshold.
342 * To lie inside point must be on the same plane formed by provided triangle
343 * and within triangle boundaries up to a certain threshold.
344 *
345 * @param triangle A triangle.
346 * @param point Point to be checked.
347 * @param threshold Threshold to determine whether point is inside this
348 * triangle, or not. This should usually be a small value.
349 * @return True if point lies inside this triangle, false otherwise.
350 * @throws IllegalArgumentException Raised if provided threshold is negative.
351 */
352 public static boolean isInside(final Triangle3D triangle, final Point3D point, final double threshold) {
353 return isInside(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3(), point, threshold);
354 }
355
356 /**
357 * Indicates whether provided point lies inside a triangle formed by
358 * provided vertices or not.
359 * To lie inside point must be on the same plane formed by that triangle and
360 * within its boundaries.
361 *
362 * @param vertex1 1st vertex of a triangle.
363 * @param vertex2 2nd vertex of a triangle.
364 * @param vertex3 3rd vertex of a triangle.
365 * @param point Point to be checked.
366 * @return True if point lies inside triangle formed by provided vertices,
367 * false otherwise.
368 */
369 public static boolean isInside(
370 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3, final Point3D point) {
371 return isInside(vertex1, vertex2, vertex3, point, DEFAULT_THRESHOLD);
372 }
373
374 /**
375 * Indicates whether provided point lies inside a triangle formed by
376 * provided vertices or not up to a certain threshold.
377 * To lie inside point must be on the same plane formed by that triangle and
378 * within its boundaries up to a certain threshold.
379 *
380 * @param vertex1 1st vertex of a triangle.
381 * @param vertex2 2nd vertex of a triangle.
382 * @param vertex3 3rd vertex of a triangle.
383 * @param point Point to be checked.
384 * @param threshold Threshold to determine whether point is inside the
385 * triangle formed by provided vertices or not. This should usually be a
386 * small value.
387 * @return True if point lies inside triangle formed by provided vertices,
388 * false otherwise.
389 * @throws IllegalArgumentException Raised if provided threshold is negative.
390 */
391 public static boolean isInside(
392 final Point3D vertex1, final Point3D vertex2,
393 final Point3D vertex3, final Point3D point, final double threshold) {
394 if (threshold < MIN_THRESHOLD) {
395 throw new IllegalArgumentException();
396 }
397 // given triangle ABC made by vectors:
398 // ab = p2 - p1, and ac = p3 - p1
399
400 // If point (x, y) lies within triangle ABC, then we have 3 sub-triangles
401 // ApB, BpC and ApC made of points:
402 // ApB: mVertex1, point, mVertex2
403 // BpC: mVertex2, point, mVertex3
404 // ApC: mVertex3, point, mVertex1
405
406 // The point will lie inside triangle ABC if the sum of the areas of the
407 // 3 sub-triangles ApB, BpC and ApC equals the area of triangle ABC (up to
408 // certain accuracy to account for numerical precision)
409
410 // Then the areas of triangles are:
411 final var areaABC = area(vertex1, vertex2, vertex3);
412
413 final var areaApB = area(vertex1, point, vertex2);
414 final var areaBpC = area(vertex2, point, vertex3);
415 final var areaApC = area(vertex3, point, vertex1);
416
417 return Math.abs(areaApB + areaBpC + areaApC - areaABC) <= threshold;
418 }
419
420 /**
421 * Returns the plane formed by the vertices of this triangle.
422 * The difference between a plane and a 3D triangle is that a triangle has
423 * its boundaries defined, whereas a plane extends up to the infinity.
424 *
425 * @return A plane.
426 * @throws ColinearPointsException Raised if vertices of this triangle are
427 * co-linear (triangle has area equal or very close to 0.0).
428 */
429 public Plane toPlane() throws ColinearPointsException {
430 return new Plane(vertex1, vertex2, vertex3);
431 }
432
433 /**
434 * Computes the plane formed by the vertices of this triangle and stores the
435 * result into provided Plane instance.
436 * The difference between a plane and a 3D triangle is that a triangle has
437 * its boundaries defined, whereas a plane extends up to the infinity.
438 *
439 * @param result Instance where resulting plane will be stored.
440 * @throws ColinearPointsException Raised if vertices of this triangle are
441 * co-linear (triangle has area equal or very close to 0.0).
442 */
443 public void toPlane(final Plane result) throws ColinearPointsException {
444 result.setParametersFromThreePoints(vertex1, vertex2, vertex3);
445 }
446
447 /**
448 * Returns center of this triangle, which is the result of averaging its
449 * vertices.
450 *
451 * @return Center of this triangle.
452 */
453 public Point3D getCenter() {
454 final var result = Point3D.create();
455 center(result);
456 return result;
457 }
458
459 /**
460 * Computes the center of this triangle and stores the result in provided
461 * point. The center of this triangle is computed as the average of its
462 * vertices.
463 *
464 * @param result Point instance where center will be stored.
465 */
466 public void center(final Point3D result) {
467 center(vertex1, vertex2, vertex3, result);
468 }
469
470 /**
471 * Computes the center of a triangle formed by provided vertices.
472 * The center is computed as the average of the three vertices.
473 *
474 * @param vertex1 1st vertex of a triangle.
475 * @param vertex2 2nd vertex of a triangle.
476 * @param vertex3 3rd vertex of a triangle.
477 * @return Center of a triangle formed by provided vertices.
478 */
479 public static Point3D center(final Point3D vertex1, final Point3D vertex2, final Point3D vertex3) {
480 final var result = Point3D.create();
481 center(vertex1, vertex2, vertex3, result);
482 return result;
483 }
484
485 /**
486 * Computes the center of provided triangle.
487 * The center is computed as the average of the vertices of provided
488 * triangle.
489 *
490 * @param t A triangle.
491 * @return Center of provided triangle.
492 */
493 public static Point3D center(final Triangle3D t) {
494 return center(t.getVertex1(), t.getVertex2(), t.getVertex3());
495 }
496
497 /**
498 * Computes the center of a triangle formed by provided vertices and stores
499 * the result in provided result point.
500 * The center is computed as the average of provided vertices.
501 *
502 * @param vertex1 1st vertex of a triangle.
503 * @param vertex2 2nd vertex of a triangle.
504 * @param vertex3 3rd vertex of a triangle.
505 * @param result Point instance where center will be stored.
506 */
507 public static void center(
508 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3, final Point3D result) {
509
510 final var x = (vertex1.getInhomX() + vertex2.getInhomX() + vertex3.getInhomX()) / 3.0;
511 final var y = (vertex1.getInhomY() + vertex2.getInhomY() + vertex3.getInhomY()) / 3.0;
512 final var z = (vertex1.getInhomZ() + vertex2.getInhomZ() + vertex3.getInhomZ()) / 3.0;
513
514 result.setInhomogeneousCoordinates(x, y, z);
515 }
516
517 /**
518 * Computes the center of provided triangle and stores the result in
519 * provided result point.
520 * The center is computed as the average of the vertices of provided
521 * triangle.
522 *
523 * @param t A triangle.
524 * @param result Point instance where center will be stored.
525 */
526 public static void center(final Triangle3D t, final Point3D result) {
527 center(t.getVertex1(), t.getVertex2(), t.getVertex3(), result);
528 }
529
530 /**
531 * Computes the shortest distance from a given point to the boundaries of
532 * this triangle, considering its boundaries as lines with a finite length
533 * Distance is computed up to triangle boundary, no matter if point lies
534 * inside the triangle or not.
535 *
536 * @param point Point to be checked.
537 * @return Shortest distance to this triangle.
538 */
539 public double getShortestDistance(final Point3D point) {
540 return shortestDistance(this, point);
541 }
542
543 /**
544 * Computes the shortest distance from a given point to the boundaries of
545 * provided triangle, considering its boundaries as lines with a finite
546 * length.
547 * Distance is computed up to triangle boundary, no matter if point lies
548 * inside the triangle or not.
549 *
550 * @param triangle A triangle.
551 * @param point Point to be checked.
552 * @return Shortest distance to this triangle.
553 */
554 public static double shortestDistance(final Triangle3D triangle, final Point3D point) {
555 return shortestDistance(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3(), point);
556 }
557
558 /**
559 * Computes the shortest distance from a given point to the boundaries of
560 * a triangle formed by provided vertices, where those boundaries are
561 * considered to be lines with a finite length.
562 * Distance is computed up to triangle boundary, no matter if point lies
563 * inside the triangle or not.
564 *
565 * @param vertex1 1st vertex of a triangle.
566 * @param vertex2 2nd vertex of a triangle.
567 * @param vertex3 3rd vertex of a triangle.
568 * @param point Point to be checked.
569 * @return Shortest distance to the triangle formed by provided vertices.
570 */
571 public static double shortestDistance(
572 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3, final Point3D point) {
573
574 // normalize points to increase accuracy
575 vertex1.normalize();
576 vertex2.normalize();
577 vertex3.normalize();
578 point.normalize();
579
580 var bestDist = Double.MAX_VALUE;
581 var dist = Double.MAX_VALUE;
582
583 Line3D line = null;
584 try {
585 line = new Line3D(vertex1, vertex2);
586 //to increase accuracy
587 line.normalize();
588 if (line.isLocus(point)) {
589 if (point.isBetween(vertex1, vertex2)) {
590 return 0.0;
591 } else {
592 // point is outside the triangle and
593 // point belongs to the line forming this side of the
594 // triangle, hence the closest vertex of this line will be
595 // the shortest distance
596 bestDist = vertex1.distanceTo(point);
597 dist = vertex2.distanceTo(point);
598 if (dist < bestDist) {
599 bestDist = dist;
600 }
601
602 return bestDist;
603 }
604 }
605
606 // point does not belong to the first line
607 bestDist = Math.abs(line.getDistance(point));
608 } catch (final CoincidentPointsException e) {
609 if (point.equals(vertex1)) {
610 return vertex1.distanceTo(point);
611 }
612 if (point.equals(vertex2)) {
613 return vertex2.distanceTo(point);
614 }
615 }
616
617 if (line == null) {
618 return bestDist;
619 }
620
621 // try on second side of the triangle
622 try {
623 line.setPlanesFromPoints(vertex1, vertex3);
624 // to increase accuracy
625 line.normalize();
626 if (line.isLocus(point)) {
627 if (point.isBetween(vertex1, vertex3)) {
628 return 0.0;
629 } else {
630 // point belongs to the line forming this side of the
631 // triangle, hence the closest vertex of this line will be
632 // the shortest distance
633 bestDist = vertex1.distanceTo(point);
634 dist = vertex3.distanceTo(point);
635 if (dist < bestDist) {
636 bestDist = dist;
637 }
638
639 return bestDist;
640 }
641 }
642
643 // point does not belong to the first or second line
644 dist = Math.abs(line.getDistance(point));
645 } catch (final CoincidentPointsException e) {
646 if (point.equals(vertex1)) {
647 return vertex1.distanceTo(point);
648 }
649 if (point.equals(vertex3)) {
650 return vertex3.distanceTo(point);
651 }
652 }
653
654 // check if second line is closest to first line
655 if (dist < bestDist) {
656 bestDist = dist;
657 }
658
659 // try on third side of the triangle
660 try {
661 line.setPlanesFromPoints(vertex2, vertex3);
662 // to increase accuracy
663 line.normalize();
664 if (line.isLocus(point)) {
665 if (point.isBetween(vertex2, vertex3)) {
666 return 0.0;
667 } else {
668 // point belongs to the line forming this side of the
669 // triangle, hence the closest vertex of this line will be
670 // the shortest distance
671 bestDist = vertex2.distanceTo(point);
672 dist = vertex3.distanceTo(point);
673 if (dist < bestDist) {
674 bestDist = dist;
675 }
676
677 return bestDist;
678 }
679 }
680
681 // point does not belong to any line forming a side of the triangle
682 dist = Math.abs(line.getDistance(point));
683 } catch (final CoincidentPointsException e) {
684 if (point.equals(vertex2)) {
685 return vertex2.distanceTo(point);
686 }
687 if (point.equals(vertex3)) {
688 return vertex3.distanceTo(point);
689 }
690 }
691
692 // check if distance to third line is the shortest
693 if (dist < bestDist) {
694 bestDist = dist;
695 }
696
697 return bestDist;
698 }
699
700 /**
701 * Returns the point which is locus of this triangle closest to provided
702 * point.
703 *
704 * @param point Point to be checked.
705 * @return Closest point laying in this triangle boundaries.
706 */
707 public Point3D getClosestPoint(final Point3D point) {
708 return getClosestPoint(point, DEFAULT_THRESHOLD);
709 }
710
711 /**
712 * Returns the point which is locus of this triangle (up to a certain
713 * threshold) closest to provided point.
714 *
715 * @param point Point to be checked.
716 * @param threshold Threshold to determine when a point is locus of this
717 * triangle or not.
718 * @return Closest point laying in this triangle boundaries.
719 * @throws IllegalArgumentException Raised if provided threshold is negative.
720 */
721 public Point3D getClosestPoint(final Point3D point, final double threshold) {
722 final var result = Point3D.create();
723 closestPoint(point, result, threshold);
724 return result;
725 }
726
727 /**
728 * Computes the point which is locus of this triangle closest to provided
729 * point and stores the result in provided result point.
730 *
731 * @param point Point to be checked.
732 * @param result Point where result will be stored.
733 */
734 public void closestPoint(final Point3D point, final Point3D result) {
735 closestPoint(point, result, DEFAULT_THRESHOLD);
736 }
737
738 /**
739 * Computes the point which is locus of this triangle (up to a certain
740 * threshold) closest to provided point and stores the result in provided
741 * result point.
742 *
743 * @param point Point to be checked.
744 * @param result Point where result will be stored.
745 * @param threshold Threshold to determine when a point is locus of this
746 * triangle or not.
747 * @throws IllegalArgumentException Raised if provided threshold is negative.
748 */
749 public void closestPoint(final Point3D point, final Point3D result, final double threshold) {
750 if (threshold < MIN_THRESHOLD) {
751 throw new IllegalArgumentException();
752 }
753
754 // normalize vertices and point to increase accuracy
755 vertex1.normalize();
756 vertex2.normalize();
757 vertex3.normalize();
758 point.normalize();
759
760 Line3D line1;
761 Line3D line2;
762 Line3D line3;
763 try {
764 line1 = new Line3D(vertex1, vertex2);
765 // to increase accuracy
766 line1.normalize();
767 if (line1.isLocus(point)) {
768 if (point.isBetween(vertex1, vertex2)) {
769 // point is on this side of the triangle, so point must
770 // be the result
771 result.setCoordinates(point);
772 } else {
773 // point belongs to the line forming this side of the
774 // triangle, hence the closest vertex of this line will be
775 // the closest point to the triangle
776 final var dist1 = vertex1.distanceTo(point);
777 final var dist2 = vertex2.distanceTo(point);
778 if (dist1 < dist2) {
779 result.setCoordinates(vertex1);
780 } else {
781 result.setCoordinates(vertex2);
782 }
783 }
784 return;
785 }
786 } catch (final CoincidentPointsException e) {
787 if (point.equals(vertex1) || point.equals(vertex2)) {
788 result.setCoordinates(point);
789 }
790 return;
791 }
792
793
794 // try on second side of the triangle
795 try {
796 line2 = new Line3D(vertex1, vertex3);
797 // to increase accuracy
798 line2.normalize();
799 if (line2.isLocus(point)) {
800 if (point.isBetween(vertex1, vertex3)) {
801 // point is on this side of the triangle, so point must be
802 // the result
803 result.setCoordinates(point);
804 } else {
805 // point belongs to the line forming this side of the
806 // triangle, hence the closest vertex of this line will be
807 // the closest point to the triangle
808 final var dist1 = vertex1.distanceTo(point);
809 final var dist3 = vertex3.distanceTo(point);
810 if (dist1 < dist3) {
811 result.setCoordinates(vertex1);
812 } else {
813 result.setCoordinates(vertex3);
814 }
815 }
816 return;
817 }
818 } catch (final CoincidentPointsException e) {
819 if (point.equals(vertex1) || point.equals(vertex3)) {
820 result.setCoordinates(point);
821 }
822 return;
823 }
824
825
826 // try on third side of the triangle
827 try {
828 line3 = new Line3D(vertex2, vertex3);
829 // to increase accuracy
830 line3.normalize();
831 if (line3.isLocus(point)) {
832 if (point.isBetween(vertex2, vertex3)) {
833 // point is on this side of the triangle, so point must be
834 // the result
835 result.setCoordinates(point);
836 } else {
837 // point belongs to the line forming this side of the
838 // triangle, hence the closest vertex of this line will be
839 // the closest point to the triangle
840 final var dist2 = vertex2.distanceTo(point);
841 final var dist3 = vertex3.distanceTo(point);
842 if (dist2 < dist3) {
843 result.setCoordinates(vertex2);
844 } else {
845 result.setCoordinates(vertex3);
846 }
847 }
848 return;
849 }
850 } catch (final CoincidentPointsException e) {
851 if (point.equals(vertex2) || point.equals(vertex3)) {
852 result.setCoordinates(point);
853 }
854 return;
855 }
856
857
858 // point does not belong to any line forming a side of the triangle,
859 // so we find the closest point for each side
860 Point3D closest1;
861 Point3D closest2;
862 Point3D closest3;
863
864 closest1 = line1.getClosestPoint(point, threshold);
865 // to increase accuracy
866 closest1.normalize();
867
868 closest2 = line2.getClosestPoint(point, threshold);
869 // to increase accuracy
870 closest2.normalize();
871
872 closest3 = line3.getClosestPoint(point, threshold);
873 // to increase accuracy
874 closest3.normalize();
875
876 // check if points lie within sides of triangle
877 final var between1 = closest1.isBetween(vertex1, vertex2);
878 final var between2 = closest2.isBetween(vertex1, vertex3);
879 final var between3 = closest3.isBetween(vertex2, vertex3);
880
881 final var distClosest1 = closest1.distanceTo(point);
882 final var distClosest2 = closest2.distanceTo(point);
883 final var distClosest3 = closest3.distanceTo(point);
884
885 final var distVertex1 = vertex1.distanceTo(point);
886 final var distVertex2 = vertex2.distanceTo(point);
887 final var distVertex3 = vertex3.distanceTo(point);
888
889 if (between1 && !between2 && !between3) {
890 // choose closest1 or opposite vertex (vertex3)
891 if (distClosest1 < distVertex3) {
892 result.setCoordinates(closest1);
893 } else {
894 result.setCoordinates(vertex3);
895 }
896 } else if (!between1 && between2 && !between3) {
897 // choose closest2 or opposite vertex (vertex2)
898 if (distClosest2 < distVertex2) {
899 result.setCoordinates(closest2);
900 } else {
901 result.setCoordinates(vertex2);
902 }
903 } else if (!between1 && !between2 && between3) {
904 // choose closest3 or opposite vertex (vertex1)
905 if (distClosest3 < distVertex1) {
906 result.setCoordinates(closest3);
907 } else {
908 result.setCoordinates(vertex1);
909 }
910 } else if (between1 && between2 && !between3) {
911 // determine if closest1 or closest2
912 if (distClosest1 < distClosest2) {
913 result.setCoordinates(closest1);
914 } else {
915 result.setCoordinates(closest2);
916 }
917 } else if (!between1 && between2) {
918 // and between3
919
920 // determine if closest2 or closest3
921 if (distClosest2 < distClosest3) {
922 result.setCoordinates(closest2);
923 } else {
924 result.setCoordinates(closest3);
925 }
926 } else if (between1 && !between2) {
927 // and between3
928
929 // determine if closest1 or closest3
930 if (distClosest1 < distClosest3) {
931 result.setCoordinates(closest1);
932 } else {
933 result.setCoordinates(closest3);
934 }
935 } else if (between1) {
936 // and between2 and between3
937
938 // determine if closest1, closest2 or closest3
939 if (distClosest1 < distClosest2 && distClosest1 < distClosest3) {
940 // pick closest1
941 result.setCoordinates(closest1);
942 } else if (distClosest2 < distClosest1 && distClosest2 < distClosest3) {
943 // pick closest2
944 result.setCoordinates(closest2);
945 } else {
946 // pick closest3
947 result.setCoordinates(closest3);
948 }
949 } else {
950 // all closest points are outside vertex limits, so we pick the
951 // closest vertex
952 if (distVertex1 < distVertex2 && distVertex1 < distVertex3) {
953 // pick vertex1
954 result.setCoordinates(vertex1);
955 } else if (distVertex2 < distVertex1 && distVertex2 < distVertex3) {
956 // pick vertex2
957 result.setCoordinates(vertex2);
958 } else {
959 // pick vertex3
960 result.setCoordinates(vertex3);
961 }
962 }
963 }
964
965 /**
966 * Returns boolean indicating if provided point is locus of this triangle
967 * (i.e. lies within this triangle boundaries) up to a certain threshold.
968 *
969 * @param point Point to be checked.
970 * @param threshold Threshold to determine if point is locus or not. This
971 * should usually be a small value.
972 * @return True if provided point is locus, false otherwise.
973 * @throws IllegalArgumentException Raised if provided threshold is negative.
974 */
975 public boolean isLocus(final Point3D point, final double threshold) {
976 if (threshold < MIN_THRESHOLD) {
977 throw new IllegalArgumentException();
978 }
979
980 return point.isBetween(vertex1, vertex2, threshold) || point.isBetween(vertex1, vertex3, threshold)
981 || point.isBetween(vertex2, vertex3, threshold);
982 }
983
984 /**
985 * Returns boolean indicating if provided point is locus of this triangle
986 * (i.e. lies within this triangle boundaries).
987 *
988 * @param point Point to be checked.
989 * @return True if provided point is locus, false otherwise.
990 */
991 public boolean isLocus(final Point3D point) {
992 return isLocus(point, DEFAULT_THRESHOLD);
993 }
994
995
996 /**
997 * Returns array containing orientation of this 3D triangle.
998 *
999 * @return Array containing orientation of this 3D triangle.
1000 * @throws CoincidentPointsException Raised if vertices of this triangle
1001 * are too close to each other.
1002 */
1003 public double[] getOrientation() throws CoincidentPointsException {
1004 return orientation(this);
1005 }
1006
1007 /**
1008 * Returns array containing orientation of this 3D triangle.
1009 *
1010 * @param threshold Threshold to determine whether vertices of this triangle
1011 * are coincident or not.
1012 * @return Array containing orientation of this 3D triangle.
1013 * @throws IllegalArgumentException Raised if provided threshold is negative.
1014 * @throws CoincidentPointsException Raised if vertices of this triangle
1015 * are too close to each other.
1016 */
1017 public double[] getOrientation(final double threshold) throws CoincidentPointsException {
1018 return orientation(this, threshold);
1019 }
1020
1021 /**
1022 * Computes orientation of this 3D triangle and stores the result in
1023 * provided array.
1024 *
1025 * @param result Array where orientation is stored.
1026 * @throws IllegalArgumentException Raised if provided array does not have
1027 * length 3.
1028 * @throws CoincidentPointsException Raised if vertices of this triangle
1029 * are too close to each other.
1030 */
1031 public void orientation(final double[] result) throws CoincidentPointsException {
1032 orientation(this, result);
1033 }
1034
1035 /**
1036 * Computes orientation of this 3D triangle and stores the result in
1037 * provided array.
1038 *
1039 * @param result Array where orientation is stored.
1040 * @param threshold Threshold to determine whether vertices of this triangle
1041 * are coincident or not.
1042 * @throws IllegalArgumentException Raised if provided threshold is negative
1043 * or if provided array does not have length 3.
1044 * @throws CoincidentPointsException Raised if vertices of this triangle
1045 * are too close to each other.
1046 */
1047 public void orientation(final double[] result, final double threshold) throws CoincidentPointsException {
1048 orientation(this, result, threshold);
1049 }
1050
1051 /**
1052 * Returns orientation of provided 3D triangle.
1053 *
1054 * @param triangle A triangle.
1055 * @return Array containing orientation of provided 3D triangle.
1056 * @throws CoincidentPointsException Raised if vertices of provided triangle
1057 * are too close to each other.
1058 */
1059 public static double[] orientation(final Triangle3D triangle) throws CoincidentPointsException {
1060 return orientation(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3());
1061 }
1062
1063 /**
1064 * Returns orientation of provided 3D triangle.
1065 *
1066 * @param triangle A triangle.
1067 * @param threshold Threshold to determine whether vertices of provided
1068 * triangle are coincident or not.
1069 * @return Array containing orientation of provided 3D triangle.
1070 * @throws IllegalArgumentException Raised if provided threshold is negative.
1071 * @throws CoincidentPointsException Raised if vertices of this triangle are
1072 * too close to each other.
1073 */
1074 public static double[] orientation(final Triangle3D triangle, final double threshold)
1075 throws CoincidentPointsException {
1076 return orientation(triangle.getVertex1(), triangle.getVertex2(),
1077 triangle.getVertex3(), threshold);
1078 }
1079
1080 /**
1081 * Computes orientation of provided 3D triangle and stores the result in
1082 * provided array.
1083 *
1084 * @param triangle A triangle.
1085 * @param result Array where orientation is stored.
1086 * @throws IllegalArgumentException Raised if provided array does not have
1087 * length 3.
1088 * @throws CoincidentPointsException Raised if vertices of provided triangle
1089 * are too close to each other.
1090 */
1091 public static void orientation(final Triangle3D triangle, final double[] result) throws CoincidentPointsException {
1092 orientation(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3(), result);
1093 }
1094
1095 /**
1096 * Computes orientation of provided 3D triangle and stores the result in
1097 * provided array.
1098 *
1099 * @param triangle A triangle.
1100 * @param result Array where orientation is stored.
1101 * @param threshold Threshold to determine whether vertices of provided
1102 * triangle are coincident or not.
1103 * @throws IllegalArgumentException Raised if provided threshold is negative
1104 * or if array does not have length 3.
1105 * @throws CoincidentPointsException Raised if vertices of provided triangle
1106 * are too close to each other.
1107 */
1108 public static void orientation(
1109 final Triangle3D triangle, final double[] result, final double threshold) throws CoincidentPointsException {
1110 orientation(triangle.getVertex1(), triangle.getVertex2(), triangle.getVertex3(), result, threshold);
1111 }
1112
1113 /**
1114 * Returns orientation of 3D triangle formed by provided vertices.
1115 *
1116 * @param vertex1 1st vertex.
1117 * @param vertex2 2nd vertex.
1118 * @param vertex3 3rd vertex.
1119 * @return Array containing triangle orientation.
1120 * @throws CoincidentPointsException Raised if provided vertices are too
1121 * close to each other.
1122 */
1123 public static double[] orientation(
1124 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3) throws CoincidentPointsException {
1125 return orientation(vertex1, vertex2, vertex3, DEFAULT_THRESHOLD);
1126 }
1127
1128 /**
1129 * Returns orientation of 3D triangle formed by provided vertices.
1130 *
1131 * @param vertex1 1st vertex.
1132 * @param vertex2 2nd vertex.
1133 * @param vertex3 3rd vertex.
1134 * @param threshold Threshold to determine whether provided vertices are
1135 * coincident or not.
1136 * @return Array containing triangle orientation.
1137 * @throws IllegalArgumentException Raised if provided threshold is negative.
1138 * @throws CoincidentPointsException Raised if provided vertices are too
1139 * close to each other.
1140 */
1141 public static double[] orientation(
1142 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3, final double threshold)
1143 throws CoincidentPointsException {
1144 final var result = new double[INHOM_COORDS];
1145 orientation(vertex1, vertex2, vertex3, result, threshold);
1146 return result;
1147 }
1148
1149 /**
1150 * Computes orientation of 3D triangle formed by provided vertices and
1151 * stores the result in provided array.
1152 *
1153 * @param vertex1 1st vertex.
1154 * @param vertex2 2nd vertex.
1155 * @param vertex3 3rd vertex.
1156 * @param result Array where triangle orientation is stored.
1157 * @throws IllegalArgumentException Raised if provided array does not have
1158 * length 3.
1159 * @throws CoincidentPointsException Raised if provided vertices are too
1160 * close to each other.
1161 */
1162 public static void orientation(
1163 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3, final double[] result)
1164 throws CoincidentPointsException {
1165 orientation(vertex1, vertex2, vertex3, result, DEFAULT_THRESHOLD);
1166 }
1167
1168 /**
1169 * Computes orientation of 3D triangle formed by provided vertices and
1170 * stores the result in provided array.
1171 *
1172 * @param vertex1 1st vertex.
1173 * @param vertex2 2nd vertex.
1174 * @param vertex3 3rd vertex.
1175 * @param result Array where triangle orientation is stored.
1176 * @param threshold Threshold to determine whether provided vertices are
1177 * coincident or not.
1178 * @throws IllegalArgumentException Raised if threshold is negative or if
1179 * provided array does not have length 3.
1180 * @throws CoincidentPointsException Raised if provided vertices are too
1181 * close to each other.
1182 */
1183 public static void orientation(
1184 final Point3D vertex1, final Point3D vertex2, final Point3D vertex3, final double[] result,
1185 final double threshold) throws CoincidentPointsException {
1186
1187 if (threshold < MIN_THRESHOLD) {
1188 throw new IllegalArgumentException();
1189 }
1190 if (result.length != INHOM_COORDS) {
1191 throw new IllegalArgumentException();
1192 }
1193
1194 final var inhomX1 = vertex1.getInhomX();
1195 final var inhomY1 = vertex1.getInhomY();
1196 final var inhomZ1 = vertex1.getInhomZ();
1197
1198 final var inhomX2 = vertex2.getInhomX();
1199 final var inhomY2 = vertex2.getInhomY();
1200 final var inhomZ2 = vertex2.getInhomZ();
1201
1202 final var inhomX3 = vertex3.getInhomX();
1203 final var inhomY3 = vertex3.getInhomY();
1204 final var inhomZ3 = vertex3.getInhomZ();
1205
1206 // given triangle ABC made by vectors ab and ac
1207 final var abX = inhomX2 - inhomX1;
1208 final var abY = inhomY2 - inhomY1;
1209 final var abZ = inhomZ2 - inhomZ1;
1210
1211 final var acX = inhomX3 - inhomX1;
1212 final var acY = inhomY3 - inhomY1;
1213 final var acZ = inhomZ3 - inhomZ1;
1214
1215 // the area of ABC is half the modulus of the cross product of
1216 // vectors ab and ac
1217 var crossX = abY * acZ - abZ * acY;
1218 var crossY = abZ * acX - abX * acZ;
1219 var crossZ = abX * acY - abY * acX;
1220 // normalize orientation vector
1221 var norm = Math.sqrt(crossX * crossX + crossY * crossY + crossZ * crossZ);
1222
1223 if (norm < threshold) {
1224 throw new CoincidentPointsException();
1225 }
1226
1227 crossX /= norm;
1228 crossY /= norm;
1229 crossZ /= norm;
1230
1231 result[0] = crossX;
1232 result[1] = crossY;
1233 result[2] = crossZ;
1234 }
1235
1236 /**
1237 * Returns the angle formed by the two provided triangles, assuming that
1238 * each triangle forms a plane.
1239 *
1240 * @param triangle1 1st triangle.
1241 * @param triangle2 2nd triangle.
1242 * @return Angle formed by the two provided triangles expressed in radians.
1243 * @throws CoincidentPointsException Raised if vertices in a triangle are
1244 * too close. This usually indicates numerical instability or triangle
1245 * degeneracy.
1246 */
1247 public static double getAngleBetweenTriangles(final Triangle3D triangle1, final Triangle3D triangle2)
1248 throws CoincidentPointsException {
1249 return getAngleBetweenTriangles(triangle1.getOrientation(), triangle2.getOrientation());
1250 }
1251
1252 /**
1253 * Internal method to compute the angle between two triangles using the
1254 * vectors containing the director vector of their corresponding planes
1255 * (i.e. their orientations).
1256 *
1257 * @param orientation1 Orientation of 1st triangle.
1258 * @param orientation2 Orientation of 2nd triangle.
1259 * @return Angle formed by the two triangles expressed in radians.
1260 * @throws IllegalArgumentException Raised if provided orientation arrays
1261 * don't have length 3.
1262 */
1263 private static double getAngleBetweenTriangles(
1264 final double[] orientation1, final double[] orientation2) {
1265 if (orientation1.length != INHOM_COORDS ||
1266 orientation2.length != INHOM_COORDS) {
1267 throw new IllegalArgumentException();
1268 }
1269
1270 final var x1 = orientation1[0];
1271 final var y1 = orientation1[1];
1272 final var z1 = orientation1[2];
1273
1274 final var x2 = orientation2[0];
1275 final var y2 = orientation2[1];
1276 final var z2 = orientation2[2];
1277
1278 final var norm1 = Math.sqrt(x1 * x1 + y1 * y1 + z1 * z1);
1279 final var norm2 = Math.sqrt(x2 * x2 + y2 * y2 + z2 * z2);
1280
1281 final var dotProduct = (x1 * x2 + y1 * y2 + z1 * z2) / (norm1 * norm2);
1282
1283 return Math.acos(dotProduct);
1284 }
1285 }