Алгоритм нахождения вершин многоугольника

26.02.2009, 09:48. **Показов** 3745. **Ответов** 4

Студворк — интернет-сервис помощи студентам

Как построить многоугольник с максимальной точностью, если известно:
1.Количество вершин многоугольника
2.Первые две вершины имеют координаты: A(0;0) B(0;длина стороны многоугольника)
3.Многоугольник разбит на треугольники(диагоналями), при этом одна точка может иметь несколько диагоналей
Я представляю себе это так:
1. Находим точку у которой есть диагонали уже с известными точками(на первом шаге это A и B)
2. По формуле пересечения двух окружностей находим одну или две точки пересечения и Вот тут то ВОПРОС: как выбрать верную точку?

Проблема в том что нужно написать алгоритм который сам определит правильное расположение точек в случае если этих вариантов несколько…

Пример на рисунке…
http://pic.ipicture.ru/uploads... BLBstw.jpg

@ostgals · 26.02.2009, 20:35

Не совсем понятно...

1. На входе есть количество вершин и еще что? Если диагонали, то каким способом они описываются?
2. Что надо получить на выходе?

27.02.2009, 05:18

Еще диагонали, например прямоугльник ABCD, AB=300, BC=500, CD=300, DA=500, диагональ AC=583, и считаем счто первые две точки А(0;0) и В(0;АВ)->В(0;300)
и нужно найти остальные точки...

На выходе многоугольник как можно с меньшей погрешностью построения...

@Yurii_74 · 27.02.2009, 09:46

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

@ostgals · 27.02.2009, 12:31

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

Таким образом, полигон (многоугольник) можно задать как массив диагоналей, определенных, например, так:

C#
1
2
3
4
5
6
struct Diagonal
{
   int Angle; // угол
   int Length; // длина
   int StartsAt; // индекс предыдущей диагонали или 0, если из точки (0, 0)
}

При этом первая диагональ всегда будет (угол: 0, длина: [задана], диагональ: 0) - угол 0 соответствует положительному направлению оси Y.

Ну, и сам полигон:

C#
1
2
3
4
struct Polygon
{
   Diagonal[] diagonals; // массив диагоналей
}

(Код чисто для наглядности.)

Так как на самом деле задаются на входе диагонали?

Добавлено через 7 минут 22 секунды
Кстати, здесь есть полезный материальчик про триангуляцию многоугольников.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

BOB4uK

	Алгоритм нахождения вершин многоугольника 26.02.2009, 09:48. Показов 3745. Ответов 4 Метки нет (Все метки) Как построить многоугольник с максимальной точностью, если известно: 1.Количество вершин многоугольника 2.Первые две вершины имеют координаты: A(0;0) B(0;длина стороны многоугольника) 3.Многоугольник разбит на треугольники(диагоналями), при этом одна точка может иметь несколько диагоналей Я представляю себе это так: 1. Находим точку у которой есть диагонали уже с известными точками(на первом шаге это A и B) 2. По формуле пересечения двух окружностей находим одну или две точки пересечения и Вот тут то ВОПРОС: как выбрать верную точку? Проблема в том что нужно написать алгоритм который сам определит правильное расположение точек в случае если этих вариантов несколько… Пример на рисунке… http://pic.ipicture.ru/uploads... BLBstw.jpg

@ostgals 886 / 681 / 101 Регистрация: 23.01.2009 Сообщений: 1,582
	26.02.2009, 20:35
	Не совсем понятно... 1. На входе есть количество вершин и еще что? Если диагонали, то каким способом они описываются? 2. Что надо получить на выходе? 0

BOB4uK
	27.02.2009, 05:18
	Еще диагонали, например прямоугльник ABCD, AB=300, BC=500, CD=300, DA=500, диагональ AC=583, и считаем счто первые две точки А(0;0) и В(0;АВ)->В(0;300) и нужно найти остальные точки... На выходе многоугольник как можно с меньшей погрешностью построения...

@Yurii_74 paladin 286 / 187 / 7 Регистрация: 25.02.2009 Сообщений: 589
	27.02.2009, 09:46
	Как я понял, некоторая фигура задается треугольниками (точнее длинами сторон треугольников), и (уже полностью мое предположение) все указанные диагонали должны лежать внутри фигуры. Тогда необходимо строить фигуру так, чтобы треугольники имеющие общую сторону (диагональ требуемой фигуры) лежали по разные стороны от нее. Проверка в принципе не сложная (можно использовать векторное произведение). Дальше, думаю, сам разберешься. 0