CODEWITHSUNDEEP
algorithmgeometryintersection
Кирилл Ровнер
Кирилл Ровнер

Reputation: 19

Is there any way to found box triangle intersection section or its area?

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.

Upvotes: 1

Views: 432

Answers (3)

Кирилл Ровнер
Кирилл Ровнер

Reputation: 19

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.

Upvotes: 0

user1196549
user1196549

Reputation:

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.

enter image description here

Upvotes: 2

genius
genius

Reputation: 19

Note that it is worth considering only the following points:

  1. Intersection of the box and triangle;
  2. The vertices of the triangle inside the box;
  3. 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.

Upvotes: 1

Related Questions