2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Поиск сегментов в пространстве, ограниченных отрезками
Сообщение18.05.2023, 12:20 
Добрый день, пытаюсь решить следующую задачу
Есть набор точек в 2-х мерном пространстве и набор прямых отрезков, которые соединяют некоторые пары точек.
Задача состоит в том, чтобы найти все сегменты в пространстве, ограниченные данными отрезками.

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

- Комната 1: [стена1, стена2 и т.д.]
- Комната 2: [стена1, стена2 и т.д.]


Подскажите пожалуйста есть ли какие-то готовые алгоритмы на данную темы? Или подходы к ее решению

 
 
 
 Re: Поиск сегментов в пространстве, ограниченных отрезками
Сообщение18.05.2023, 22:18 
Как по мне, зря вы теорию графов пытаетесь применить — в ней, насколько я понимаю, нужное вам понятие отсутствует.
Если не принимать во внимание экзотические квартиры с круглыми или косыми (в форме параллелограмма) комнатами, можно, имхо, попробовать вести достаточно длинный отрезок, параллельный одной из стен, перпендикулярно себе. Стены будут разбивать его на различные части в зависимости от положения. Смена разбиения означает... Ну, что-то означает.

 
 
 
 Re: Поиск сегментов в пространстве, ограниченных отрезками
Сообщение18.05.2023, 22:43 
Аватара пользователя
Что такое "сегменты"?
Я правильно понимаю, что задача - найти наборы отрезков, каждый из которых задает многоугольник, внутри которого никаких отрезков уже нет?

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group