طوبولوجيا الشبكة الثلاثية

Question

لدي فئة شبكية مثلثة تحتوي على قائمة بالعقد (ثنائية الأبعاد في حالتي ولكن هذا لا يهم) وقائمة الوجوه.كل وجه عبارة عن مثلث ويحتوي فقط على المؤشرات الموجودة في مصفوفة العقدة.الشبكة تأتي من خوارزمية Delaunay لذا فهي نظيفة جدًا.

بالنسبة لكل عقدة في الشبكة، أحتاج إلى العثور على العقد المتصلة بها بحافة واحدة.ما هي الطريقة السريعة لإنشاء قاعدة بيانات الطوبولوجيا هذه والبحث فيها؟

ملزم كثيرًا ، ديفيد روتن

Answer 1

هناك نوعان من بنيات البيانات القياسية إلى حد ما التي تسهل استعلامات طوبولوجيا الشبكة.واحد هو حواف مجنحة (ويشار إليها عادة باسم نصف الحافة)، والآخر هو الحواف الموجهة.ابحث في Google وستجد عددًا كبيرًا من التفاصيل ومقدمات متعددة المستويات في كل منها.

لا تعرف ما يكفي عن السيناريو الخاص بك للتوصية بأحدها.على سبيل المثال، الحواف الموجهة مُحسّنة للتخزين، وهي مناسبة بشكل أفضل للشبكات الكبيرة جدًا.تعتبر الحواف المجنحة "كلاسيكية"، وهي نقطة انطلاق جيدة للنكهات الأكثر تقدمًا.

في الواقع، إذا كنت متأكدًا من أن هذا هو الاستعلام الوحيد الذي ستحتاج إليه، فكلاهما يعد مبالغة وستكون جيدًا باستخدام تجزئة واحدة.ومع ذلك، إذا وجدت نفسك بحاجة إلى إجابات فعالة لاستفسارات مثل -

• ما هي الوجوه التي تستخدم هذه القمة؟
• ما هي الحواف التي تستخدم هذا الرأس؟
• ما هي الوجوه التي تحد هذه الحافة؟
• ما هي الحواف التي تحد هذا الوجه؟
• ما هي الوجوه المجاورة لهذا الوجه؟

يجب أن تفكر في الغوص في واحد منهم.

Answer 2

وأعتقد أنني قد يحدق نفسي أعمى على HashTables، قواميس وقوائم الترتيب ... وفيما يلي ربما تكون أسهل وأسرع:

Public Sub SolveConnectivity(ByVal nodes As Node2List, ByVal faces As List(Of Face))
  m_map = New List(Of List(Of Int32))(nodes.Count)

  'Create blank lists
  For i As Int32 = 0 To nodes.Count - 1
    m_map.Add(New List(Of Int32)(6))
  Next

  'Populate connectivity diagram
  For i As Int32 = 0 To faces.Count - 1
    Dim F As Face = faces(i)
    m_map(F.A).Add(F.B)
    m_map(F.A).Add(F.C)

    m_map(F.B).Add(F.A)
    m_map(F.B).Add(F.C)

    m_map(F.C).Add(F.A)
    m_map(F.C).Add(F.B)
  Next
End Sub