@Nataly93

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

0

@eropegov

Выпуклый многоугольник или не обязательно?

0

@Nataly93

Да, чтобы захватывались все максимально удаленные точки

0

@eropegov

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

0

@Nataly93

Заранее извиняюсь, что непонятно может излагаю свой вопрос. Вот на рисунке я изобразила под номерами точки и как математически рассчитать, что именно точки 6, 8-11 являются искомыми, а не лежащие внутри импровизированного многоугольника. А так же, как перестроить границу, если исчезнет например 8.

Миниатюры

 

0

@eropegov

Ага, всё-таки, видимо, речь идёт о построении выпуклой оболочки конечного множества точек. Я думаю, что уже простой поисковый запрос "выпуклая оболочка набора точек" принесёт вам немало полезного. А как перестраивать эту выпуклую оболочку при появлении новых точек или исчезновения имеющихся - тоже хорошая задачка. Опять же: можно перебором, но есть чувство, что можно и изящнее. Как именно - навскидку, конечно, не скажешь.

0

@Nataly93

Спасибо за Ваши ответы!) Да, поищу еще!

0

@TheCalligrapher

Ничего не понял.

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

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

К чему тут тогда требование "наибольшего периметра"? Откуда оно вообще взялось, что аж вынесено в заголовок (!)? Либо убирайте требование наибольшего периметра, либо убирайте требование выпуклости. Вместе эти требования - бессмысленны.

Добавлено через 3 минуты
Так а "наибольший периметр"-то тут при чем?

0

@eropegov

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

0

@TheCalligrapher

В исходной - действительно не было.

Нет.

Именно это условие, очевидно, пытается донести до нас ТС через свои туманные "чтобы захватывались все максимально удаленные точки", "вот на рисунке я изобразила под номерами точки" и "именно точки 6, 8-11 являются искомыми, а не лежащие внутри импровизированного многоугольника".

Получается плохо, но, я думаю, мы все уже догадались ("придумали"), о чем идет речь

0

@eropegov

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

Как-то я косноязычно написал, но, надеюсь, понятно.

0

@Nataly93

Я честно говоря в этом не очень сильна.
Смысл в том что на производстве произошла утечка опасного вещества, по периметру производства расставлены датчики,откалиброван не на данное вещество. Утечка в конечном счёте представляет собой облако, которое расширяется и движется в сторону направления ветра. Соответственно в процессе его распространения срабатывают датчики, либо если облако от прежде сработавших улетело дальше, чем зона их чувствительности, данный датчик перестал сигнализировать. Так вот для визуализации примерного размера этого облака нам нужно очертить его размеры по сработавшим датчикам, поэтому необходимы точки, очерчивающие многоугольник с наибольшей площадью покрытия.
И каждые 10с надо опрсшивать систему не появились ли новые и не исчезли ли старые датчики, которые являлись границей этого многоугольника.
Вот на пальцах как-то так...

0

@mathmichel

До сих пор Вы говорили о наибольшем периметре, а не площади! У Вас какое образование? (если для Вас все равно, что периметр, что площадь!)

0

@Nataly93

Ладно, спасибо вам, что указали на ошибки, на плохое образование и кто-то дал ссылки в какую сторону искать ответ.

0

@kabenyuk

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

0

@Excalibur921

Датчики имеют некий радиус срабатывания. Могут быть пустоты в облаке.
Тогда сработавшие датчики это точки с зарядом, визуализация изоуровня алгоритмом шагающие квадраты.
https://ru.wikipedia.org/wiki/Marching_squares
http://www.cs.carleton.edu/cs_... cubes.html

0

@Symon

Предлагаемая программа при каждом нажатии Ctrl+F9 рандомно выдает множество точек (до 20. можно настроить на любое максимальное число) и строит выпуклую оболчку этого множества.

1