I am trying to develop algorithm to find out not only the fact of intersection but its section or maybe its area. I found at least 6 different cases which may occur and I suppose that there are many more. That is why I am looking for universal algorithm neither try to solve each case separately. I am working with 3D box.
Asked
Active
Viewed 297 times
1
-
Hi! Welcome to StackOverflow. You might be interested in these near-duplicate questions: [Intersection of two convex polygons](https://stackoverflow.com/questions/13101288/intersection-of-two-convex-polygons), [A simple algorithm for polygon intersection](https://stackoverflow.com/questions/2272179/a-simple-algorithm-for-polygon-intersection), – Stef Sep 16 '21 at 10:55
-
[How do I determine if two convex polygons intersect?](https://stackoverflow.com/questions/753140/how-do-i-determine-if-two-convex-polygons-intersect), [Algorithm for area of polygons intersection](https://stackoverflow.com/questions/29295626/algorithm-for-area-of-polygons-intersection), [Checking convex polygon intersection in less than O(n)?](https://stackoverflow.com/questions/35289376/checking-convex-polygon-intersection-in-less-than-on) – Stef Sep 16 '21 at 10:55
-
Your second reference is about the intersection of general polygons. Even though a (very good) ready-made software is available, it may be overkill for the present case. – Sep 17 '21 at 12:51
3 Answers
2
As a triangle and a box are convex shapes, you can use the Sutherland-Hodgman algorithm. https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
It amounts to finding the intersection of a polygon with a half-plane, and repeat this with every side of one of the shapes, against the other. Then the area is found by the shoelace formula.
In the case of an axis-aligned box, the computation is simpler.
-
You provided a solution for 2d case, I am currently working with 3D box – Кирилл Ровнер Sep 17 '21 at 19:29
-
@КириллРовнер: haha, yo changed the question after the fact. But he method is easy to generalize to 3D, you should have guessed. – Sep 20 '21 at 07:20
-
Yes, that is why I didn’t say that you’re totally wrong. In my opinion it is not the best way to use with algorithm in 3D case. Maybe with box and pyramid but not with triangle – Кирилл Ровнер Sep 20 '21 at 10:50
-
-
Because in 3D algorithm there are 4 adjacent faces for each face. I have no idea how to iterate in the right order – Кирилл Ровнер Sep 20 '21 at 10:55
-
1
Note that it is worth considering only the following points:
- Intersection of the box and triangle;
- The vertices of the triangle inside the box;
- The vertices of the box inside the triangle. (There are famous algorithms to find these points) These points are vertices of the polygon that is the desired Intersection section, but we need to sort these points in correct order. You can do this using Graham's algorithm for finding a convex hull. So, we have found a polygon that is box triangle intersection section. You also can find it's area using one of the famous algorithms.
genius
- 19
- 1
-
Thank you so much! I was just stumped because I didn't realize whether there is a possibility to sort points – Кирилл Ровнер Sep 16 '21 at 11:21
-
-
This answer is confuse and incomplete. I am not sure that "There are famous algorithms to find these points" be so helpful. – Sep 16 '21 at 19:30
0
Finally I came to solution bu myself. I just intersect my box with edges of triangle to get points inside box or its faces. So I have points of my convex in the wrong order. To solve with problem I use the fact that all the points belong to one plane that is why I can find point by arithmetic mean of convex points which lies exactly inside the convex and use polar coordinates to get angle of each point. All that remains just sort the angles and we will get sorted convex.
Кирилл Ровнер
- 19
- 4