На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Помогите с алгоритмом поиска замкнутой области
    Есть n отрезков. Есть координаты концов отрезков [(x11,y11),(x12,y12)]...[(x1i,y1i),(x1i,y1i)]...[(x1n,y1n),(x1n,y1n)]. Нужно найти все многоугольники (составляющие их отрезки), образующие замкнутые фигуры. При этом замкнутые фигуры должны быть базисными, т.е. не иметь вложенных замкнутостей.

    Может кто знает алгоритм? Очень нужно реализовать. :( Пожалуйста помогите.  
    Заранее спасибо  :)  
      Неужели такая задачка нигде не решалась  ???
        преобразовываешь в граф и ищешь все цыклы. незнаю как, никогда не пробовал, хотя неоднократно читал ;D . . даже могу при желании коечто вспомнить.
        хотя там отрезки могут ещё пересекаться....
        тогда ищешь все пересечения и принимаешь их тоже за вершины.
          Спасибо, за внимание.  :)
           ;D Первая мысль у меня тоже была в граф преобразовать. Но есть несколько но.  ;D
          1. Граф неориентированный. А в инете я нашел только алгоритм исключения вершин не входящих в цикл (строится матрица связности и т.д.) и то он для ориентированного графа.
          2. В инете нашел только алгоритмы поиска эйлерова и еще какого-то (не помню какого, но не того) цикла.
          3. Нужны ведь базисные циклы   ;) Т.е. играет значение не только какая прямая с какой связанна, а еще и координаты начала и конца прямых. Поясняю:

                          1 -----2                          1 -----2         Для графа разницы между этими
                          |         |                         |         |         картинками не будет. А базисные
                          |         3---4                   |  4----3         циклы будут разные.
                          |         |     |                   |  |     |
                          |         |     |                   |  |     |
                          |         5---6                   |  6----5
                          |         |                         |         |
                          8------7                         8------7

          Кто знает, помогите. Мне не сегодня завтра перед преподом отчитываться. Он мне устроит стимуляцию чего-нибудь.  :(
          Буду рад любым замечаниям.


            Забыл еще сказать.  :) Отрезки по  условию не могут пересекаться. В противном случае происходит разбиение отрезка в точке пересечения на 2 отрезка.
              Кому-нибудь нужен алгоритм? Если нужен опишу основную идею. Как руки дойдут исходник сбацаю. Я сразу бы описал, да интересно нужен ли кому такой алгоритм  ;)
              Пишите  :)
                Как готово будет высылай мне на мыло, или сам алгоритм выкладывай прямо здесь. Нечего секретничать  ;D
                  Слово модератора закон  ;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
                  Может где, что не так расказал или упустил, но в принципе все должно работать.
                  Вроде и програмирование мне сильно страшным не представляется. Составляется пара вспомогательных матриц и все нормально.

                  Если что непонятно или есть вопросы, спрашивайте, постараюсь ответить.
                  Мне сегодня вечером придется исходник на енто дело стряпать  ;)
                  Так что если есть предложения сделать попроще - пишите  :)













                    Тут небольшой касяк при программировании выяснился.
                     2
                       |
                     1|______3
                       |
                       |
                      4
                    Т.е. если начать обход со стенки 1-3 в направлении 3, получим, что двигаться некуда кроме как в точку 1. Получится ситуация будто обход завершен и комната найдена.

                    Для того чтоб исправить просто не начинаем обход с подобных аппенидксов. В нумерацию они все равно попадут в силу соединения с другими стенками.

                    Что-то у меня ощущение, что я сам с собой разговариваю. :-)
                    Мож пора лечится?  ::)
                      Это ты зря,
                      Как стати с исходником??? Охото глянуть на произведение других.
                      Тут накидал сам нечто подобное, щас проверяю.
                        Кстати немного изменил твои алгоритм поиска
                          2animos

                          так ето снова по поводу поиска циклов в графе. ведь циклы ищутся так: последовательно удаляешь все вершины, которые соединены только с одной другой вершиной, пока таковые не закончатся. после проведения подобной операции у тебя не может возникнуть ситуации, указанной на рисунке.
                            Извиняюсь, что долго молчал. :)  На выходных не мог кинуть исходник (не такая большая зарпалата чтобы дома в инете сидеть). А в понедельник не было дистрибутива Visio, чтоб из проекта исходник выдрать.

                            Держите  ;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
                              Забыл. Тут функция в другом модуле завалялась.

                              Function gint(stroka As String) As Double   ' функция которая делает из (120 мм) просто 120
                               gint = Mid(stroka, 1, Len(stroka) - 2)
                              End Function


                              Вобще-то програмка для Visio (в проекте есть объект с названием Walls - из них и состоят комнаты, которые ищем), но и без него можно понять, что к чему.   :)
                                Цитата GrAnd, 17.04.03, 11:55:39
                                Кстати немного изменил твои алгоритм поиска


                                Можно поинтересоваться что за изменение.  :)
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0401 ]   [ 15 queries used ]   [ Generated: 21.05.24, 07:43 GMT ]