كيف تخبر ما إذا كان الخط يتقاطع مضلعا في C #؟

Question

لدي سؤال مشابه جدا لهذا:

كيف تعرف ما إذا كان الخط يتقاطع طائرة في C #؟

أنا أبحث عن طريقة (في C #) التي تخبر ما إذا كان السطر يتقاطع مضلع تعسفي.

اعتقد ان خوارزمية كريس ماراستي جورج كان مفيدا للغاية، ولكن في عداد المفقودين الطريقة الأكثر أهمية، أي خط إلى تقاطع الخط.

هل أي شخص يعرف طريقة تقاطع الخط لإكمال رمز كريس ماراستي جورج أو لديك أي شيء مماثل؟

هل يوجد رمز مدمج لهذا في C #؟

هذه الطريقة هي للاستخدام مع خوارزمية خرائط Bing المحسنة مع ميزة منطقة ممنوعة. يجب ألا يمر المسار الناتج عبر المنطقة المحرمة (المضلع التعسفي).

Answer 1

لا يوجد رمز مدمج للكشف عن الحافة المضمنة في .NET Framework.

هنا رمز (تم نقله إلى C #) الذي يفعل ما تحتاجه (تم العثور على الخوارزمية الفعلية في comp.graphics.algorithms على مجموعات Google):

public static PointF FindLineIntersection(PointF start1, PointF end1, PointF start2, PointF end2)
{
    float denom = ((end1.X - start1.X) * (end2.Y - start2.Y)) - ((end1.Y - start1.Y) * (end2.X - start2.X));

    //  AB & CD are parallel 
    if (denom == 0)
        return PointF.Empty;

    float numer = ((start1.Y - start2.Y) * (end2.X - start2.X)) - ((start1.X - start2.X) * (end2.Y - start2.Y));

    float r = numer / denom;

    float numer2 = ((start1.Y - start2.Y) * (end1.X - start1.X)) - ((start1.X - start2.X) * (end1.Y - start1.Y));

    float s = numer2 / denom;

    if ((r < 0 || r > 1) || (s < 0 || s > 1))
        return PointF.Empty;

    // Find intersection point
    PointF result = new PointF();
    result.X = start1.X + (r * (end1.X - start1.X));
    result.Y = start1.Y + (r * (end1.Y - start1.Y));

    return result;
 }

Answer 2

قليلا خارج الموضوع، ولكن إذا كان الخط لانهائي أعتقد أن هناك حل أبسط بكثير:

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

بمساعدة من هذين:

• باستخدام LinQ أو غير ذلك، كيف تحقق ما إذا كانت جميع العناصر القائمة لها نفس القيمة وإرجاعها، أو إرجاع "الآخر" إذا لم يفعلوا ذلك؟
• تحديد أي جانب من خط يكمن النقطة

حصلت على هذه الجوهرة الصغيرة:

  public class PointsAndLines
  {
    public static bool IsOutside(Point lineP1, Point lineP2, IEnumerable<Point> region)
    {
      if (region == null || !region.Any()) return true;
      var side = GetSide(lineP1, lineP2, region.First());
      return
        side == 0
        ? false
        : region.All(x => GetSide(lineP1, lineP2, x) == side);
    }

    public static int GetSide(Point lineP1, Point lineP2, Point queryP)
    {
      return Math.Sign((lineP2.X - lineP1.X) * (queryP.Y - lineP1.Y) - (lineP2.Y - lineP1.Y) * (queryP.X - lineP1.X));
    }
  }

Answer 3

للكشف عن التصادمات بين مضلعات في مشروع خريطة Silverlight لدينا، نحن نستخدم مكتبة المقصية:

مجانا للاستخدام التجاري، وحجم صغير، وأداء كبير وسهل الاستخدام للغاية.

clipper webpage.

Answer 4

يبدو أن هذه المقالة ستساعد

http://www.codeproject.com/kb/recipes/2dpolyclip.aspx.

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