Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
Заранее спасибо!

Здравствуйте, LeeLoo, Вы писали:

LL>Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
LL>и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
LL>Заранее спасибо!

Звёздчатый, это который углами?

У меня есть полуфабрикат на C#. Генерирует всё исправно. Как оформлю, чтобы понятно было — оставлю. Сегодня днём, как просплюсь...

Здравствуйте, LeeLoo, Вы писали:

LL>Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
LL>и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
LL>Заранее спасибо!

Здесь проект и небольшая иллюстрация.
http://chandrush.narod.ru/StarPolygons.zip

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, LeeLoo, Вы писали:

LL>>Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
LL>>и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
LL>>Заранее спасибо!

А>Здесь проект и небольшая иллюстрация.
А>http://chandrush.narod.ru/StarPolygons.zip
так интересно..а я вот подумала, что есть вообще, звездчатый полигон??
я думала, это ткой многоугольник, в котором есть т.н. ядро(точко или комбтинация таковых), из которого видны все точки этого многоугольника, т.е. можно провести прямые до любой точки многоугольника.
и моя задача заключалась в том, чтобы из обычного многоугольника, поступающего на вход, сделать звездчатый
а вот увидела вашу картинку и запуталась окончательно..вы не могли бы объяснить, что делает ваша программа?
очень интересно

Здравствуйте, LeeLoo, Вы писали:

LL>Здравствуйте, Аноним, Вы писали:

А>>Здравствуйте, LeeLoo, Вы писали:

LL>>>Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
LL>>>и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
LL>>>Заранее спасибо!

А>>Здесь проект и небольшая иллюстрация.
А>>http://chandrush.narod.ru/StarPolygons.zip
LL>так интересно..а я вот подумала, что есть вообще, звездчатый полигон??
LL>я думала, это ткой многоугольник, в котором есть т.н. ядро(точко или комбтинация таковых), из которого видны все точки этого многоугольника, т.е. можно провести прямые до любой точки многоугольника.
LL>и моя задача заключалась в том, чтобы из обычного многоугольника, поступающего на вход, сделать звездчатый
LL>а вот увидела вашу картинку и запуталась окончательно..вы не могли бы объяснить, что делает ваша программа?
LL>очень интересно

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

Здравствуйте, LeeLoo, Вы писали:

LL>Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
Что дано? Какие ограничения?
LL>и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
Наверняка здесь что-то есть

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, LeeLoo, Вы писали:

LL>>Ребята, не доскажите, где можно найти алгоритм построения звездчатого полигона??
FM>Что дано? Какие ограничения?
есть комбинация точек, из них надо сделать звездчатый полигон

LL>>и вообще поподробнее почитать о нем. Есть книга Шикина и Борискова, но не все в ней понятко(
FM>Наверняка здесь что-то есть
где здесь?

Здравствуйте, LeeLoo, Вы писали:

LL>есть комбинация точек, из них надо сделать звездчатый полигон

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

Не уверен, что полигон получится красивым , но он точно будет звездчатым (относительно центра масс исходных точек)

Здравствуйте, Аноним, Вы писали:

LL>>есть комбинация точек, из них надо сделать звездчатый полигон

А>Ну тогда все совсем просто
А>Ищем центр масс точек, упорядочиваем эти точки по возрастанию полярного угла относительно их центра масс
А>(если углы совпадают — по убыванию радиусов), и затем соединяем их отрезками в порядке получившейся последовательности

Зачем центр масс? Можно взять любую точку плоскости (вообще любую, даже за пределами выпуклой оболочки).
Конечно, если внутри выпуклой оболочки, то получится красивее...

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

Можно найти выпуклую оболочку и затем найти её центр масс — либо сплошной фигуры, либо периметра.
Но это уже O(n log n).

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Аноним, Вы писали:

LL>>>есть комбинация точек, из них надо сделать звездчатый полигон

А>>Ну тогда все совсем просто
А>>Ищем центр масс точек, упорядочиваем эти точки по возрастанию полярного угла относительно их центра масс
А>>(если углы совпадают — по убыванию радиусов), и затем соединяем их отрезками в порядке получившейся последовательности

К>Зачем центр масс? Можно взять любую точку плоскости (вообще любую, даже за пределами выпуклой оболочки).
К>Конечно, если внутри выпуклой оболочки, то получится красивее...

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

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

К>Можно найти выпуклую оболочку и затем найти её центр масс — либо сплошной фигуры, либо периметра.
К>Но это уже O(n log n).

Можно, можно найти. Можно еще много чего найти, если делать нечего
Но для решения данной задачи этого не требуется

Ребят, а может все-таки есть кусочек кода??
ну, совсем маленький))
желательно по этой задаче)))

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, LeeLoo, Вы писали:

LL>>есть комбинация точек, из них надо сделать звездчатый полигон

А>Ну тогда все совсем просто
А>Ищем центр масс точек, упорядочиваем эти точки по возрастанию полярного угла относительно их центра масс
А>(если углы совпадают — по убыванию радиусов), и затем соединяем их отрезками в порядке получившейся последовательности

а как реализовывается сортировка по полярным координатам??

А>Не уверен, что полигон получится красивым , но он точно будет звездчатым (относительно центра масс исходных точек)

Здравствуйте, LeeLoo, Вы писали:

LL>а как реализовывается сортировка по полярным координатам??

Не совсем понял вопрос

Есть точка (X,Y)
Считаем ее координаты относительно центра масс (X-Xcenter,Y-Ycenter)
Далее, у этого вектора находим радиус и полярный угол (оптимизацию сейчас не рассматриваем)

Потом производим сортировку
Смотрим, если у первой точки полярный угол больше, чем у второй, то считаем, что первая точка больше второй
Если полярные углы равны, сравниваем радиусы

Алгоритмов сортировки навалом, в интернете есть множество реализаций, бери любую
Только измени процедуру сравнения под свои нужды
В чем проблема-то?

PS Код писать я за тебя не буду, можешь не надеяться

А>PS Код писать я за тебя не буду, можешь не надеяться
Спасибо!
И правильно!!
Я уже написала!!
так что обращайтесь, если кому-нибудь надо!!