حساب الاتحاد من شكلين تعسفي

Question

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

يتم تخزين الأشكال كتسلسل من النقاط بطريقة عقارب الساعة.

من الناحية المثالية ، أود خوارزمية ستستغرق صفيفتين من النقاط (x ، y) وإرجاع مجموعة واحدة من الشكل الناتج.

لقد قرأت ويكيبيديا العمليات المنطقية على المضلعات الذي يذكر خوارزمية خط المسح لكن لا يمكنني صنع العلاقة بين هذا وهدفي ، للأسف أنا لست عالم رياضيات.

أقوم بتطوير التطبيق في ActionScript 3 ، لكنني على دراية بـ C#و Java ويمكنني اختيار طريقي عبر C و C ++.

Answer 1

تنفيذ العمليات المنطقية بشكل صحيح ليس تافهة ؛ لحسن الحظ ، هناك مكتبات تنفذ هذه الوظيفة بالفعل.

اي لغة تستخدم؟ إذا كان C ++ ، ألق نظرة على cgal, ، مكتبة خوارزميات الهندسة الحسابية.

Answer 2

بالنظر إلى قائمتين من النقاط (أ و ب)
- [1] لكل سطر في A هل يتقاطع مع خط في ب
-.- [2] إذا لم تتقاطع خطوط (أكثر)
-.- [3] إذا كان خط في (أ) يتقاطع مع خط في B ثم
-.-.- [4] أضف نقطة التقاطع إلى الإخراج
-
-.-.-.- [6] إذا لم يكن الأمر
-

انظر أيضا نقطة التقاطع لخطين. لن أكتب الرمز آسف :)

Answer 3

أنظر أيضا GPC.

Answer 4

سيكون هذه الخوارزمية اعمل لاجلك؟

Answer 5

ماذا عن:

1. اختر النقطة اليسرى من الشكلين. نسمي هذا الشكل A وجعله الشكل الحالي.
2. الرياح في اتجاه عقارب الساعة على طول الشكل الحالي إلى النقطة التالية وتحقق لمعرفة ما إذا كان خط خط واحد أو أكثر يتقاطع.
   • في حالة تقاطع أي خطوط ، ابحث عن نقطة التقاطع الأولى وأضف ذلك إلى شكلك الجديد. التبديل إلى اللف على طول الشكل الآخر.
   • إذا لم تتقاطع أي خطوط إلى النقطة التالية في الشكل A وأضف ذلك كنقطة في شكلك الجديد. استمر في الارتفاع على طول الشكل الحالي.
3. كرر الخطوة 2.

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

أنا متأكد من أن هناك الكثير من التحسينات التي يمكنك إضافتها بمجرد أن تعمل الأساسيات.

Answer 6

يبدو أن هناك أيضًا واجهة برمجة تطبيقات JavaScript:

https://github.com/bjornharrtell/jsts/

الذي يبدو أنه ينفذ معيار JTS وله عدة تطبيقات مختلفة:

http://tsusiatsoftware.net/jts/jts-links.html#ports

كلهم يجب أن يكونوا قادرين على أداء الاتحاد وما إلى ذلك:

http://tsusiatsoftware.net/jts/jtsuser/contents.html

لكن CSG.JS هو المشروع الأكثر إثارة للإعجاب IMO

https://github.com/evanw/csg.js