Существует ли быстрый алгоритм проверки пересечения линии полигона с собой?

Question

[Ингвар Фон Бьёрк]

Есть полигон, заданный некоторым массивом точек, образующих прямые (около 4000). Надо проверить,пересекаются ли эти линии с самими собой.
Метод перебора массива в массиве занимает очень много времени. Есть ли более быстрый способ?

Comments

[Евгений Шатунов]

Ингвар Фон Бьёрк

Надо проверить,пересекаются ли эти линии с самими собой.

А какую именно задачу решит определение этого свойства у полигона? Иными словами, для чего тебе знать, пересекаются ли ребра полигона или нет?

Answer 1

[Clark Kent]

Ну вообще есть хитрый способ ) Надо создать битмап(канвас) и отрисовать туда все эти линии например с альфой 0.5, И далее пройтись по всем точкам и проверить альфа координату и если она хотя бы в одном пикселе более 0.5 то значит в том месте примерно имеется пересечение. Естественно есть много тонкостей и настроек такого способа. И не факт что будет быстрей )

Потом при переборе массива с массивом может возникнуть ситуация двойной проверки. Например 100х200 и 200х100. Можно как минимум в пару раз сократить время расчетов:

for(var i = 0; i < 4000; i++)
{
    for(var j = i + 1; j < 4000; j++ )
    {
          // check i vs j
    }
}

Comments

[Ингвар Фон Бьёрк]

Да, я использую такой же цикл, как Вы предложили. Идея с канвасами вряд-ли окажется быстрой.
Как писали ниже можно исключить ещё и смежные отрезки, т.е. j = i + 2.

[Clark Kent]

Еще есть способ. Локализация отрезков. Виртуально разбиваем все поле на квадраты. Бежим по всем отрезкам полигона и вычисляем их bounds box. Смотрим в какие квадраты попал тот или иной отрезок и записываем отрезок в ячейку. И так по всем отрезкам. Далее бежим уже по всем использованным виртуальным клеткам. И если там более двух отрезков - проверяем их пересечение. Реальных проверок должно получится намного меньше.

И потом еще сам метод проверки:

function cross(p0x, p0y, p1x, p1y,
	      p2x, p2y, p3x, p3y)
	{
		const d = ((p3y - p2y) * (p1x - p0x)) - ((p3x - p2x) * (p1y - p0y));
		
		if (d === 0)
		{
			return null;
		}
		
		const d02x = p0x - p2x;
		const d02y = p0y - p2y;
		
		let n1 = ((p3x - p2x) * d02y) - ((p3y - p2y) * d02x);
		let n2 = ((p1x - p0x) * d02y) - ((p1y - p0y) * d02x);
		
		const v01 = n1 / d;
		const v23 = n2 / d;
		
		if (v01 < 0 || v01 > 1)
		{
			return null;
		}
		
		if (v23 < 0 || v23 > 1)
		{
			return null;
		}
		
		const x = p0x + (v01 * (p1x - p0x));
		const y = p0y + (v01 * (p1y - p0y));
		
		return {x, y};
	}

Answer 2

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

Известны ли какие-то особенности полигона, или каждая следующая вершина может оказаться где угодно?

В общем случае полигон ничем не отличается от набора независимых отрезков, где придётся проверить каждый-с-каждым, кроме смежных соседей. Можно оптимизировать: бить на подгруппы, сортировать и пр.

Comments

[Ингвар Фон Бьёрк]

Про исключение смежных не подумал, спасибо за наводку.