С Новым годом! Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгоритм Полигона - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Как запустить COM InprocServer как LocalServer? http://www.cyberforum.ru/cpp-beginners/thread464134.html
Привет! Подскажите как запустить COM InprocServer как LocalServer? Как правильно загрузить суррогат? Что надо писать в реестр? В MSDN не очень понятно :( Спасибо, Кирилл.
C++ Как производится векторизация BITMAP? Народ поможите! Как производится векторизация BITMAP и тому подобное. http://www.cyberforum.ru/cpp-beginners/thread464123.html
C++ Где достать контрол с диаграммой Ганта?
Кто-нибудь подскажет, где достать контрол с диаграммой Ганта... Заранее благодарен...
C++ Как записать структуру в файл?
есть структура struct frend { char name; char tel; };как записать ее в файл и потом считат соответственно)) заранее благодарен Роман
C++ Есть ли в Windows какой-нибудь стандартный "загрузчик dll"? http://www.cyberforum.ru/cpp-beginners/thread464073.html
у меня всю задачу выполняет DLL... есть ли в виндовс какойнить файл который позволяет загрузть DLL чтобы не писать прогу которая ее активизирует? заранее благодарен.
C++ Как отправить email, используя win32? заморочка... как отправить сообщение на email не используя MFC и его классы... принимаются любые предложения ) заранее благодарен... подробнее

Показать сообщение отдельно
McVillain
1 / 1 / 0
Регистрация: 30.04.2007
Сообщений: 226
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 Тормозить будет жутко.
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.