كيف يمكنني تحديد ما إذا كانت سلسلة من النقاط (أو المضلع) ضمن منطقة مستطيلة؟

Question

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

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

لا أستطيع ببساطة اختبار كل نقطة لمعرفة ما إذا كان يكمن في المنطقة الرأي. من الممكن أن يمر قطعة من خلال المنطقة دون أي نقطة داخل المنطقة (أي يتم رسم الخط عبر المنطقة).

هنا مثال على ما أريد تحديده (يعني أن الوظيفة يجب أن تعود الوظيفة صحيحة لمجموعة النقاط، يعني اللون الأزرق أنه يجب أن يعود False، مثال يستخدم خطوط مستقيمة واستطيلات لأنني لست فنانا).

هنا هو مثالا توضيح نفاد البادنة (لا يحتوي المستطيل الأحمر على قمة واحدة أو شريحة حدودية تمر عبر المنطقة التي تظهر على الشاشة، ولكن لا يزال ينبغي النظر في الشاشة):

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

كما هو الحال دائما، شكرا لك مقدما على أي مساعدة أو اقتراحات.

PS لدي وظيفة لتحديد تقاطع الخط، ولكن يبدو وكأنه مبالغ فيه لاستخدامه لمقارنة كل قطعة على كل جانب من جانب المنطقة على الشاشة لأن المنطقة على الشاشة هي دائما عادي [0، 0، العرض ارتفاع] المستطيل. ليس هناك نوع من القص القصيرة؟

Answer 1

ps لدي وظيفة لتحديد تقاطع الخط، ولكن يبدو overkill لاستخدامها لمقارنة كل منها الجزء على كل جانب من الشاشة المنطقة لأن المنطقة التي تظهر على الشاشة دائما عادي [0، 0، العرض، الارتفاع] مستطيل.ليس هناك نوع من قصيرة قطع؟

ليست مبالغة، و neccessary هنا.النوع الوحيد من الاختصار الذي يمكنني التفكير فيه هو قيم المخادين [0، 0، العرض، الارتفاع] في هذه الوظيفة وتبسيطه قليلا.

Answer 2

ما تبحث عنه هو باسم خوارزمية كشف التصادم سيقود بحث Googleإلى الكثير من التطبيقات بلغة مختلفة وكذلك الكثير من النظرية

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

قراءة جيدة