Пересечение треугольников

Простейшие вопросы в области инженерной разработки
Ответить
Slime1789
interested
interested
Сообщения: 2
Зарегистрирован: 01 июн 2023, 19:54
Версия LabVIEW: 10
Контактная информация:

Пересечение треугольников

Сообщение Slime1789 »

Здравствуйте, помогите пожалуйста с заданием, звучит оно так: "Дано множество точек на плоскости. Построить все возможные треугольники с вершинами в этом множестве точек и найти среди них такой, стороны которого пересекаются с максимальным количеством треугольников."
Юрий
leader
leader
Сообщения: 526
Зарегистрирован: 28 фев 2010, 18:04
Версия LabVIEW: LV2018
Благодарил (а): 10 раз
Поблагодарили: 18 раз
Контактная информация:

Re: Пересечение треугольников

Сообщение Юрий »

Для затравки. Вариант генератора списка номеров точек треугольников.
Треугольники.png
2023-06-02_012606.jpg
Вложения
Треугольники.vi
(13.36 КБ) 21 скачивание
Slime1789
interested
interested
Сообщения: 2
Зарегистрирован: 01 июн 2023, 19:54
Версия LabVIEW: 10
Контактная информация:

Re: Пересечение треугольников

Сообщение Slime1789 »

Точки вводятся пользователем из текстового файла, и нужно вывод на график и хотелось бы узнать как пересечение треугольников сделать
Последний раз редактировалось Slime1789 02 июн 2023, 20:24, всего редактировалось 1 раз.
Юрий
leader
leader
Сообщения: 526
Зарегистрирован: 28 фев 2010, 18:04
Версия LabVIEW: LV2018
Благодарил (а): 10 раз
Поблагодарили: 18 раз
Контактная информация:

Re: Пересечение треугольников

Сообщение Юрий »

Slime1789 писал(а): 02 июн 2023, 20:02 Точки вводятся пользователем из текстового файла, и нужно вывод на график и хотелось бы узнать как пересечение треугольников сделать
В любом случае из введённых точек нужно будет сформировать набор треугольников. Идентификацию треугольника наиболее удобно представлять номерами точек вершин, как и представлено выше. Каждому номеру точки соответствует её координаты, которые вводит пользователь. Где то на форуме (не смог найти) есть тема, посвящённая определению пересечения между собой множества линий - что то связанное с пересекающимися дорожками печатных плат. Практически там, ну, сажем, на 80% есть подсказки как найти пересечение треугольников.
Аватара пользователя
Jakob Brontfeyn

Activity Gold Silver Black
expert
expert
Сообщения: 1729
Зарегистрирован: 28 фев 2008, 11:01
Награды: 6
Благодарил (а): 1 раз
Контактная информация:

Re: Пересечение треугольников

Сообщение Jakob Brontfeyn »

А не хотите сначала задачу комбинаторную решить.
Дано n случайных точек вершин потенциальных треугольников.
Сколько всего треугольников получится? Будем считать,
что вероятность нахождения трех случайных точек на одной прямой
равна нулю. Ясно, что для n=3 будет один треугольник, а для n=4
уже 4 треугольника. Не гонитесь за большим количеством точек,
для n=5 уже ??? сколько треугольников.
Смотри пример построения треугольников для n=4 разными цветами
Вообще-то мне интуиция подсказывает, что это какая-то сложная математическая проблема.
Уж как-то сильно в общем случае поставлена задача.
Вложения
triangl_4.vi
(38.38 КБ) 91 скачивание
Юрий
leader
leader
Сообщения: 526
Зарегистрирован: 28 фев 2010, 18:04
Версия LabVIEW: LV2018
Благодарил (а): 10 раз
Поблагодарили: 18 раз
Контактная информация:

Re: Пересечение треугольников

Сообщение Юрий »

Юрий писал(а): 02 июн 2023, 23:20 Где то на форуме (не смог найти) есть тема, посвящённая определению пересечения между собой множества линий - что то связанное с пересекающимися дорожками печатных плат. Практически там, ну, сажем, на 80% есть подсказки как найти пересечение треугольников.
Вот она viewtopic.php?p=77200&hilit=%D0%9E%D0%B ... %B8#p77200
Так же прилагаю набросок решения задачи, который, конечно, надо допиливать. В нём есть подпрограмма для определения пересечения двух отрезков.
2023-06-05_183733.jpg
Вложения
Треугольники.zip
(66.13 КБ) 20 скачиваний
Ответить

Вернуться в «Для чайников»