Given:

1) A complex body (landscape mesh) consisting of triangular polygons

2) A simple body (for example, a cylinder). For him, the center point and all its measurements are known.

We need an algorithm for determining the presence of the intersection of these two bodies. At the same time, a complex body is much larger than a simple one (in size and number of vertices).

The main task is to answer as quickly as possible whether there is an intersection between these bodies. Pretreatment of a complex body is allowed.

What are some approaches to solve this problem?

I’ll also say right away that we need an algorithm, and not some kind of physics engine, which will determine all this by itself.

    2 answers 2

    Break the search into stages. The first is a rough cut, in the extreme coordinates of the bodies. If a collision is not found, then the bodies do not intersect. If found, then transgress to a detailed cut-off of landfills that fall into this area.

    You can read in more detail about the algorithms Sweep And Prune and V-Clip

    enter image description here enter image description here

      If you want fast - you need mathematically:

      In fact, it is necessary to check for the intersection of each primitive of which a complex body with a cylinder consists.

      Suppose we know the equation of the surface of some part of a complex body, then having a solution of a system of two equations, in which the first is the equation of this surface and the second is the parametric (or some other) equation of the cylinder, will they give the answer if they intersect (do they have common points).

      If at least one part has an intersection, the algorithm stops, otherwise there are no intersections.