How to determine the superposition of two geometric bodies?

Question

Java

Good day.

Faced with an interesting problem, I would like to ask the opinion of the Habra community.

There are geometric objects defined by some point (Position, in simple shapes such as a rectangle or circle, this will be the center of mass, in more complex ones it is not clear) and a list of vectors indicating the corners of this figure, based on the position point. For example, for a rectangle with length 10 and width 6 with position (0, 0), the vectors would be:
[-5, -3];
[-5, 3];
[5, 3];
[5, -3];

Question: how to determine (in the general case, for any figures) whether two figures overlap each other?

I have an idea: If the minimum distance from the position of figure 1 to the corners of figure 2 is less than any distance from the position of figure 1 to the corners of figure 1, then they overlap (and, accordingly, the same check for figure 2). But I don't like it, it's too complicated, it's not pretty... Do you have any better solutions?

Thanks in advance

Answer 1

1. Check all segments for intersection. Find if the shapes intersect. It remains to find whether the figures are nested. One figure is nested in another, if all points of the figure are nested in another (the problem is to determine whether the point is inside the polygon)
2. Algorithm of the scanning line. As events: vertices of polygons, points of intersection of segments (there is a suspicion that you can do without them). We store the sides of the polygons in the set, while we move the line, their vertical position changes, but the relative position should not change

Answer 2

Then it's easier to check whether any two sides (from different polygons) intersect or not. A dumb algorithm will be quadratic. You can use the sweep line algorithm, which runs in O(nlogn) time. There is a description in Russian in the book Preparata and Sheimos (edition 1989) "Computational Geometry" p. 341 and below.
PS: The rectangle from your example will have a length of 10 and a width of 6, not 5 and 3...

Answer 3

The answer is here - algolist.ru/maths/geom