Точки пересечений N линий.

[Hasar1n]

Здравствуйте, господа и дамы. Не знаю, куда лучше поместить тему, ибо она относится и к математике, и к программированию. И к какому разделу она относится больше решать не мне.
Задача такова. Есть два упорядоченных множества точек на плоскости (m1,m2: array[0..n] of TPoint_2d). Нужно найти все пересечения за минимальное количество итераций. Не могу организовать правильно вложенные циклы. Понимаю, что нужно просто не проходить по паре проверенных линий, но как дубликаты убрать? Помогла бы, наверно, комбинаторика.
На бумаге набросал множества из 3, 4, 5 точек. Пересечений вышло 9, 36, 96.
Благодарю за внимание.

[Deggial]

Уточните, пожалуйста, формулировку, вот это:

Hasar1n в сообщении #746532 писал(а):

Есть два упорядоченных множества точек на плоскости (m1,m2: array[0..n] of TPoint_2d). Нужно найти все пересечения за минимальное количество итераций.

Пересечения чего? Отрезков? Каких? Которые проведены между точками массивов? Напишите явно

Куски кода оформляйте тегом code, маленькие куски кода - тегом tt, формулы - $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
Сейчас я код поправил, в дальнейшем, в случае плохого оформления, тема будет перенесена в Карантин.

[Hasar1n]

Цитата:

Куски кода оформляйте тегом code, маленькие куски кода - тегом tt, формулы - $\TeX$ом.

Прошу прощения.

Цитата:

Пересечения чего? Отрезков? Каких? Которые проведены между точками массивов? Напишите явно

Пересечения отрезков между точками 2 множеств.
Нашел более-менее подходящее решение:

for k :=1 to n-1 do
for i :=k to n do
for j :=k to n do
for z :=1 to i-1 do

Правда, избыточность циклов есть. Но хоть как-то.

[iifat]

А в каком смысле "упорядоченных"? Это просто отражение того факта, что точки хранятся в массивах? Или же они там в каком-то смысле упорядочены?
Можно попробовать упорядочить по какой-нить координате и чего-нить из этого поиметь. Это не рецепт и даже на идею не тянет, но: если первый массив разбить на два — первая координата меньше/больше какого-нибудь числа, второй аналогично (с другим, вообще говоря, числом), то отрезки с обоими концами из первых частей массива и из второй уж точно не пересекаются между собой.

[Hasar1n]

Цитата:

А в каком смысле "упорядоченных"? Это просто отражение того факта, что точки хранятся в массивах? Или же они там в каком-то смысле упорядочены?

Точки создаются рандомно. Каждое множество точек имеет, так сказать, свой центр, вокруг которого они формируются(не знаю, как это называется математически). В общем, вот так:

  for i:=0 to n do
  begin
    m1[i].x:=1+random(100)/300;
    m1[i].y:=1+random(100)/300;

    m2[i].x:=1+random(100)/300;
    m2[i].y:=-1-random(100)/300;
  end;

Далее, пробегаемся быстрой сортировкой по координате Х. Таким образом мы и упорядочиваем массивы.

Цитата:

если первый массив разбить на два — первая координата меньше/больше какого-нибудь числа, второй аналогично (с другим, вообще говоря, числом), то отрезки с обоими концами из первых частей массива и из второй уж точно не пересекаются между собой.

Это было понятно, когда начал разбивать на части общую картинку пересечений:

[venco]

Пропустили итерацию $6{1\over2}$.

-- Чт июл 18, 2013 09:41:49 --

А чтобы узнать формулу, лучше записать первую итерацию как $3\cdot1$, вторую - как $3\cdot2$, и т.д.
И после этого будет ясно, что при $n=5$ количество пересечений равно $100$.

[Hasar1n]

Цитата:

Пропустили итерацию $6{1\over2}$.

Не понял.

Цитата:

А чтобы узнать формулу, лучше записать первую итерацию как $3\cdot1$, вторую - как $3\cdot2$, и т.д.
И после этого будет ясно, что при $n=5$ количество пересечений равно $100$.

Да, вы правы. Пересмотрел свой рисунок при n = 5. Пересечений действительно 100, а не 96. Но..
Все равно не понял формулы. Что такое $3\cdot1$ и $3\cdot2$?

[venco]

Hasar1n в сообщении #747197 писал(а):

Цитата:

Пропустили итерацию $6{1\over2}$.

Не понял.

Между 6 и 7 на вашем рисунке должна быть ещё одна.

Hasar1n в сообщении #747197 писал(а):

Все равно не понял формулы. Что такое $3\cdot1$ и $3\cdot2$?

В первой итерации зелёные отрезки соединяют каждую из трёх верхних точек с каждой из одной нижней , во второй итерации - ...

[Hasar1n]

Цитата:

Между 6 и 7 на вашем рисунке должна быть ещё одна.

Самое ужасное, что я это понял. Но я не понял, какой должна быть эта итерация. В математике я проффи. Ой, профан я в математике.)

Цитата:

В первой итерации зелёные отрезки соединяют каждую из трёх верхних точек с каждой из одной нижней , во второй итерации - ...

Так, то есть такой должна быть первая итерация по вашему алгоритму
?

[venco]

Блин. Ну как(!) можно так понять мои слова:

venco в сообщении #747218 писал(а):

В первой итерации зелёные отрезки соединяют каждую из трёх верхних точек с каждой из одной нижней , во второй итерации - ...

На всякий случай: я полностью сохранил ваше понятие об итерации.

[Hasar1n]

Мне сложно понять некоторые вещи словами. Нужно увидеть.
Не подскажете, какая последовательность итераций правильная? Если я правильно понял ваши слова.

[venco]

Никакая. Я имел в виду то, что было на вашем первом рисунке.
Мне, правда, уже надоело, так что дальше думайте сами.

[Hasar1n]

Наконец-то я выспался, и с новыми силами в бой. Я понял, что Вы имели в виду:
$3\cdot1$ + $3\cdot2$ + $3\cdot3$ + $2\cdot1$ + $2\cdot2$ + $2\cdot3$ + $1\cdot1$ + $1\cdot2$ + $1\cdot3$.
Вот и получается, что их 36. По аналогии и с n=5 получаем 100.
Формула для n=4 получается такая : $ \sum\limits_{i=1}^{n-1}$$(n-i)\cdot 1 + (n-i)\cdot 2 + (n-i)\cdot 3$
До этого я все-таки допер не без ваших стараний. Благодарю за помощь. Но как графически представить итерацию $6{1\over2}$ я до сих пор не могу допереть.

[Hasar1n]

Для произвольной n формула приняла бы такой вид:
$\sum\limits_{j=1}^{n-1} \sum\limits_{i=1}^{n-1}$ $(n-i)\cdot j$
В программировании получилось бы так:

for i:=1 to n-1 do
for j:=1 to n-1 do
sum:=sum+(n-i)*j

Но вот в чем загвоздка. Я пытаюсь найти координаты пересечения всех этих точек. У меня в функцию передаются 5 параметров: 4 точки

(m1[i]{начало 1-ой линии},m2[j]{конец 1-ой линии},m1[k]{начало 2-ой линии},m2[z]{конец 2-ой линии})

и указатель на тип, в который будут занесены координаты пересечения, если оно есть. Поэтому-то я и прошу помощи для нахождения итерации 6.5.
Deggial, на самом деле это был обезьяний труд, ибо кто смог помочь, помогли. У меня предчувствие, что больше не будет ответов. Просто не знают, как, или не понимают чего я хочу, т.к. выражать свои мысли корректно я не умею.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: неправильно оформлены формулы

Hasar1n, наберите, формулу с картинки $\TeX$ом, а картинку уберите. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул