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

Есть много подобных фигур.
1e85c574113d4753ad778e58a5079072.jpg
Я хочу рисовать их в случайном порядке. Но нужно чтобы они не пересекались.
Как это можно реализовать?
Фигуры в формате svg path, рисую на canvas.
  • Вопрос задан
  • 3947 просмотров
Решения вопроса 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));
}

Но он не понадобился, так как у меня фигуры состоят из большого количества полигонов.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 5
Astrohas
@Astrohas
Python/Django Developer
Если в вкратце - то вам нужно хранить в какой то структуре все отрезки (стороны) каждого многоугольника в виде пар (x1, y1 , x2, y2), а также координаты краев. Затем При добавлении вам нужно сравнивать многоугольник которого хотите добавить со всеми многоугольниками. Суть сравнения в проверки пересечения отрезков. Т.Е. сравниваем отрезки друг с другом. Общее время для сравнение двух многоугольников N^M, где N и M - количество отрезков многоугольников. Для того чтобы не тратить ресурсов для сравнения многоугольников которые не могут быть пересекать друг друга, сначала сравнивайте координаты краев.
UPD:
Как отметил Сергей Соколов нужно проверят возможность вхождения одной фигуры в другую. Для этого вдобавок нужно например проверять вхождение точки одного многоугольника в другую. Тоже NM операций.
Ответ написан
@Interface
Как вариант, можно разбить плоскость на множество гарантированно непересекающихся полигонов. И при добавлении полигона располагать его в незанятой ячейке. Это не решит задачу в общем случае. Но для частного случая может оказаться простым приемлемым решением. Например, можно разбить на квадраты "в клеточку" и распологать фигуры только в пустых квадратах. Это естественно создаст паттерн, который будет тем более заметен, чем больше будет фигур. Можно поэксперементировать с формой клетки. Напрмер, сделать треугольную разбивку.
Ответ написан
Exploding
@Exploding
wtf?
Эээ, в общем... Как правильно это сделать я не знаю.
Может все и ржать будете))) Но вот случайно придумал идею только что и скорее всего я бы со своими null-евыми знаниями алгебры/геометрии и учетом геморности задачи делал бы так:
- представил канвас в виде массива из точек типа:

$point[1]['x'] = 0;
$point[1]['y'] = 0;
...и т.д.
- при генерации фигуры "занимаемые" ею точки также представлялись в виде аналогичного массива
- и перед отрисовкой проверяем например in_array и если все точки свободны - рисуем фигуру, при этом помечая в массиве точек канваса элементы, с индексами из массива рисуемой фигуры, а в качестве значений можно использовать идентификатор фигуры, что было бы и признаком занятости точки и информацией какой именно фигурой она занята...
Вот такое) Но что-то мне кажется, что решение гораздо сложнее и менее ресурсозатратно...
Ответ написан
Комментировать
@evgeniy_lm
Перед отрисовкой определяете принадлежность каждой вершины уже отрисованным фигурам.
Ответ написан
sergiks
@sergiks Куратор тега JavaScript
♬♬
Вкратце:
1. набросать фигуры по сетке. Пусть они где-то накладываются, где-то выходят за границу полотна.
2. дать им «расслабиться» – будто они льдины, свободно плавающие. И при этом взаимно-отталкиваются. Для упрощения можно посчитать, что каждая точка отталкивается от всех точек других фигур, сила пропорциональна квадрату расстояния. Просчитать несколько «шагов» такого плавания.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы