Всем доброго времени суток!
Есть у меня координаты точек (N штук, порядка 10000). Если соединить эти точки, получается ломанная. Необходимо соединить две любых точки, чтобы получилась фигура, с максимальной площадью. Помимо этого, нельзя чтобы линия между двумя точками пересекала ломанную.
Получется примерно вот такая картинка:


Есть идея перебирать напрямую пары точек (1,3), (1,4), ..., (1,N); (2,4), (2,5), ..., (2,N); и после проверять пересечение линии с кажой из N частей ломанной, но это получиться по меньшей мере не рационально.

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

Это сообщение отредактировал(а) Ground - 20.3.2009, 09:11

Нужно нарисовать фигуру, внутри которой находится ломаная?

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


Серая линия (между точками 3 и 8) создает фигуру с наибольшей площадью. Нам и нужно в алгоритме найти эту линию, т.е. между какими точками её нужно прочертить.

А зеленая линия пересекает одну из частей ломанной, и не подходит под условия задачи => её нужно исключить из перебора.

Всего 49985001 различных способов провести линию.

Это сообщение отредактировал(а) Ground - 20.3.2009, 10:29

Непонятно. Серая линия НЕ создает фигуру с наибольшей площадью. Это только часть фигуры.
Если вместо отрезков 2-3 и 3-4 провести отрезки 2-4 и 3-1, то получившаяся фигура будет больше заштрихованной, что видно без доказательства, из построения. 
Или последовательность соединения точек задается, а потом одним отрезком (в приведенном примере - восьмым по счету), проведенным между любыми двумя точками, нужно получить замкнутый контур максимальной площади, в который не обязательно должны входить все точки?

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

Нет, вы не поняли. У нас есть ломанная из N точек (на рисунке 8). Нам нужно соединить линией две любые точки, чтобы эта линия не пересекала ломанную, и образовывала фигуру. После нужно найти площадь этой фигуры, но это уже к основному алгоритму не относится.

По рисунку можно провести линии:
Для точки 1:
1 в 3; 1 в 4; 1 в 5; 1 в 6; 1 в 7 и 1 в 8 (далее буду писать (первая_точка, вторая_точка)). Но линии, образуемые из пар точек (1,4), (1,5), (1,6), (1,7) и (1,8) пересекаются с ломанной, и нам не подходят.

Заносим данные в массив: 1 3 S1, где S1 - площадь фигуры.

Для точки 2:
(2,4), (2,5), (2,6) - образуют фигуры. (2,7), (2,8) пересекают, и нам не подходят.

Данные по этим точками можно было бы занести в массив в виде: 2 4 S2; 2 5 S3; 2 6 S4, где Sn - площади фигур.

И так далее для всех точек. После анализа всех точек, делаем сортировку, и смотрим наибольшее значение площади и соответствующую пару точек.

И все бы было замечательно, если бы не количество точек - 10000. В этом случае алгоритм становиться не выгоден. А ничего лучше я придумать не могу...


Это сообщение отредактировал(а) Ground - 20.3.2009, 11:28

Похоже, W4FhLF прав: для построения ломаной точки соединяются в определенной последовательности.
Ground,  уточни по поводу координат точек. Судя по примеру из 8 точек, каждая  последующая точка отличается от предыдущей тем, что у нее больше координата по горизонтали (обычно это ось Х). Ты привел такой пример случайно или в твоем реальном наборе координат такая же зависимость?
(Пока не знаю, чем это поможет в решении твоей проблемы, но чем черт не шутит, может, это будет отправной точкой решения... ) 

Координаты по X в такой зависимости: x1<x2<x3< ... <xn. Вообщем расположены по возрастанию. Положительные.
Координаты по Y - никакой зависимости, положительные.

Просто набор точек слева направо, с увеличивающейся координатой по X, и случайной координатой по Y. Соединяются слева направо. 

Пример приведенный мной на рисунке - случаен, я пишу программу для общего случая.

Ну вообще-то, перебор. Можно только попытаться сокращать варианты.

-- От каждой точки X достаточно перебирать "отрезки", ведущие в точку X+2 и далее.
-- для стартовой точки X и набора {X+2.. X+у} имеет смысл вести отрезок только к точкам, с "экстремальными" значениями Y. (вообще говоря - спорное утвержение..., интуитивно кажется, что правильное  ). То есть, для точки X+у+1, если ее Y координата не "экстремальнее" точек {X+2.. X+у}, то отрезок пересечется...

Остальное - считать, сравнивать...

Эх, ну ясно, будем перебирать.

