Нужна помощь с алгоритмом

[Aber]

Здравствуйте!
Необходимо придумать алгоритм соединения множества точек линиями, да так чтобы они не пересекались. Из одной точки может быть несколько линий но не менее 2.

Может кто-то сталкивался с подобной задачей.

Алгоритм проверки на пересечение 2 линий я придумал. Но вот как связать это всё вместе не знаю.

Буду рад любой идее!

[Партизан]

Идея номер раз: Карандашом отметить точки, провести нужное количество линий между точками с помощью линейки используя ваш алгоритм исключения вероятности пересечений.

Идея номер два: После прочтения данного поста вы описываете свою задачу с приведением как можно большего числа строк строго относящегося к решению задачи кода, условий реализации и вообще всего, что поможет рассеять туманность вашего первого поста, чтобы не возвращать вас к идее номер раз. Если вы конечно действительно рассчитываете на помощь.

[Dukobpa3]

"Задача коммивояжера"... Не?

1. Генетический алгоритм
2. Нейронная сеть (кстати нейронной сетью я такой вопрос решал помнится будучи студентом 6 лет назад)
3. ваш вариант.

[Aber]

Ну хорошо, я понял ошибки своего первого поста.

Подробнее:

Я начал писать игру "Паучки." Суть такова: Есть n-ое количество объектов(В нашем случае поучков), они соеденены между собой линиями(Паутинами) и запутаны.
Цель игры: Необходимо распутать всех паучков так, чтобы не одна линия не пересекалась, перемещая их мышью.
Обекты я создаю

for (var i = 0; i < 9; i++) {
	parray[i] = new paukk();
	parray[i].x=stage.stageWidth*Math.random();
	parray[i].y=stage.stageHeight*Math.random();
	addChild(parray[i]);
}

В классе объекта уже прописаны действия на щелчок мыши. Т.е. После создания я уже могу их перемещать.
Паутина, это простая линия нарисованная от начального объекта, до конечного.

На данный момент я создал в Классе объекта две переменных(oneline и twoline), в которые заносятся номера объектов, с которыми он соединяется.

И код прорисовки линий такой:

function enterFrameHandler(e:Event):void {
	graphics.clear();
	for (var k = 0; k < parray.length; k++) {
		one=parray[k].oneline;
		two=parray[k].twoline;
		graphics.lineStyle(5, 0);
		graphics.moveTo(parray[k].x, parray[k].y);
		graphics.lineTo(parray[one].x, parray[one].y);
		graphics.moveTo(parray[k].x, parray[k].y);
		graphics.lineTo(parray[two].x, parray[two].y);
	}
}

Переменные oneline и twoline я заполняю рандомно.

function LiniiRandom() {			
	for (var i = 0; i<parray.length; i++)  
	{
		do 
		{
			one = Math.round(Math.random()*(parray.length -1));
			two = Math.round(Math.random()*(parray.length -1));
		}
		while((one == two) || (parray[one].oneline == i) || (parray[two].twoline == i) || (parray[two].oneline == i) || (parray[one].twoline == i));
		parray[i].oneline = one;
		parray[i].twoline = two;
	}
 
}

Но в итоге получается расклад который невозможно распутать.

И мне нужны идеи как реализовать запутывание, с возможностью распутывания.

Вот Ссылка на моё приложение, которое есть сейчас: http://uwww.narod.ru/pauk.html

[Dukobpa3]

Я же ответил))) И это не стёб был - генетический алгоритм.

К тому же можно не парить себе моск а добавить пользователю возможность "разрывать" какое-то количество паутинок.

К тому же гораздо проще будет если у каждого паука будет строго ограниченное кол-во линий от и до. А у меня к примеру получилось что все по 2-3 паутинки, а у одного паука штук семь. собственно из-за него одного и не смог распутать.

А еще проще будет если количество паутинок будет у всех одинаковое. Скажем 3.

А еще было бы неплохо предварительно рисовать в памяти граф с правильно соединенными пауками, а потом рандомно менять им х.у

т.е. если у вас уже есть алгоритм проверки на пересечение то всё что надо - это запускать его не потом когда пользователь уже работает, а до того. И перед рисованием каждой линии проверять по этому алгоритму, если пересечения есть, значит отставить...

После этого взять и рандомно смешать координаты.

Добавлено через 2 минуты
т.е. грубо говоря у вас одна глобальная ошибка...

Вам не линии надо рисовать рандомно.

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

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

[Aber]

Dukobpa3
Твой пост я оценил, Спасибо. Я просто увидел его когда написал второй.

И сейчас всё-же решил изначально расставить линии так чтобы они не пересекались. А затем запутыват.

Посмотрим что получится.

И еще думаю поиграть с количеством линий, четность, нечетность. количество от одного, и так-далее.

Добавлено через 6 минут
Кстати про круг вы хорошо заметили.
Ставим их в круг, соединяем все по кругу, а затем и остальные соединяем, чтоб не пересекались.

[Dukobpa3]

Кстати про круг вы хорошо заметили.

Обращайтесь))

[Aber]

Я Придумал самый простой вариант!!!!
Мы тупа соединяем 1 с 2и3, 2 с 3и4, и так далее. последний соединяем с первым. В итоге у нас все как минимум по 2 соединения, И можно распутать.

Пока сделаю так, в дальнейшем буду менять.

[Dukobpa3]

Ну только если вы учли что такая схема не сработает с непарным кол-вом пауков

[Aber]

Спасибо, я чтот даже не подумал.
Значить будет всегда нечетное количество. Никто и не догадается.