🤸🏼 ☁️ ♟️ خوارزميات للبحث في حجم ووسط كتلة متعدد السطوح 💭 👨🏽‍🌾 🌗

ربما يعلم الجميع هذه الخوارزمية ، لكن "السلطات كانت مختبئة عني". لقد وجدت وصفه اللفظي في الصفحة الثالثة من محرك البحث في أرشيف الترجمات الآلية لمنتدى اللغة الإنجليزية. يبدو لي أن وصفها المفصل (ومع الكود) يستحق habrosta.

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

الغوغاء عبارة عن متعدد الوجوه ، نظرًا إلى البساطة ، فإننا نعتقد أن المجسم متعدد الوجوه يتكون فقط من مثلثات (في الخوارزمية الموجودة داخل صيغة منطقة غاوس ، بحيث يمكنك توسيعها لأي مجسم متعدد السطوح ، ولكن لماذا ...). بالإضافة إلى ذلك ، لا ينبغي أن يكون متعدد السطوح التقاطعات الذاتية والحد من حجم مغلقة ، كما يليق المجسم متعدد السطوح لائق.

(حسنا ، هكذا)

UPD صغير يشرح لماذا الغوغاء الأيمن على KDPV ليس على ما يرام ، ولكن اليسار موافق:
الصورة الصحيحة ليست موافق لأن الغوغاء سوف يسقطون للأمام يمتد مركز كتلته خارج منطقة الدعم. يتم تعريف منطقة الدعم لمضلع يقف على السطح على أنه الحد الأدنى للمضلع الذي توجد به جميع النقاط على السطح. في الحالة اليسرى ، يتم نقل منطقة الدعم إلى مركز الكتلة وأكثر من ذلك (لأن مخالب الديناصورات أكبر) ، وفي الصورة اليمنى تكون المنطقة نفسها أصغر وأقرب من الذيل.
ستكون نسبة المساحة المرجعية إلى مركز الكتلة مثل هذا:

سأبدأ على الفور برمز البحث الصوتي (Python ، إدخال - قائمة بالنقاط ومصفوفة انتقال):

بعض الكود

def RecSetDirsTriangles(para, Connects, TR): """ ,           """ #1.   , ,     for i in range(0,len(Connects)): if i != para[0] and i != para[1] and Connects[i][para[0]] and Connects[i][para[1]]: #  ! fl = 1 for T in TR: if i in T and para[1] in T and para[0] in T: fl = 0 #    break if fl: # ! TR += [(para[1],para[0],i)] Recc((para[0], i) , Connects, TR) Recc((i, para[1]) , Connects, TR) def FindV(dots, Connects): """ .   - dots     [x, y, z], Connects -  , Connects[i][j]=1      i, j,  =0 """ #1.      TR = [] for i in range(1,len(Connects)):#        - if Connects[i][0]: for j in range(i+1, len(Connects)): if Connects[0][j] and Connects[i][j]: TR += [(0,i,j)] break RecSetDirsTriangles((0,i),Connects, TR) break print(" : ", len(TR)) #2.        V = 0 for T in TR: ''' : x1y2 x2y3 x3y1 x2y1 x3y2 x1y3''' S = 0.5 * (dots[T[0]][0]*dots[T[1]][1] + dots[T[1]][0]*dots[T[2]][1] + dots[T[2]][0]*dots[T[0]][1] - dots[T[1]][0]*dots[T[0]][1] - dots[T[2]][0]*dots[T[1]][1] - dots[T[0]][0]*dots[T[2]][1]) #S   +  -    ,    V += S*(dots[T[0]][2] + dots[T[1]][2] + dots[T[2]][2])/3 #    ... return math.fabs(V)

جوهر الخوارزمية هو النظر في أحجام الأشكال التي تشكل وجوه متعدد السطوح التي "تسقط" على المستوي xy. للقيام بذلك ، تحتاج إلى معرفة منطقة الإسقاط للمثلث والإشارة التي لإضافة حجم الشكل (المنشور المقطوع). في الواقع ، إذا تم طلب المثلثات مقدمًا ، يتم تخفيض كل من الحجم والإشارة إلى حساب واحد.

لذلك ، فإن أول شيء تقوم دالة عودية بتجميع المثلثات منه هو الإدخال. يتم التجميع بطريقة بحيث عند النظر إلى "الخارج" في مجسم متعدد الوجوه ، تكون اتجاهات الالتفاف حول المثلثات هي نفسها (من الناحية المثالية عكس اتجاه عقارب الساعة ؛ إذا كنت تأخذ الاتجاهات في اتجاه عقارب الساعة ، فإن النتيجة ستكون صحيحة ، ولكن سلبيًا - لذلك ، يتم إعطاء معامل مستوى الصوت للعائد).

هذا بسيط للغاية لتحقيقه - خذ مثلثًا (النقاط a1 و a2 و a3) وابحث عن جيرانها وسرد رأسين متطابقين بالترتيب العكسي (على سبيل المثال ، مثل هذا: a2 و a1 و b1).
اتضح شيء مثل هذا:

الآن ، إذا عرضنا مثلثًا على المستوى xy ، فإن ترتيب اجتياز الإسقاط للمثلث "العلوي" سيتزامن مع المثلث المحدد في البداية ، وسيغير ترتيب التقاطع لإسقاط المثلث "السفلي" اتجاهه. نتيجةً لذلك ، ستقوم بتغيير علامة ومساحة هذا المثلث ، ويتم حسابها بواسطة صيغة Gauss. هنا ، المثلث "السفلي" - مفهوم شرطي - يعني أن الحجم الموجود أسفله مباشرة غير مدرج في حجم متعدد السطوح. يمكن أن يكون المثلث "السفلي" لمتعدد السطوح غير المحدب أعلى من "العلوي".

بعد هذه الخطوات الأولية ، من أجل حساب إجمالي حجم متعدد السطوح ، تحتاج فقط إلى إضافة (مع الأخذ في الاعتبار علامة ، والتي يتم الحصول عليها في حد ذاته) جميع مجلدات من المنشور اقتطاع جمعها من وجوه وتوقعات هذه الوجوه على متن الطائرة س ص. وتعتبر أحجام المنشور نتاجًا للمنطقة (غوسية ، مع وجود إشارة) والحساب المتوسط للإحداثي z لرؤوس المثلث.

إذا كان التقاطع المتعدد السطوح يتقاطع مع المستوى xy ، فعند حساب الحجم ، ستلغي كل العلامات بعضها البعض وتبقى النتيجة صحيحة (تحتاج فقط إلى أخذ ارتفاعات المنشور بدون وحدة نمطية).

(على نحو ما يبدو المنشور "العلوي" المقطوع)

مع البحث عن مركز الكتلة ، كل شيء هو نفسه تقريبا. وبالمثل ، نحن بحاجة إلى إيجاد مراكز الكتلة لكل منشور مقطوع وتلخيص الإحداثي بالتنسيق ، مضروبا في حجم المنشور (من المفترض أن الكتلة موزعة بالتساوي في جميع أنحاء المجلد ويمكن استبدال واحد بآخر). للعثور على مركز كتلة المنشور المقطوع ، من الضروري حساب مراكز كتلة اثنين من رباعي الاسطح (دالة +1) ومنشور عادي واحد. الخوارزمية أيضًا "لا تتدهور" إذا كان متعدد السطوح يعبر المستوى xy (وهنا يمكن أن يكون نسخة من Magritte).

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

الرمز الذي يعد هذا وذاك:

