Разделение произвольного многоугольника на треугольники

@zontik24 · Регистрация: 14.06.2013

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

Здравствуйте, пишу не в тему Canvas, так как там мало кто обитает

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

На картинках видно, что один можно разделить, а другой - не получается

Может есть средства типа Three.js или что-то подобное для быстой реализации, я же писал на нативе

@cyb0rg_01 · 14.09.2016, 15:27

Пусть 0 - это вершина с которой производится разделение

Разделение произвольного многоугольника на треугольники

тогда начиная с этой вершина любая точка многоугольника, у которой остаток от деления на 2 равен 0, нужно будет соединить со следующей точкой у которой остаток от деления на 2 равен 0.

т.е. нужно рисовать линии из т.0 в т.2 и из т.2 в т.4

@cyb0rg_01 · 14.09.2016, 15:39

В случае если, число сторон нечетное, то последние не соединяются.

@cyb0rg_01 · 14.09.2016, 16:04

еще не учтен такой момент:

Как видно из рисунка, правильность разрезания зависит от того верно ли выбрана начальная вершина, для этого нужно искать такой контур из линий, у которого описывающий прямоугольник имеет наименьшую площадь. описывающий прямоугольник задается максимальными и минимальными значениями Х и Y контура

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

@cyb0rg_01 · 14.09.2016, 16:59

насчет большей площади ошибся(((( попробую на днях выяснить как не допустить выходы линии за пределы многоугольника.

@zontik24 · 14.09.2016, 17:18 **[ТС]**

Спасибо вам за отклик!

@zontik24 · 16.09.2016, 13:20 **[ТС]**

Есть у кого-нибудь задумки?

@Padimanskas · 16.09.2016, 22:01

zontik24,
1. декомпозировать полигон в трапеции
2. декомпозировать трапеции в монотонные полигоны
3. декомпозировать монотонные полигоны треугольники

http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@zontik24 36 / 33 / 10 Регистрация: 14.06.2013 Сообщений: 432

	Разделение произвольного многоугольника на треугольники 13.09.2016, 16:51. Показов 3074. Ответов 7 Метки нет (Все метки) Здравствуйте, пишу не в тему Canvas, так как там мало кто обитает Есть полигон из который собирается в многоугольник произвольный (без самопересечения), нужно его разделить на треугольники, можно, конечно, заюзать алгоритм триангуляции, но я бы хотел обойтись без него. Возможно это как-то осуществить? т.е сначала я рисую контур, потом разделяю У меня не получалось до этого, может у кого есть мысли? На картинках видно, что один можно разделить, а другой - не получается Может есть средства типа Three.js или что-то подобное для быстой реализации, я же писал на нативе Миниатюры 0

@cyb0rg_01 Фрилансер 735 / 352 / 96 Регистрация: 05.05.2014 Сообщений: 2,621
	14.09.2016, 15:27
	Пусть 0 - это вершина с которой производится разделение тогда начиная с этой вершина любая точка многоугольника, у которой остаток от деления на 2 равен 0, нужно будет соединить со следующей точкой у которой остаток от деления на 2 равен 0. т.е. нужно рисовать линии из т.0 в т.2 и из т.2 в т.4 1

@cyb0rg_01 Фрилансер 735 / 352 / 96 Регистрация: 05.05.2014 Сообщений: 2,621
	14.09.2016, 15:39
	В случае если, число сторон нечетное, то последние не соединяются. 1

@cyb0rg_01 Фрилансер 735 / 352 / 96 Регистрация: 05.05.2014 Сообщений: 2,621
	14.09.2016, 16:04
	еще не учтен такой момент: Как видно из рисунка, правильность разрезания зависит от того верно ли выбрана начальная вершина, для этого нужно искать такой контур из линий, у которого описывающий прямоугольник имеет наименьшую площадь. описывающий прямоугольник задается максимальными и минимальными значениями Х и Y контура т.е. нужно в цикле от каждой вершины создавать контур из точек, и выбрать тот, описывающий прямоугольник которого имеет наименьшую площадь. И от нужной вершины рисовать линии описываемым способом 1

@cyb0rg_01 Фрилансер 735 / 352 / 96 Регистрация: 05.05.2014 Сообщений: 2,621
	14.09.2016, 16:59
	насчет большей площади ошибся(((( попробую на днях выяснить как не допустить выходы линии за пределы многоугольника. 1

@zontik24 36 / 33 / 10 Регистрация: 14.06.2013 Сообщений: 432
	14.09.2016, 17:18 [ТС]
	Спасибо вам за отклик! 0

@zontik24 36 / 33 / 10 Регистрация: 14.06.2013 Сообщений: 432
	16.09.2016, 13:20 [ТС]
	Есть у кого-нибудь задумки? 0

@Padimanskas Superposition 950 / 615 / 256 Регистрация: 27.10.2013 Сообщений: 2,083
	16.09.2016, 22:01
	zontik24, 1. декомпозировать полигон в трапеции 2. декомпозировать трапеции в монотонные полигоны 3. декомпозировать монотонные полигоны треугольники http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html 0