كيفية تقاطع اثنين من المضلعات؟

Question

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

مدخل: 2 مضلعات (A و B) في 2D، نظرا كقائمة من الحواف [(x0, y0, x1, y2), ...] كل. يتم تمثيل النقاط أزواج من doubleس. لا أعرف إذا أعطيت في اتجاه عقارب الساعة أو في اتجاه عقارب الساعة أو في أي اتجاه على الإطلاق. أنا فعل تعرف أنها ليست بالضرورة محدب.

انتاج |: 3 مضلعات تمثل A، B و Bustersecting Polygon AB. أي منها قد يكون مضلع فارغا (؟)، على سبيل المثال null.

تلميح لتحسين: تمثل هذه المضلعات من حدود الغرفة والأرضيات. لذلك فإن حدود الغرفة ستتقاطع بشكل كامل مع حدود الأرضية، ما لم تنتمي إلى أرضية أخرى على نفس الطائرة (Argh!).

أنا من الأمل أن يكون شخص ما قد فعل ذلك بالفعل في C # وسوف اسمحوا لي أن أستخدم استراتيجية / رمز الخاصة بهم، لأن ما وجدته حتى الآن في هذه المشكلة أمر شحمي إلى حد ما.

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

انتاج |: أول مضلع ناقص جميع البتات المتقاطعة، بوليجل تقاطع (الجمع على ما يرام). أنا لست مهتما حقا في المضلع الثاني، فقط تقاطعها مع الأول.

Edit2.: أنا حاليا باستخدام GPC (مجز مضلع عام) المكتبة التي تجعل هذا أمر سهل حقا!

Answer 1

ما أعتقد أنه يجب عليك القيام به

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

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

http://www.cs.man.ac.uk/~toby/gpc/

ما فعلته بالفعل هو استخدام خوارزمية مقطوعة تقاطع المضلع التي تعد جزءا من مكتبات Java2D. ربما يمكنك العثور على شيء مشابه في مكتبات MS الخاصة ب C # لاستخدامها.

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

بمجرد أن تكون لديك بالفعل مكتبة لقطة مضلع، تحتاج فقط إلى طرح مضلع Poygon B من المضلع A للحصول على أول قطعة من الإخراج، وتقاطع المضلعات A و B للحصول على القطعة الثانية من الإخراج.

كيفية لفة الخاصة بك، بالنسبة للمظير اليأس

عندما كنت أفكر في تدحرج بلدي، وجدت خوارزمية Weiler-Atherton أن يكون لديك أقصى إمكانات لقطع المضلع العام. استخدمت ما يلي كمرجع:

http://cs1.bradley.edu/public/jcm/weileratherton.html.

http://en.wikipedia.org/wiki/weiler-atherton.

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

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

Answer 2

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

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

Answer 3

إذا كنت برمجة في .NET Framework، فقد ترغب في إلقاء نظرة على فئة SQLGeometry متوفرة في .NET تجميعات شحنها Microsoft SQL Server System Clr أنواع

توفر فئة SQLGeometry stintersection. طريقة

SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))");
SqlGeometry intersection = g1.STIntersection(g2);

Answer 4

قد ترغب أيضا في إلقاء نظرة على nettopologysuite. أو حتى حاول استيرادها إلى SQL Server 2008 وأدوات مكانية.

Answer 5

يتم وصف مضلع بالكامل من قبل قائمة من النقاط المطلوبة (P1، P2، ...، PN). الحواف هي (P1 - P2)، (P2 - P3)، ...، (PN - P1). إذا كان لديك مضلان A و B يتداخلان، فستكون هناك نقطة (من القائمة الموجودة في النقاط التي تصف المضلع أ) والتي تكمن داخل المنطقة المحاطة بالقليم ب أو العكس بالعكس (نقطة B). إذا لم يتم العثور على هذه النقطة، فلن تتداخل المضلعات. إذا تم العثور على هذه النقطة (أي AI) تحقق من النقاط المجاورة للضغط A (I-1) و A (I + 1). كرر حتى تجد نقطة خارج المنطقة أو يتم فحص جميع النقاط (ثم الأكاذيب الأول المضلع بالكامل داخل المضلع الثاني). إذا وجدت نقطة خارج، يمكنك حساب نقطة العبور. ابحث عن الحافة المقابلة من المضلع B واتبعها مع أدوار ظاهرية = الآن تحقق مما إذا كانت نقاط المضلع B تكمن داخل المضلع A. وبهذه الطريقة يمكنك بناء قائمة من النقاط التي تصف المضلع المتداخلة. إذا لزم الأمر، يجب عليك التحقق مما إذا كانت المضلعات متطابقة، (P1، P2، P3) === (P2، P3، P1).

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

أصيب

Answer 6

حاول استخدام أدوات نظم المعلومات الجغرافية لذلك، مثل ArcoBjects، Topologysuite، GEOS، OGR، إلخ. لست متأكدا مما إذا كانت جميع هذه التوزيعات متواصلة إلى .NET، لكنهم جميعا يفعلون نفس الشيء.

Answer 7

المقص هو فتح المصدر مجانا مكتبة القطع المضلع (مكتوبة في دلفي و C ++) التي تفعل بالضبط ما تسأل - http://sourceforge.net/projects/polyclipping/

في الاختبارات الخاصة بي، يكون المقص أسرع بكثير وأقل عرضة للخطأ للخطأ من GPC (انظر المزيد من المقارنات التفصيلية هنا - http://www.angusj.com/delphi/clipper.php#features.). أيضا، في حين أن هناك رمز مصدر لكل من Delphi و C ++، تتضمن مكتبة Clipper أيضا DLL مجمعة لجعلها سهلة الاستخدام للغاية في استخدام وظائف القص في لغات أخرى (Windows) أيضا.

Answer 8

هذه ورقة الأكاديمية يشرح كيفية القيام بذلك.

Answer 9

إذا كنت تجرؤ على إلقاء نظرة على رمز GPL C ++ GPL C ++ الآخرين، فيمكنك أن ترى كيف يفعلون ذلك في Inkscape:

http://bazaar.launchpad.net/~inkscape.dev/inkcape/trunk/view/head :/src/2geom/shape.cpp. (خط 126)