А реально оценить время работы такой программы? 
Если перебором решать, то получается два вложенных цикла от 1 до 10к (с некоторыми корректировками, в итоге примерно 50млн различных варантов) + внутри рекурсия до 9995 вызовов. Это пока самый неоптимизированный вариант. Время выполнения у меня жестко лимитированно - 3 секунды. У меня закрадываются сомнения, что за такое время алгоритм не отработает 

У меня такая мысль. 

Взглянем сюда:



Чем характерны отрезки 2-4; 2-5; 2-6? Тем что между этими точками координата "y" начала и конца отдельно взятого отрезка (т.е. точек 2 и 4, 5, 6) макисмальны. Т.е. для отрезка 2-4 координаты "y" концов больше, чем координата "y" точки №3, для отрезка 2-5 координата "y" точек 2 и 5 больше, чем координата "y" точек 3 и 4. И т.д.

Добавлено через 2 минуты и 22 секунды


Здесь значения "y" точек 1 и 3 меньше, чем "y" точки 2. 

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

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

Только под ломаной.
Для упрощения понимании задачи вводятся вот такие аналогии: Есть береговая линия (ломаная) и бульдозер, которому необходимо отсечь максимальную часть от берега. Если он пересечет ломаную, то соответственно утонет.


Пока сложно сказать, где эту программу можно применить)

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

Я немного не понимаю вас. Вот смотрите:

У нас 9 точек. Мы в данном случае проверяем 1 и 9 точки. Их ординаты 2 и 3 соответственно. Я понимаю ваш алгоритм так: если ординаты всех промежуточных точек меньше 2, то кривая обязательно пересечет линию. Аналогично, если ордината всех промежуточных точек больше 3, то кривая абсолютно точно не пересечет линию. Тут все верно, но у нас остаются неописанные алгоритмом области - справа внизу под красной линией, и слева вверху. Если точка попадает в эти треугольнички, алгоритм не будет знать как поступить.

Это сообщение отредактировал(а) Ground - 21.3.2009, 08:28

Не понял. Можете показать на графике?

Добавлено через 9 минут и 54 секунды


Если ордината хотя бы одной точки <= 2, то отрезок пересечёт кривую.

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


Вот тут точка 3 как раз попадает в эту область.

Но эт не работает.   Ибо если ордината 7ой точки будет 2.5, то отрезок всё равно пересечёт кривую.

Добавлено через 1 минуту и 56 секунд
Да, я уже понял. Хм. 

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

Добавлено через 3 минуты и 55 секунд
Причём надо вычислять только для синей/жёлтой областей. Т.е. сначала проверка в какую область попадает точка, если в синюю/жёлтую, то вычислять ординату отрезка в этой точке и сравнивать с ординатой текущей промежуточной точке. 

Тогда получается нужно брать коориднаты точек, через которые провели линию, получать из них коэффициенты A, B и C для уравнения прямой Ах+Ву+С=0. И потом подставлять абциссу в уравнение y=-(Ax+C)/B. После сравнивать 2 ординаты. И еще надо делать проверку на деление на 0.
Ну такой алгоритм намного проще, чем находить пересечение линий 
Но все равно, при 10к точек получается 50млн различных вариантов проведения линии. С таким колчиеством не уложиться даже в минуту работы программы.
Должно быть что-то еще, какой то неучтенный момент, который заметно упростит программу.

Хотя сначала лучше напишу, проверю скорость выполнения.

Неверно. Уравнение прямой проведённой через две точки выглядит следующим образом: 





Я же говорю, что тебе нужно проверять сначала в какую область попадает точка. Этим ты снизишь количество необходимых уравнений для решения. 

W4FhLF, Вид уравнения не совсем удобен для такой задачи
Вот в таком виде y=A*x+B для всех таких прямых, проходящих через  точку (x1,y1) угол наклона такой прямой будет монотонной функцией от A. Так что экстремальные значения углов будут приходится на экстремальные значения А, тригонометрия становится не нужна.

ksnk, да вообще он приводится к виду:

y = (x - x1) * (y2 - y1) / (x2 - x1) + y1

Dыражение (y2 - y1) / (x2 - x1) находится один раз и получается в итоге(обозначив это выражение как a):

y = (x - x1) * a + y1

Раскрываем скобки:

x*a - x1*a + y1

Обозначаем -x1*a + y1 как b и получаем:

y = x*a + b

Ничего не напоминает? 


Это сообщение отредактировал(а) W4FhLF - 21.3.2009, 17:04

Всем спасибо за помощь!
Алгоритм, предложенный W4FhLF очень хорошо себя показал.

Это сообщение отредактировал(а) Ground - 22.3.2009, 13:31