Как вычислить пересекаются ли много многоугольников?

Question

[TANK_IST]

Есть много подобных фигур.

Я хочу рисовать их в случайном порядке. Но нужно чтобы они не пересекались.
Как это можно реализовать?
Фигуры в формате svg path, рисую на canvas.

Comments

[Сергей Соколов]

Что у фигур зафиксировано? Форма, размер, ориентация – можно что-то из этого менять? Например, наехала новая фигура на соседнюю, а мы её уменьшаем пропорционально (?) до тех пор пока она не перестанет накладываться с соседней. Или просто повернуть её по часовой стрелке и она впишется без коллизий.

Может, формы не фиксированы, и можно их генерить налету?

Answer 1

[TANK_IST]

Всем спасибо за ответы!
Мне помогла статья Базовая теория столкновения объектов, спрайтов на .... Там же есть код для определения принадлежности точки полигону.

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;
}

Также нашел код для определения пересечений полигонов.

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));
}

Но он не понадобился, так как у меня фигуры состоят из большого количества полигонов.

Answer 2

[Astrohas]

Если в вкратце - то вам нужно хранить в какой то структуре все отрезки (стороны) каждого многоугольника в виде пар (x1, y1 , x2, y2), а также координаты краев. Затем При добавлении вам нужно сравнивать многоугольник которого хотите добавить со всеми многоугольниками. Суть сравнения в проверки пересечения отрезков. Т.Е. сравниваем отрезки друг с другом. Общее время для сравнение двух многоугольников N^M, где N и M - количество отрезков многоугольников. Для того чтобы не тратить ресурсов для сравнения многоугольников которые не могут быть пересекать друг друга, сначала сравнивайте координаты краев.
UPD:
Как отметил Сергей Соколов нужно проверят возможность вхождения одной фигуры в другую. Для этого вдобавок нужно например проверять вхождение точки одного многоугольника в другую. Тоже NM операций.

Comments

[Сергей Соколов]

Может быть случай полного поглощения одного полигона другим, без пересечений:

[Сергей Соколов]

..и вариант окружения без поглощения

[Astrohas]

Сергей Соколов: Хм вы правы, этого я не учел

[Сергей Соколов]

Наверное, надо триангулировать сложные фигуры (бить в сетку из треугольников), и проверять ещё и «внутренние» грани.

[Сергей Соколов]

Нет, триангуляция не панацея:

Надо проверять вхождение точек.

Answer 3

[Interface]

Как вариант, можно разбить плоскость на множество гарантированно непересекающихся полигонов. И при добавлении полигона располагать его в незанятой ячейке. Это не решит задачу в общем случае. Но для частного случая может оказаться простым приемлемым решением. Например, можно разбить на квадраты "в клеточку" и распологать фигуры только в пустых квадратах. Это естественно создаст паттерн, который будет тем более заметен, чем больше будет фигур. Можно поэксперементировать с формой клетки. Напрмер, сделать треугольную разбивку.

Comments

[Сергей Соколов]

тоже была мысль как-то задействовать диаграмму Вороного.

Вариант – накидать случайных точек, построить по ним диаграмму, в «островки» вписывать фигуры.

Answer 4

[Exploding]

Эээ, в общем... Как правильно это сделать я не знаю.
Может все и ржать будете))) Но вот случайно придумал идею только что и скорее всего я бы со своими null-евыми знаниями алгебры/геометрии и учетом геморности задачи делал бы так:
- представил канвас в виде массива из точек типа:

$point[1]['x'] = 0;
$point[1]['y'] = 0;
...и т.д.
- при генерации фигуры "занимаемые" ею точки также представлялись в виде аналогичного массива
- и перед отрисовкой проверяем например in_array и если все точки свободны - рисуем фигуру, при этом помечая в массиве точек канваса элементы, с индексами из массива рисуемой фигуры, а в качестве значений можно использовать идентификатор фигуры, что было бы и признаком занятости точки и информацией какой именно фигурой она занята...
Вот такое) Но что-то мне кажется, что решение гораздо сложнее и менее ресурсозатратно...

Answer 5

[evgeniy_lm]

Перед отрисовкой определяете принадлежность каждой вершины уже отрисованным фигурам.

Comments

[Иван]

вершины могут и не совпадать , а пересечение ребер то будет.

[evgeniy_lm]

А с какой сырости вершины должны совпадать? я разве писал о совпадении?
Я писал о том находится вершина внутри замкнутой области или нет. Проверить это можно гораздо быстрее чем пересечение ребер. Ко всему прочему во всех уважающих себя ЯП такая функция уже реализована

[Иван]

evgeniy_lm: да извиняюсь неверно прочел

[evgeniy_lm]

Сейчас в голову пришла мысль, что мой ответ верный только в случае выпуклых многоугольников. Если многоугольник может быть не выпуклым, то часто будут ситуации когда фигуры пересекаются но вершины нет. Т.е. все таки нужно рассчитывать пересечение ребер

Answer 6

[Сергей Соколов]

Вкратце:
1. набросать фигуры по сетке. Пусть они где-то накладываются, где-то выходят за границу полотна.
2. дать им «расслабиться» – будто они льдины, свободно плавающие. И при этом взаимно-отталкиваются. Для упрощения можно посчитать, что каждая точка отталкивается от всех точек других фигур, сила пропорциональна квадрату расстояния. Просчитать несколько «шагов» такого плавания.

Для определения, пересеклись ли полигоны, как уже написал Хасан Истамкулов, надо проверять пересечение отрезков. Если у двух фигур найдётся, что какие-то два отрезка пересеклись, значит есть коллизия: