Всем доброго времени суток!
Есть у меня координаты точек (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, а фигура может быть и над ломаной, а не только под ломаной (как в приведенном примере)?
И еще. Если не секрет: какое практическое значение этой работы, которую ты выполняешь, зачем нужно выискивать фигуру с максимальной площадью?  

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


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

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