![>](style_images/1/nav_m.gif)
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.135.190.113] |
![]() |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Есть n отрезков. Есть координаты концов отрезков [(x11,y11),(x12,y12)]...[(x1i,y1i),(x1i,y1i)]...[(x1n,y1n),(x1n,y1n)]. Нужно найти все многоугольники (составляющие их отрезки), образующие замкнутые фигуры. При этом замкнутые фигуры должны быть базисными, т.е. не иметь вложенных замкнутостей.
Может кто знает алгоритм? Очень нужно реализовать. ![]() Заранее спасибо :) |
Сообщ.
#2
,
|
|
|
Неужели такая задачка нигде не решалась ???
|
Сообщ.
#3
,
|
|
|
преобразовываешь в граф и ищешь все цыклы. незнаю как, никогда не пробовал, хотя неоднократно читал ;D . . даже могу при желании коечто вспомнить.
хотя там отрезки могут ещё пересекаться.... тогда ищешь все пересечения и принимаешь их тоже за вершины. |
Сообщ.
#4
,
|
|
|
Спасибо, за внимание. :)
;D Первая мысль у меня тоже была в граф преобразовать. Но есть несколько но. ;D 1. Граф неориентированный. А в инете я нашел только алгоритм исключения вершин не входящих в цикл (строится матрица связности и т.д.) и то он для ориентированного графа. 2. В инете нашел только алгоритмы поиска эйлерова и еще какого-то (не помню какого, но не того) цикла. 3. Нужны ведь базисные циклы ![]() 1 -----2 1 -----2 Для графа разницы между этими | | | | картинками не будет. А базисные | 3---4 | 4----3 циклы будут разные. | | | | | | | | | | | | | 5---6 | 6----5 | | | | 8------7 8------7 Кто знает, помогите. Мне не сегодня завтра перед преподом отчитываться. Он мне устроит стимуляцию чего-нибудь. :( Буду рад любым замечаниям. |
Сообщ.
#5
,
|
|
|
Забыл еще сказать. :) Отрезки по условию не могут пересекаться. В противном случае происходит разбиение отрезка в точке пересечения на 2 отрезка.
|
Сообщ.
#6
,
|
|
|
Кому-нибудь нужен алгоритм? Если нужен опишу основную идею. Как руки дойдут исходник сбацаю. Я сразу бы описал, да интересно нужен ли кому такой алгоритм ;)
Пишите :) |
Сообщ.
#7
,
|
|
|
Как готово будет высылай мне на мыло, или сам алгоритм выкладывай прямо здесь. Нечего секретничать ;D
|
Сообщ.
#8
,
|
|
|
Слово модератора закон ;D
А алгоритм в принципе простой. Принимаем, что справа и слева от любой стены должна находиться комната. Даже если стенка наружная у нее с одной стороны внутреняя комната, с другой бесконечное пространство - тоже комната. Алгоритм заключается в обходе всех стенок. Поступаем так. Берем любую стенку. Есть координаты концов стенки. Пусть какая нибудь начало, какая нибудь конец (практически выбираем направление). Помечаем. что справа (слева) находится комната №1. От того справа или слева будет зависеть направление обхода (по часовой или против). Находим стыки с другими стенками (это просто сравнение координат). Находим наиболее правую (левую) стенку по часовой (против часовой) стрелки. На рисунке понятнее. __3 -- 1------2---------4 №1 --___5 №1 Т.е. в данном случае следующую стенку выбираем 2-5. Помечаем эту стенку №1. И так до тех пор пока не придем опять в начало. А в начало мы обязательно попадем, если делать различие между стенками с одинковыми координатами но с разными началом и концом. Т.е. 1-2 и 2-1. Т.е. №1 1-------------2 №1 Т.е. дойдя до точки 2 нам некуда будет идти кроме как в направлении 2-1. Предполагается что угол между 1-2 и 2-1 минимальный. Это для того, чтобы идти в этом направлении только если больше нет никаких стенок. Как только пришли в исходную точку, ищем следующую непомеченую стенку справа (слева) (не забывать, что стенки 2-1 и 1-2 - условно разные, а обход мы делаем всегда в одну сторону). Как только непомеченные стенки кончились значит все комнаты найдены. Единственное что плохо придется проверять на вложенность. Так как возможна ситуация №3 --------------------------------- | №2 | | №1 | | ------ | №3 |№2 №1| №4 |№1 №2 |№3 | ----- | | №1 | | №2 | --------------------------------- №3 Может где, что не так расказал или упустил, но в принципе все должно работать. Вроде и програмирование мне сильно страшным не представляется. Составляется пара вспомогательных матриц и все нормально. Если что непонятно или есть вопросы, спрашивайте, постараюсь ответить. Мне сегодня вечером придется исходник на енто дело стряпать ;) Так что если есть предложения сделать попроще - пишите :) |
Сообщ.
#9
,
|
|
|
Тут небольшой касяк при программировании выяснился.
2 | 1|______3 | | 4 Т.е. если начать обход со стенки 1-3 в направлении 3, получим, что двигаться некуда кроме как в точку 1. Получится ситуация будто обход завершен и комната найдена. Для того чтоб исправить просто не начинаем обход с подобных аппенидксов. В нумерацию они все равно попадут в силу соединения с другими стенками. Что-то у меня ощущение, что я сам с собой разговариваю. :-) Мож пора лечится? : ![]() |
Сообщ.
#10
,
|
|
|
Это ты зря,
Как стати с исходником??? Охото глянуть на произведение других. Тут накидал сам нечто подобное, щас проверяю. |
Сообщ.
#11
,
|
|
|
Кстати немного изменил твои алгоритм поиска
|
Сообщ.
#12
,
|
|
|
2animos
так ето снова по поводу поиска циклов в графе. ведь циклы ищутся так: последовательно удаляешь все вершины, которые соединены только с одной другой вершиной, пока таковые не закончатся. после проведения подобной операции у тебя не может возникнуть ситуации, указанной на рисунке. |
Сообщ.
#13
,
|
|
|
Извиняюсь, что долго молчал.
![]() Держите ;D Attribute VB_Name = "poisk_komnat" Public Sub poisk_komnat() Dim alpha As Double ' точность с которой считается, что alpha = 0.000001 ' стык стенки соединен Dim walls As New Collection 'колллекция где будут хранится комнаты 'поместим все стенки проекта в коллекцию: Dim find As Boolean find = False Dim count_point As Integer count_point = 1 For i = 1 To Documents(1).Pages(1).Shapes.Count If Mid(Documents(1).Pages(1).Shapes(i).Name, 1, 4) = "Wall" Then walls.Add Item:=Documents(1).Pages(1).Shapes(i) End If Next i Dim tochka() As Double ReDim tochka(1 To 2 * walls.Count, 2) As Double For i = 1 To walls.Count tochka(2 * (i - 1) + 1, 1) = gint(walls(i).Cells("BeginX")) tochka(2 * (i - 1) + 1, 2) = gint(walls(i).Cells("BeginY")) tochka(2 * (i - 1) + 2, 1) = gint(walls(i).Cells("EndX")) tochka(2 * (i - 1) + 2, 2) = gint(walls(i).Cells("EndY")) Next i For i = 2 To 2 * walls.Count For j = 1 To i - 1 If Abs(tochka(j, 1) - tochka(i, 1)) < alpha And Abs(tochka(j, 2) - tochka(i, 2)) < alpha Then find = True End If Next j If find Then find = False Else count_point = count_point + 1 End If Next i '--------------------------------- Dim u_tochka() As Double ReDim u_tochka(1 To count_point, 2) As Double u_tochka(1, 1) = tochka(1, 1) u_tochka(1, 2) = tochka(1, 2) k = 1 Debug.Print Str(1) + ">" + Str(u_tochka(1, 1)) + ":" + Str(u_tochka(1, 2)) For i = 2 To 2 * walls.Count For j = 1 To i - 1 If Abs(tochka(j, 1) - tochka(i, 1)) < alpha And Abs(tochka(j, 2) - tochka(i, 2)) < alpha Then find = True End If Next j If find Then find = False Else k = k + 1 u_tochka(k, 1) = tochka(i, 1) u_tochka(k, 2) = tochka(i, 2) Debug.Print Str(k) + ">" + Str(u_tochka(k, 1)) + ":" + Str(u_tochka(k, 2)) End If Next i '--------------строим вспомогательные матрицы---------- Dim U() As Double Dim NS() As Integer Dim Nk() As Integer ReDim U(1 To count_point, 1 To count_point) As Double ReDim NS(1 To count_point, 1 To count_point) As Integer ReDim Nk(1 To count_point, 1 To count_point) As Integer Dim find_i As Boolean Dim find_j As Boolean find_i = False find_j = False Dim i_k As Integer Dim j_k As Integer i_k = 1 j_k = 1 Debug.Print "____" For i = 1 To count_point For j = 1 To count_point For k = 1 To 2 * walls.Count If (Not i = j) And Abs(u_tochka(i, 1) - tochka(k, 1)) < alpha And Abs(u_tochka(i, 2) - tochka(k, 2)) < alpha Then find_i = True i_k = k End If If (Not i = j) And Abs(u_tochka(j, 1) - tochka(k, 1)) < alpha And Abs(u_tochka(j, 2) - tochka(k, 2)) < alpha Then find_j = True j_k = k End If If find_i = True And find_j = True Then If (i_k + 1) \ 2 = (j_k + 1) \ 2 Then 'заполним матрицу NS(i,j): NS(i, j) = (i_k + 1) \ 2 ' Debug.Print NS(i, j) 'заполним матрицу u(i,j): U(i, j) = ugol(tochka(i_k, 1), tochka(i_k, 2), tochka(j_k, 1), tochka(j_k, 2)) Debug.Print Str(i) + "->" + Str(j) + ":" + Str(U(i, j)) Exit For End If End If Next k find_i = False find_j = False Next j Next i 'Теперь собственно найдем комнаты: Dim counter_room As Integer counter_room = 1 Dim t_i As Integer Dim t_j As Integer Dim max As Integer For i = 1 To count_point For j = 1 To count_point If Nk(i, j) = 0 And Not (NS(i, j) = 0) Then 'надо искать комнату t_i = i t_j = j Nk(i, j) = counter_room Debug.Print Str(i) + ":" + Str(j) + ">" + Str(counter_room) While Not (t_j = i) 'пока не пришли в начальную точку первой стенки max = t_i For k = 1 To count_point If Not (NS(t_j, k) = 0) And (U(t_j, k) + (360 - (180 + U(t_i, t_j)) Mod 360)) Mod 360 >= (U(t_j, max) + (360 - (180 + U(t_i, t_j)) Mod 360)) Mod 360 Then 'ищем максимальный угол If t_i < t_j Or t_i > t_j Then max = k End If End If Next k t_i = t_j 'перескакиваем на другую стенку t_j = max Nk(t_i, t_j) = counter_room Debug.Print Str(t_i) + ":" + Str(t_j) + ">" + Str(counter_room) Wend counter_room = counter_room + 1 'увеличиваем счетчик комнат End If Next j Next i ' Nk - искомая матрица End Sub Public Function ugol(x1 As Double, y1 As Double, x2 As Double, y2 As Double) As Double If Abs(y2 - y1) < 0.000001 And Abs(x2 - x1) < 0.000001 Then Else If Abs(y2 - y1) < 0.000001 Then If x2 > x1 Then ugol = 180 Else ugol = 0 End If ElseIf y2 < y1 Then ugol = Round((540 - 180 * (arccos((x2 - x1) / Sqr((x2 - x1) ^ 2 + (y2 - y1) ^ 2))) / 3.1415926535) Mod 360) ElseIf y2 > y1 Then ugol = Round(180 + 180 * (arccos((x2 - x1) / Sqr((x2 - x1) ^ 2 + (y2 - y1) ^ 2))) / 3.1415926535) End If End If End Function Function lent(x1 As Double, y1 As Double, x2 As Double, y2 As Double) lent = Sqr((x1 - x2) ^ 2 + (y1 - y2) ^ 2) End Function Public Function arccos(xx As Double) As Double arccos = Atn(-xx / Sqr(-xx * xx + 1)) + 2 * Atn(1) End Function _______________________________________________________________________ В этом коде нет проверки на вложенности. Препод сказал и так нормально. Во всех остальных случаях все работает. Пришлось на Basic писать, хотя я больше Си люблю. Basic потому что его Visio поддерживает. А Visio -чтоб с интерфейсом не парится. ;) Жду комментариев. Покритикуйте код. Я часто не вижу очевидных простых решений, но стараюсь от этого избавится. Помогайте. ;D |
Сообщ.
#14
,
|
|
|
Забыл. Тут функция в другом модуле завалялась.
Function gint(stroka As String) As Double ' функция которая делает из (120 мм) просто 120 gint = Mid(stroka, 1, Len(stroka) - 2) End Function Вобще-то програмка для Visio (в проекте есть объект с названием Walls - из них и состоят комнаты, которые ищем), но и без него можно понять, что к чему. ![]() |
Сообщ.
#15
,
|
|
|
Цитата GrAnd, 17.04.03, 11:55:39 Кстати немного изменил твои алгоритм поиска Можно поинтересоваться что за изменение. :) |