Помогите с алгоритмом поиска замкнутой области

Есть 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

Кстати немного изменил твои алгоритм поиска

Можно поинтересоваться что за изменение.  :)