Алгоритм Полигона - C++ - Ответ 2578615

@McVillain · 10.01.2008, 16:47

> Предполагаю следующую реакцию: 'Еще хуже!'.

А вот и неправда!

Никакой реакции. Произвольный - и пусть его произвольный.

===============

Как я вижу алгоритм...

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

2. Разбить невыпуклый многоугольник на треугольники. Наверное, есть какие-то более умные алгоритмы, но я их не знаю. Предлагаю следующее:

Взять три подряд идущие вершины а(i), а(i+1), а(i+2) контура. Если отрезок а(i)-а(i+2) лежит внутри многоугольника (см. ниже), запомнить треугольник а(i)-а(i+1)-а(i+2) и перейти к контуру a(0)-a(1)-..-a(i)-a(i+2)-..-a(n), полученному из начального исключением вершины a(i+1). В противном случае перейти к следующей тройке контура. В итоге получаем совокупность треугольников, покрывающих без перекрытия исходный многоугольник.

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

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

точка X лежит внутри треугольника ABC, если и только если знаки третьих координат векторных произведений [AX, AB], [BX, BC], [CX, CA] совпадают.

С не меньшим уважением.

PS Тормозить будет жутко.

Вернуться к обсуждению:
Алгоритм Полигона C++

Следующий ответ

Другие темы раздела
C++ Как запустить COM InprocServer как LocalServer? Привет! Подскажите как запустить COM InprocServer как LocalServer? Как правильно загрузить суррогат? Что надо писать в реестр? В MSDN не очень понятно :( Спасибо, Кирилл. https://www.cyberforum.ru/ cpp-beginners/ thread464134.html	Как производится векторизация BITMAP? C++ Народ поможите! Как производится векторизация BITMAP и тому подобное.
C++ Где достать контрол с диаграммой Ганта? Кто-нибудь подскажет, где достать контрол с диаграммой Ганта... Заранее благодарен... https://www.cyberforum.ru/ cpp-beginners/ thread464104.html	C++ Как записать структуру в файл? есть структура struct frend { char name; char tel; };как записать ее в файл и потом считат соответственно)) заранее благодарен Роман https://www.cyberforum.ru/ cpp-beginners/ thread464074.html
Есть ли в Windows какой-нибудь стандартный "загрузчик dll"? C++ у меня всю задачу выполняет DLL... есть ли в виндовс какойнить файл который позволяет загрузть DLL чтобы не писать прогу которая ее активизирует? заранее благодарен.	C++ Как отправить email, используя win32? заморочка... как отправить сообщение на email не используя MFC и его классы... принимаются любые предложения ) заранее благодарен... https://www.cyberforum.ru/ cpp-beginners/ thread464072.html
C++ Ошибка при работе с портами https://www.cyberforum.ru/ cpp-beginners/ thread464067.html Следующ.кусок кода определяет нажата клавиша Esc или F8. После компиляции при запуске проги и при нажатии F8 вызывается функция printf произвольное кол-во раз (по идее должно всего один), но под дебагером printf вызывается один раз. И в Borlande и в Watcome одинаковый результат while (chz!=1) { asm { mov byte ptr ,0 in al,060h //читаем код клавиши mov byte ptr ,al	C++ Отличия: CreateWindow() от СFrameWnd::Create(); ЛЮДИ! Чем отличается CreateWindow() от СFrameWnd::Create(); Они вообще как-нибудь друг с другом соотносятся??? Ну ламер я, ламер...
C++ Как в функцию обработки сообщений передать параметры? Как в функцию обработки сообщений типа void CMathematicsView::OnResultButton() передать параметры? Как и где написать прототип и определение - понятно. Но как о откуда вызвать эту функцию в моем коде? Спасибо всем, кто ответит! https://www.cyberforum.ru/ cpp-beginners/ thread464056.html	C++ Как в коде задать высоту выпадающего списка ComboBox? https://www.cyberforum.ru/ cpp-beginners/ thread464055.html Создаю в клиентской области комбинированные окна списка ComboBox, используя функции: m_inputWindow.Create(WS_VISIBLE \| WS_CHILD \| WS_TABSTOP \| CBS_DROPDOWN, CRect( 120, nextStringY, 190, nextStringY + 20 ), this, 121 + i); ... m_inputWindow.AddString(_itoa(pDoc->GetMemberC(j), aBuffer, 10));Окна на экран выводятся, список заполняется значениями, но при раскрытии он имеет нулевую высоту. Как ее...
Как послать сообщение по асе? C++ мне необходимо в фоновом режиме послать сообщение по ICQ на определенный (заранее известный) UIN... ася уже загружена... хотя если можно без ее явного рисутствия - тоже подойдет))) в общем, с удовольствием выслушаю любую информацию на эту тему... заранее благодарен...	C++ Я понял, мало кто знает, как ПРАВИЛЬНО интегрировать Internet Explorer в свою :-) окно... https://www.cyberforum.ru/ cpp-beginners/ thread464013.html Али все же кто-то этим занимался? (Да не сочтет модератор это дублированием :-)) Снорк.

	10.01.2008, 16:47