Multiple line segment intersection
کمپیوٹیشنل جیومیٹری میں، ایک سے زیادہ لائن سیگمنٹ انٹرسیکشن کا مسئلہ یوکلڈین پلین میں لائن سیگمنٹس کی ایک فہرست فراہم کرتا ہے اور پوچھتا ہے کہ کیا ان میں سے کوئی دو انٹرسیکٹ (کراس) کرتے ہیں۔ سادہ الگورتھم حصوں کے ہر جوڑے کی جانچ کرتے ہیں۔ تاہم، اگر ممکنہ طور پر ایک دوسرے کو عبور کرنے والے حصوں کی ایک بڑی تعداد کو چیک کرنا ہے، تو یہ تیزی سے غیر موثر ہو جاتا ہے کیونکہ حصوں کے زیادہ تر جوڑے ایک عام ان پٹ ترتیب میں ایک دوسرے کے قریب نہیں ہوتے ہیں۔ زیادہ تعداد میں حصوں کے لیے اس مسئلے کو حل کرنے کا سب سے عام، اور زیادہ موثر طریقہ سویپ لائن الگورتھم کا استعمال کرنا ہے، جہاں ہم لائن کے حصوں میں ایک لکیر کے پھسلنے کا تصور کرتے ہیں اور ہم ٹریک کرتے ہیں کہ یہ بائنری سرچ ٹریز پر مبنی متحرک ڈیٹا ڈھانچے کا استعمال کرتے ہوئے ہر وقت کون سے لائن کے حصوں کو کاٹتا ہے۔ شاموس-ہوئی الگورتھم اس اصول کو لائن سیگمنٹ انٹرسیکشن کا پتہ لگانے کے مسئلے کو حل کرنے کے لیے لاگو کرتا ہے، جیسا کہ اوپر بیان کیا گیا ہے، اس بات کا تعین کرنے کے لیے کہ لائن سیگمنٹس کے سیٹ میں انٹرسیکشن ہے یا نہیں۔ بینٹلے-اوٹمین الگورتھم اسی اصول کے مطابق کام کرتا ہے تاکہ تمام انٹرسیکشنز کو لوگرتھمک ٹائم فی انٹرسیکشن میں درج کیا جا سکے۔ Bentley-Ottmann الگورتھم حوالہ جات مزید پڑھنا باب 2: لائن سیگمنٹ انٹرسیکشن، پی پی۔ 19-44 بھی دیکھیں۔ تھامس ایچ کورمین، چارلس ای لیسرسن، رونالڈ ایل ریویسٹ، اور کلفورڈ اسٹین۔ الگورتھم کا تعارف، دوسرا ایڈیشن۔ ایم آئی ٹی پریس اور میک گرا ہل، 1990۔ سیکشن 33.2: اس بات کا تعین کرنا کہ آیا حصوں کا کوئی جوڑا ایک دوسرے کو کاٹتا ہے، پی پی۔ 934-947۔ جے۔ ایل۔ بینٹلے اور ٹی۔ Ottmann.، جیومیٹرک چوراہوں کی رپورٹنگ اور گنتی کے لیے الگورتھم، IEEE ٹرانس۔ کمپیوٹنگ۔ C28 (1979)، 643-647۔ بیرونی روابط لائنوں اور طیاروں کے انٹرسیکشنز الگورتھم اور نمونہ کوڈ بذریعہ ڈین سنڈے رابرٹ پلیز۔ لیکچر 4 نوٹ۔ سینٹ لوئس میں واشنگٹن یونیورسٹی، CS 506: کمپیوٹیشنل جیومیٹری (کیش شدہ کاپی)۔ سی جی اے ایل میں لائن سیگمنٹ انٹرسیکشن، کمپیوٹیشنل جیومیٹری الگورتھم لائبریری "لائن سیگمنٹ انٹرسیکشن" لیکچر جیف ایرکسن کے نوٹ۔ سی کوڈ کے ساتھ لائن لائن انٹرسیکشن کا طریقہ نمونہ ڈیرل ریکس فنلی جیومیٹرک الگورتھم جیومیٹرک انٹرسیکشن کمپیوٹیشنل جیومیٹری