Is there an algorithm to quickly find the most does one shape the other?

Welcome!
Need the fastest way to find does a fully one other figure on the plane except brute force.
The figure is specified as a set of points with coordinates X, Y clockwise.
Would be glad if the algorithm was in Russian.

Yet came up with only this: in a circle we go around the figure, take her, laid from her segment on the OX axis, and consider the intersection of this segment with each segment between adjacent points of another shape. If the odd on the inside, if even, outside. If one was outside, then stop, otherwise we consider it further.

Get it out, but're dead slow.
July 4th 19 at 23:10
3 answers
July 4th 19 at 23:12
Solution
This can be done through 2 projection on the axis 0x and 0y for each figure. In the end we get the 4 lines. Compare the coordinates of the two segments on the same straight line, if both projections of the first figure "absorb" the projection of the second, it means that the figure 2 is the figure 1.

The algorithm
struct Plane {
 int px1 = 0;
 int px2 = 0;
 int py1 = 0;
 int py2 = 0;
};

Plane getPlane(const QPolygon &shape) {
 Plane plane;
 plane.px1 = shape.at(0).x();
 plane.px2 = plane.px1;
 plane.py1 = shape.at(0).y();
 plane.py2 = plane.py1;

 foreach (const QPoint &point, shape) {
 if(point.x() < plane.px1) plane.px1 = point.x();
 if(point.x() > plane.px2) plane.px2 = point.x();
 if(point.y() < plane.py1) plane.py1 = point.y();
 if(point.y() > plane.py2) plane.py2 = point.y();
}

 return plane;
}

void test()
{
 QPolygon shapeA;
shapeA.append(QPoint(100,100));
shapeA.append(QPoint(of 120.90));
shapeA.append(QPoint(150,110));
shapeA.append(QPoint(150,130));
shapeA.append(QPoint(120,140));
shapeA.append(QPoint(90,130));

 QPolygon shapeB;
shapeB.append(QPoint(100,120));
shapeB.append(QPoint(110,110));
shapeB.append(QPoint(140,120));
shapeB.append(QPoint(120,130));
shapeB.append(QPoint(100,190));

 PlaneA Plane = getPlane(shapeA);
 Plane planeB = getPlane(shapeB);

 if(planeA.px1 < planeB.px1
 && planeA.px2 > planeB.px2
 && planeA.py1 < planeB.py1
 && planeA.py2 > planeB.py2) {
 qDebug() << "Figure B in figure A!";
}
 else if(planeA.px1 > planeB.px1
 && planeA.px2 < planeB.px2
 && planeA.py1 > planeB.py1
 && planeA.py2 < planeB.py2) {
 qDebug() << "Shape A figure!";
}
 else {
 /* nothing */
};
}



It can be supplemented with conditions on the detection of incomplete instances. The algorithm is very easy, but it has a drawback: it only works with convex shapes. If the shape is in the shape of a horseshoe and in the middle of this horseshoe is a different shape, the algorithm will decide what figures are in each other.

Here is the implementation with a detailed description www.gamedev.ru/code/articles/?id=4195
July 4th 19 at 23:14
Solution
1. It is necessary to specify not only that all the points of the first figure within a second, but that all points to a second shape on the outside first.
2. Even a primitive algorithm gives the rate O(mn). You have approximately how many points?
3. You can use heuristics. If the bounding rectangle of 1 figure entirely in the 2nd, YES. If it gets out of covering rectangle 2-y — NO.
4. You can do so. Let's sort all points of the shape check on the points by X-coordinate. Also sort all the intervals of the shape check on the segments by X-coordinate left point. Index segment set in the beginning of the list of segments. Start the list of active segments. Go through all points in doing so...
• For all segments in the list active: if the point out of [X1, X2) — excluded from the list!
• Look at the period that is under the pointer. If the point's X >= X1 — go figure-on; if at the same time X < X2 and Y above the line (X1,X2 (Y1,Y2) — switch on the cut list.
When a specific device list (very X2) have O(n log n). And if a smaller figure is about as most (i.e. not the logarithm) are winning.
1. in the agoritm, that is - why, after all, considered crossing it?
2. points at the moment 10 thousand, but the algorithm should be fast for video processing.
3. not always, unfortunately (for example the first figure in the form of letters and the second in the form of a square that exactly fits into it)
4. need to check, because I haven't looked specifically at the forms of the figures, I know for sure that is both salient and not, but certainly not self-intersecting. But I want to get away from Robin. - darrell commented on July 4th 19 at 23:17
1. There are counterexamples — for example, a concave "thorn"
2. This is serious, n2 does not roll.
3. She and heuristics. - Humberto_Lynch68 commented on July 4th 19 at 23:20
Slightly tweaked the algorithm. - Humberto_Lynch68 commented on July 4th 19 at 23:23
:
1. hmm, I agree. the difficulty is added =((( - darrell commented on July 4th 19 at 23:26
I said "linked list"? No, a lot. - Humberto_Lynch68 commented on July 4th 19 at 23:29
July 4th 19 at 23:16
Solution
You need the algorithm of intersection of the segments. This is already approved by us ;)
for example, the Algorithm of Bentley — ottmann of
Oh and can about bikes to read
https://habrahabr.ru/post/267461/
https://habrahabr.ru/post/267037/
As an option, thanks. - darrell commented on July 4th 19 at 23:19

Find more questions by tags AlgebraAlgorithmsGeometry