تحديد ما إذا كان تنسيق موجود داخل المضلع

Question

أنا أعمل على مفتوح المصدر تتبع geofence تطبيق البرمجيات وأنا أعاني من صعوبة في معرفة الرياضيات بالنسبة geofencing.

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

بحثي يقول أن أسهل طريقة هي أن تأخذ وجهة نظري (التي سأتصل x) و نقطة خارج المضلع (نسميها y) وتحديد ما إذا كان خط ((xx xy), (yx ، yy)) يتقاطع مع مضلع حدود.إذا كان يتقاطع مع عدد فردي من المرات, نقطة x يجب أن يكون داخل المضلع.

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

محل تقدير كبير.

Answer 1

انظر هنا

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

HTH

تحرير هناك آخر لذلك السؤال الذي يتعلق في هذه المسألة التي يمكن العثور عليها هنا

Answer 2

ومفتاح واحد هنا هو أن ندرك أن أنت حر في اختيار أي نقطة Y التي تريد. وهناك خيار لطيف هو نقطة (س س، -infinity). وبعبارة أخرى، فإن نقطة بانخفاض مباشرة من وجهة المعنية وبلا حدود بعيدة. الآن يصبح السؤال: كم من حواف المضلع عبور الإحداثي X أدناه نقطة في السؤال. وذلك فقط أجزاء الخط التي تنتشر على X تنسيق الحاجة إلى النظر فيها.

إذا وجهة نظرك هي P = (س، ص)، ونقطة نهاية الجزء هي P1 = (X1، Y1) وP2 = (X2، Y2) ذ تنسيق الجزء الذي يعبر تعطى x بواسطة سي = (خ-X1) * (Y2-Y1) / (X2-X1) + Y1

ومعرفة ما اذا كان سي <ص (إلا إذا X1 <س

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

Answer 3

وجوستين،

وأنت قد تحتاج أيضا إلى تحديد أفضل "خارج المضلع" لبناء القطاع.

وخذ دقيقة والحد الأقصى من كل س و ص الإحداثيات وبناء مستطيل (xmin، ymin)، (xmax، ymin)، (xmax، ymax)، (xmin، ymax). إن أي نقطة خارج المستطيل سيكون بالتأكيد خارج المضلع - ثم تابع كما أظهرت الآخرين أعلاه. ويعرف كل جزء المضلع والخط شيدت من قبل ذ المعادلة = الفأس + ب، ولكل قطاع، وXLO نطاق وxhi. خط شيدت الخاص بك إما يعبر شريحة في مجموعة أم لا. وهذا هو، في حل المعادلات في وقت واحد اثنين في نطاق الشريحة إما موجودا أم لا. الاعتماد فقط على عدد من الحلول الموجودة للحصول على عدد من التقاطعات.

Answer 4

سوف نفترض أنك في طائرة (2D).

• حساب المنحدرات من كل جانب (في بعض تنسيق النظام) المنحدر من خط من النقطة X إلى النقطة Y (خط XY).
• على جميع الاطراف حيث المنحدر لا يساوي المنحدر من XY ، وحساب نقطة تقاطع.
• من أجل كل نقطة ، تحديد ما إذا كانت نقطة التقاطع على الخط الجزء XY و شريحة خط تحديد الجانب.إن تجاوز هذا الجانب.(راجع إحداثيات التقاطع ومعرفة ما إذا كان كل من x و y هي المكونات المدرجة في مجموعة من القيم لكل شريحة خط.)
• لعد عدد من المعابر لديك الإجابة.

Answer 5

لف عدد المضلع وهذه النقطة.

Answer 6

وجرب هذا،

public static bool PointinPolygon( Point[] points, Point p )
    {
        bool result = false;

        for( int i = 0; i < points.Length - 1; i++ )
        {
            if( ( ( ( points[ i + 1 ].Y <= p.Y ) && ( p.Y < points[ i ].Y ) ) || ( ( points[ i ].Y <= p.Y ) && ( p.Y < points[ i + 1 ].Y ) ) ) && ( p.X < ( points[ i ].X - points[ i + 1 ].X ) * ( p.Y - points[ i + 1 ].Y ) / ( points[ i ].Y - points[ i + 1 ].Y ) + points[ i + 1 ].X ) )
            {
                result = !result;
            }
        }
        return result;
    }