How to calculate if many polygons intersect?

Question

JavaScript

There are many similar figures.

I want to draw them randomly. But it is necessary that they do not intersect.
How can this be implemented?
Shapes in svg path format, draw on canvas.

Answer 1

Thanks everyone for the replies!
I was helped by the article Basic theory of collision of objects, sprites on ... . There is also a code for determining whether a point belongs to a polygon.

function pointInPoly(polyCords, pointX, pointY)
{
  var i, j, c = 0;
 
  for (i = 0, j = polyCords.length - 1; i < polyCords.length; j = i++)
  {
 
    if (((polyCords[i][1] > pointY) != (polyCords[j][1] > pointY)) && (pointX < (polyCords[j][0] - polyCords[i][0]) * (pointY - polyCords[i][1]) / (polyCords[j][1] - polyCords[i][1]) + polyCords[i][0]))
    {
      c = !c;
    }
 
  }
 
  return c;
}

I also found a code for determining the intersections of polygons.

function crossLine(l1,l2) {
    var dx1 = l1[1][0] - l1[0][0],
        dy1 = l1[1][1] - l1[0][1],
        dx2 = l2[1][0] - l2[0][0],
        dy2 = l2[1][1] - l2[0][1],
        x = dy1 * dx2 - dy2 * dx1;

    if(!x, !dx2) {
        return false;
    }

    var y = l2[0][0] * l2[1][1] - l2[0][1] * l2[1][0];
    x = ((l1[0][0] * l1[1][1] - l1[0][1] * l1[1][0]) * dx2 - y * dx1) / x;
    y = (dy2 * x - y) / dx2;

    return ((l1[0][0] <= x && l1[1][0] >= x) || (l1[1][0] <= x && l1[0][0] >= x)) &&
           ((l2[0][0] <= x && l2[1][0] >= x) || (l2[1][0] <= x && l2[0][0] >= x));
}

But it was not needed, since my figures consist of a large number of polygons.

Answer 2

In short, you need to store in some structure all the segments (sides) of each polygon in the form of pairs (x1, y1 , x2, y2), as well as the coordinates of the edges. Then When adding, you need to compare the polygon you want to add with all polygons. The essence of the comparison is to check the intersection of segments. THOSE. compare segments with each other. The total time to compare two polygons is N^M, where N and M are the number of polygon segments. In order not to waste resources for comparing polygons that cannot intersect each other, first compare the coordinates of the edges.
UPD:
As noted by Sergei Sokolovwe need to check the possibility of occurrence of one figure in another. To do this, in addition, you need, for example, to check the occurrence of a point of one polygon in another. Also NM operations.

Answer 3

Alternatively, you can split the plane into a set of guaranteed non-intersecting polygons. And when adding a polygon, place it in an unoccupied cell. This will not solve the problem in the general case. But for a particular case, it may turn out to be a simple acceptable solution. For example, you can divide into squares "in a box" and place the figures only in empty squares. This will naturally create a pattern that will be more noticeable the more shapes there are. You can experiment with the shape of the cell. For example, make a triangular layout.

Answer 4

Uh, in general... I don't know how to do it right.
Maybe you’ll laugh at everything))) But I just accidentally came up with an idea, and most likely, with my null knowledge of algebra / geometry and taking into account the hemorrhoids of the task, I would do this:
- presented the canvas as an array of points like:
$point[ 1]['x'] = 0;
$point[1]['y'] = 0;
...etc.
- when generating a figure, the points "occupied" by it were also represented as a similar array
- and before drawing, for example, we check in_array and if all points are free - we draw a figure, while marking elements in the array of canvas points, with indices from the array of the figure being drawn, and as values, you can use the figure identifier, which would be both a sign of the point being busy and information what kind of figure is she occupied with...
Like this) But something seems to me that the solution is much more complicated and less resource-intensive...

Answer 5

Before drawing, you determine the belonging of each vertex to already drawn figures.

Answer 6

In short:
1. sketch out the shapes on the grid. Let them overlap somewhere, somewhere go beyond the border of the canvas.
2. let them "relax" - as if they are ice floes, floating freely. And at the same time they repel each other. To simplify, we can consider that each point is repelled from all points of other figures, the force is proportional to the square of the distance. Calculate a few "steps" of such a voyage.
To determine whether the polygons intersected, as Hasan Istamkulov already wrote , it is necessary to check the intersection of the segments. If two figures find that some two segments intersect, then there is a collision: