Выявить все треугольники, не пересекающиеся с другими треугольниками этого набора

@Kykylllka · Регистрация: 17.05.2014

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

Всем привет!

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

Перелопатил весь интернет в поисках решения, ничего не нашёл, вообще ничего, все пишут про пересечение отрезков и останавливаются на этом.

Я понял, что надо подходить к решению через определение пересечения отрезков треугольника, написал алгоритм:

C++
1
2
3
4
5
float v1 = (stprov[j+1].X-stprov[i+1].X)*(stprov[i].Y-stprov[i+1].Y)-(stprov[j+1].Y-stprov[i+1].Y)*(stprov[i].X-stprov[i+1].X);
float v2 = (stprov[j+1].X-stprov[i+1].X)*(stprov[j].Y-stprov[i+1].Y)-(stprov[j+1].Y-stprov[i+1].Y)*(stprov[j].X-stprov[i+1].X);
float v3 = (stprov[j].X-stprov[i].X)*(stprov[i+1].Y-stprov[i].Y)-(stprov[j].Y-stprov[i].Y)*(stprov[i+1].X-stprov[i].X);
float v4 = (stprov[j].X-stprov[i].X)*(stprov[j+1].Y-stprov[i].Y)-(stprov[j].Y-stprov[i].Y)*(stprov[j+1].X-stprov[i].X);
if (((v1*v2)<0) && ((v3*v4)<0)) ...

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

У меня дело обстоит так, что я ввожу данные 3-мя способами: рандом, с файла, в ручную и по этим данным строю треугольники. Данные о координатах каждой точки находятся в структуре и к ним надо обращаться.
И каждый раз новые проблемы которые я ни как не могу обойти. Я не буду их описывать, я прошу у вас помощи, подкиньте идей, или просто пруф на спрятанную в самых недрах интернета страницу с решением поставленной задачи.

Tulosba · 31.05.2014, 23:48

Сообщение от Kykylllka

все пишут про пересечение отрезков и останавливаются на этом.

А как же хотя бы это?

@Kykylllka · 31.05.2014, 23:51 **[ТС]**

Не вижу там ничего полезного для моей проблемы.

Добавлено через 1 минуту
Хотя я лучше все прочитаю, а потом сделаю вывод

Tulosba · 31.05.2014, 23:53

Сообщение от Kykylllka

Не вижу там ничего полезного для моей проблемы.

Что такое треугольник, как не частный случай выпуклого многоугольника.

@Kykylllka · 01.06.2014, 00:08 **[ТС]**

Я прочитал 2 раза, понял что это какая-то жесть, и без объяснения я не смогу это понять.

Tulosba · 01.06.2014, 00:15

Kykylllka, я предложил первое, что выдал гугл. Суть в том, что метод определения пересечений треугольников - это частный случай метода определения пересечения многоугольников. А такой инфы в инете полно.

@Kykylllka · 01.06.2014, 16:13 **[ТС]**

Tulosba, спасибо. Буду дальше лопатить интернет.

Если кто-нибудь владеет какой-либо информацией, не поленитесь и отпишитесь, буду при много благодарен.

Добавлено через 14 часов 14 минут
Так и ничего не нашёл

(

Добавлено через 1 час 37 минут
Хелп

Новые блоги и статьи Все статьи Все блоги /
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 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Kykylllka 0 / 0 / 0 Регистрация: 17.05.2014 Сообщений: 12
	31.05.2014, 23:51 [ТС]
	Не вижу там ничего полезного для моей проблемы. Добавлено через 1 минуту Хотя я лучше все прочитаю, а потом сделаю вывод 0

@Kykylllka 0 / 0 / 0 Регистрация: 17.05.2014 Сообщений: 12
	01.06.2014, 00:08 [ТС]
	Я прочитал 2 раза, понял что это какая-то жесть, и без объяснения я не смогу это понять. 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	01.06.2014, 00:15
	Kykylllka, я предложил первое, что выдал гугл. Суть в том, что метод определения пересечений треугольников - это частный случай метода определения пересечения многоугольников. А такой инфы в инете полно. 0

@Kykylllka 0 / 0 / 0 Регистрация: 17.05.2014 Сообщений: 12
	01.06.2014, 16:13 [ТС]
	Tulosba, спасибо. Буду дальше лопатить интернет. Если кто-нибудь владеет какой-либо информацией, не поленитесь и отпишитесь, буду при много благодарен. Добавлено через 14 часов 14 минут Так и ничего не нашёл ( Добавлено через 1 час 37 минут Хелп 0