رمز أكثر قليلا

 def RecSetDirsTriangles(para, Connects, TR): #1.   , ,     for i in range(0,len(Connects)): if i != para[0] and i != para[1] and Connects[i][para[0]] and Connects[i][para[1]]: #  ! fl = 1 for T in TR: if i in T and para[1] in T and para[0] in T: fl = 0 break if fl: # ! TR += [(para[1],para[0],i)] Recc((para[0], i) , Connects, TR) Recc((i, para[1]) , Connects, TR) def TetrV(mas):#dot1, dot2, dot3, dot4): """   """ M = np.zeros((3,3),float) for i in range(1,4): for j in range(0,3): M[i-1][j] = mas[i][j] - mas[0][j] #print(M) return math.fabs(np.linalg.det(M)/6) def FindVandCM(dots, Connects): """     """ #1.      TR = [] for i in range(1,len(Connects)): #        - if Connects[i][0]: for j in range(i+1, len(Connects)): if Connects[0][j] and Connects[i][j]: TR += [(0,i,j)] break RecSetDirsTriangles((0,i),Connects, TR) break print(" : ", len(TR)) #2.   ,          V = 0 CM = [0, 0, 0] for T in TR: ''' : x1y2 x2y3 x3y1 x2y1 x3y2 x1y3''' S = 0.5 * (dots[T[0]][0]*dots[T[1]][1] + dots[T[1]][0]*dots[T[2]][1] + dots[T[2]][0]*dots[T[0]][1] - dots[T[1]][0]*dots[T[0]][1] - dots[T[2]][0]*dots[T[1]][1] - dots[T[0]][0]*dots[T[2]][1]) #S   +  -    ,    V += S*(dots[T[0]][2] + dots[T[1]][2] + dots[T[2]][2])/3 #    ... #c        c1 = ((dots[T[0]][0] + dots[T[1]][0] + dots[T[2]][0])/3, (dots[T[0]][1]+ dots[T[1]][1]+ dots[T[2]][1])/3) #    hm = min([dots[T[0]][2] , dots[T[1]][2] , dots[T[2]][2]]) hM = max([dots[T[0]][2] , dots[T[1]][2] , dots[T[2]][2]]) indM = [dots[T[0]][2] , dots[T[1]][2] , dots[T[2]][2]].index(hM) indm = [dots[T[0]][2] , dots[T[1]][2] , dots[T[2]][2]].index(hm) V3 = S * hm if indM == indm: # ! CM[0] += V3*c1[0] CM[1] += V3*c1[1] CM[2] += V3*hm/2 continue L = [0,1,2] L.remove(indM) L.remove(indm) indmidle = L[0] dots1 = [dots[T[0]], dots[T[1]], dots[T[2]], (dots[T[indM]][0], dots[T[indM]][1] , hm)] #  V1 = TetrV(dots1) if S < 0: V1 = -V1 V2 = S * ( dots[T[indmidle]][2] - hm)/3 #V3 = S * hm CM[0] += V1*((dots[T[0]][0] + dots[T[1]][0] + dots[T[2]][0] + dots[T[indM]][0])/4) + V2*((dots[T[0]][0] + dots[T[1]][0] + dots[T[2]][0] + dots[T[indmidle]][0])/4) + V3*c1[0] CM[1] += V1*((dots[T[0]][1] + dots[T[1]][1] + dots[T[2]][1] + dots[T[indM]][1])/4) + V2*((dots[T[0]][1] + dots[T[1]][1] + dots[T[2]][1] + dots[T[indmidle]][1])/4) + V3*c1[1] CM[2] += V1*((dots[T[0]][2] + dots[T[1]][2] + dots[T[2]][2] + hm)/4) + V2*((dots[T[0]][2] + dots[T[1]][2] + dots[T[2]][2] + hm)/4) + V3*hm/2 CM[0] = CM[0]/V CM[1] = CM[1]/V CM[2] = CM[2]/V return (math.fabs(V), CM)

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

(احزر الفيلم!)

خوارزميات للبحث في حجم ووسط كتلة متعدد السطوح

More articles: