بستهاین سوال دستورالعمل های سرریز پشته را برآورده نمی کند. در حال حاضر پاسخ ها را قبول نمی کند.

به نظر نمی رسد که این سوال در مورد برنامه نویسی در محدوده تعریف شده در مرکز کمک باشد. 6 سال پیش بسته شد.

قفل شدهاین سؤال و پاسخ های آن قفل شده است زیرا سوال خارج از موضوع است اما از اهمیت تاریخی برخوردار است. در حال حاضر پاسخ ها یا تعامل های جدید را نمی پذیرد.

چگونه می توانم تعیین کنم که آیا دو خط با هم تلاقی می کنند یا خیر ، و اگر این کار را انجام دهند ، در چه نقطه x ، y؟ کاربر 3956566 از 18 فوریه 2009 در 22:47 پرسید Kingnestor Kingnestor 65K 51 51 نشان طلا 121 121 نشان نقره 152 152 نشان های برنز

این ممکن است به جای چند ضلعی کامل ، از لبه های مستطیل به عنوان خطوط جداگانه فکر کند.

18 فوریه 2009 در 22:53 نظرات غیرفعال شده در پست های حذف شده / قفل شده / بررسی |

27 پاسخ 27

مرتب شده توسط: تنظیم مجدد به طور پیش فرض رای

یک رویکرد خوب برای این مشکل وجود دارد که از محصولات صلیب وکتور استفاده می کند. محصول متقاطع بردار 2 بعدی V × W را تعریف کنید تا V باشد_xحرف_y- v_yحرف_x.

فرض کنید دو بخش خط از P تا P + R و از Q تا Q + S اجرا شود. سپس هر نقطه در خط اول به عنوان P + T R (برای یک پارامتر مقیاس T) و هر نقطه در خط دوم به عنوان Q + U S (برای یک پارامتر مقیاس U) نشان داده شده است.

اگر بتوانیم t و u را به گونه ای پیدا کنیم که:

P + t r = q + u s

عبور از هر دو طرف با S ، گرفتن

(p + t r) × s = (q + u s) × s

و از آنجا که s × s = 0 ، این به معنی است

t (r × s) = (q - p) × s

و بنابراین ، حل برای t:

t = (q - p) × s / (r × s)

به همین روش ، ما می توانیم برای U حل کنیم:

(p + t r) × r = (q + u s) × r

u (s × r) = (p - q) × r

u = (p - q) × r / (s × r)

برای کاهش تعداد مراحل محاسبات ، بازنویسی این موضوع به شرح زیر است (به یاد داشته باشید که s × r = - r × s):

u = (q - p) × r / (r × s)

اکنون چهار مورد وجود دارد:

1. اگر r × s = 0 و (q - p) × r = 0 ، سپس دو خط با خطی هستند. در این حالت ، نقاط پایانی بخش دوم (Q و Q + S) را از نظر معادله بخش خط اول (P + T R) بیان کنید:

    

حرف₀= (q - p) · r / (r · r) t₁= (q + s - p) · r / (r · r) = t₀+ s · r / (r · r)

اعتبار: این روش تخصص دو بعدی الگوریتم تقاطع خطوط سه بعدی از مقاله "تقاطع دو خط در سه فضا" نوشته رونالد گلدمن است که در Graphics Gems صفحه 304 منتشر شده است. در سه بعدی حالت معمول این است کهخطوط چوله هستند (نه موازی و نه متقاطع) در این صورت روش نزدیکترین نقاط دو خط را نشان می دهد.

پاسخ داده شده در 19 فوریه 2009 در 13:24 گرت ریس گرت ریس 64. 4k 9 9 نشان طلا 132 132 نشان نقره 162 162 نشان برنز

@myrkos: خیر. پاره خط اول «از p تا p + r» اجرا می شود، بنابراین وقتی در شرایط پارامتری به صورت «p + tr» نمایش داده می شود، آن پاره با 0 ≤ t ≤ 1 مطابقت دارد. به طور مشابه برای بخش دیگر.

ژانویه 31, 2012 در 17:48

گرت، احساس می کنم باید چیزی را از دست بدهم، اما چگونه می توان (بردار) را بر بردار تقسیم کرد؟راه حل های شما برای t و u به / (r × s) ختم می شود، اما (r×s) یک بردار است، درست است؟یک بردار (0، 0، rx * sy - ry * sx). و سمت چپ به طور مشابه بردار موازی با محور z است. بنابراین. آیا فقط جزء z را بر مولفه z دیگر تقسیم کنم؟آیا فرمول t در واقع |(q − p) × s| است/ |(r × s)|?

اوت 31, 2012 در 3:40 @LarsH: پاراگراف اول را ببینید. اوت 31, 2012 در 8:15

برای کسانی که علاقه مند هستند، در اینجا یک پیاده سازی C# ساده وجود دارد، با گرفتن مختصات شروع و پایان PointF برای خطوط، که به نظر می رسد کار می کند: ideone. com/PnPJgb

دسامبر 17, 2012 در 0:42

من پیاده سازی جاوا اسکریپت را به دنبال @Matt قرار دادم. من اشتباهاتی را که تکیتو به آنها اشاره کرده بود اصلاح کردم.

اوت 29, 2013 در 4:10 رای

FWIW، تابع زیر (در C) هم تقاطع خطوط را تشخیص می دهد و هم نقطه تقاطع را تعیین می کند. این بر اساس یک الگوریتم در "ترفندهای مربیان برنامه نویسی بازی ویندوز" آندره لموث است. این بی شباهت به برخی از الگوریتم های موجود در پاسخ های دیگر (مثلاً گرث) نیست. سپس LeMothe از قانون کرامر (از من نپرس) برای حل خود معادلات استفاده می کند.

من می توانم تأیید کنم که در شبیه سازی سیارک های ضعیف من کار می کند و به نظر می رسد که به درستی با موارد لبه ای که در پاسخ های دیگر توسط Elemental، Dan و Wodzu توضیح داده شده است، برخورد می کند. همچنین احتمالاً سریعتر از کد ارسال شده توسط KingNestor است زیرا همه آن ضرب و تقسیم است، بدون ریشه مربع!

حدس می زنم مقداری پتانسیل برای تقسیم بر صفر در آنجا وجود دارد، اگرچه در مورد من مشکلی وجود ندارد. به اندازه کافی آسان برای تغییر برای جلوگیری از تصادف به هر حال.

// اگر خطوط در تقاطع باشند ، 1 را برمی گرداند ، در غیر این صورت 0. علاوه بر این ، اگر خطوط // از نقطه تقاطع تقاطع می کنند ممکن است در شناورها I_X و I_Y ذخیره شوند. char get_line_intersection (float p0_x ، float p0_y ، float p1_x ، float p1_y ، float p2_x ، float p2_y ، float p3_x ، float p3_y ، float *i_x ، float *i_y)= 0 && s = 0 && t retu 0; // No collision> 

BTW ، باید بگویم که در کتاب Lemothe ، اگرچه او ظاهراً الگوریتم را به درستی دریافت می کند ، نمونه بارز او به شماره های اشتباه وصل می کند و محاسبات را اشتباه می کند. مثلا:

که ساعت ها مرا گیج کرد.:(

1 1 1 نشان نقره ای در 28 دسامبر 2009 در 7:16 پاسخ داد گاوین گاوین 9،787 7 7 نشان های طلا 48 48 نشان نقره 61 61 نشان برنز

تابع GetLineIntersection (P0_X ، P0_Y ، P1_X ، P1_Y ، P2_X ، P2_Y ، P3_X ، P3_Y) 19 دسامبر 2012 در 15:27 if (s>= 0 && s<= 1 && t>= 0 && t<= 1) retu null; // No collision> 19 دسامبر 2012 در 15:28

الگوریتم خوب ، با این حال FYI مواردی را که تعیین کننده 0 است ، کنترل نمی کند (-S2_X * S1_Y + S1_X * S2_Y در بالا). اگر 0 (یا نزدیک 0) باشد ، خطوط موازی یا خطی هستند. اگر خطی باشد ، تقاطع ممکن است یک بخش خط دیگر باشد.

5 ژوئیه 2013 در 22:56

از دو عمل تقسیم می توان برای سرعت جلوگیری کرد (تقسیم هزینه بیشتر از ضرب). اگر خطوط از هم جدا می شوند ، به یک بخش نیاز دارید ، اگر آنها از هم جدا نشوند ، به صفر نیاز دارید. ابتدا باید مخرج را محاسبه کرده و در صورت صفر متوقف شود (احتمالاً اضافه کردن کد برای تشخیص کالری بودن.) در مرحله بعد ، به جای محاسبه مستقیم S و T ، رابطه بین دو عدد و مخرج را آزمایش کنید. فقط در صورت تأیید خطوط به تقاطع ، آیا در واقع نیاز به محاسبه مقدار T (اما نه S) دارید.

14 ژوئیه 2013 ساعت 17:02

من تست عملکرد را در تمام الگوریتم های ارسال شده در اینجا انجام دادم و این یکی حداقل دو برابر سریع هر یک از دیگران است. با تشکر از ارسال شما!

29 نوامبر 2013 در 21:20 رای

مشکل به این سؤال کاهش می یابد: آیا دو خط از A تا B و از C تا D تقاطع می کنند؟سپس می توانید چهار بار از آن سؤال کنید (بین خط و هر یک از چهار طرف مستطیل).

در اینجا ریاضی بردار برای انجام آن است. من فرض می کنم خط از A تا B خط مورد نظر است و خط از C تا D یکی از خطوط مستطیل است. نماد من این است که AX "هماهنگ X" است و CY "هماهنگ C C." استو " *" به معنای محصول DOT است ، بنابراین به عنوان مثالa*b = ax*bx + ay*توسط.

e = b-a = (bx-ax ، by-ay) f = d-c = (dx-cx ، dy-cy) p = (-ey ، ex) h = ((a-c) * p) / (f * p) 

این شماره H کلید است. اگر ساعت بین 0 تا 1 باشد ، خطوط با هم تلاقی می کنند ، در غیر این صورت آنها این کار را نمی کنند. اگر f*p صفر باشد ، البته شما نمی توانید محاسبه را انجام دهید ، اما در این حالت خطوط موازی هستند و بنابراین فقط در موارد آشکار تلاقی می کنند.

نقطه دقیق تقاطع C + F*H است.

سرگرم کننده بیشتر:

اگر H دقیقاً 0 یا 1 باشد ، خطوط در نقطه پایانی لمس می شوند. شما می توانید این را "تقاطع" در نظر بگیرید یا نه همانطور که می بینید مناسب است.

به طور خاص ، H این است که چقدر باید طول خط را ضرب کنید تا دقیقاً خط دیگر را لمس کنید.

استخراج:

A و C بردارهایی هستند که به شروع خط اشاره می کنند. E و F بردارهای انتهای A و C هستند که خط را تشکیل می دهند.

برای هر دو خط غیر موازی در هواپیما ، باید دقیقاً یک جفت مقیاس G و H وجود داشته باشد به گونه ای که این معادله دارای آن باشد:

a + e*g = c + f*h 

چرا؟از آنجا که دو خط غیر موازی باید از هم تقاطع کنند ، به این معنی که می توانید هر دو خط را با مقداری از هر مقدار مقیاس بندی کرده و یکدیگر را لمس کنید.

(در ابتدا این مانند یک معادله واحد با دو ناشناخته به نظر می رسد! اما وقتی در نظر بگیرید که این یک معادله بردار 2D است ، به این معنی که این واقعاً یک جفت معادله در x و y است.)

ما باید یکی از این متغیرها را از بین ببریم. یک راه آسان برای ساختن اصطلاح E صفر است. برای انجام این کار ، با استفاده از یک بردار که با E. به صفر می رسد ، آن بردار را که من در بالا به آن خوانده ام ، از محصول نقطه ای از هر دو طرف معادله استفاده کنید ، و من تحول آشکار E. را انجام دادم.

a*p = c*p + f*p*h (a-c)*p = (f*p)*h ((a-c)*p) / (f*p) = h 

22. 1k 32 32 نشان طلا 112 112 نشان نقره 129 129 نشان برنز در 18 فوریه 2009 در 23:09 پاسخ داد جیسون کوهن جیسون کوهن 80. 5k 26 26 نشان های طلا 107 107 نشان نقره 112 112 نشان های برنز

این الگوریتم خوب است. اما سوراخی در آن وجود دارد که توسط Dan @ stackoverflow. com/questions/563198/… و Elemental @ stackoverflow. com/questions/563198/tlet جالب خواهد بود ، اگر پاسخ خود را برای مرجع آینده به روز کنید ، جالب خواهد بود. با تشکر.

6 اکتبر 2009 در 1:45

آیا این الگوریتم از نظر عددی پایدار است؟من یک similliar aproach را امتحان کردم و معلوم شد که هنگام کار روی شناورها نتایج عجیب و غریب می دهد.

1 آگوست 2010 در 8:57

به نظر می رسد مشکل دیگری با این الگوریتم وجود دارد. هنگامی که آن را تغذیه می کند.<1, 0>b = c = d = ، اگرچه بخش های خط به وضوح در انتهای آن لمس می شوند ، f p (و همچنین e q ، مطابق با کاربر زیر ثابت) هر دو 0 هستند ، بنابراین باعث می شود که تقسیم 0 و G را پیدا کند. هنوز هم روی راه حل این راه حل کار می کنم ، اما فکر کردم مشکل ارزش اشاره دارد.

27 فوریه 2011 در 6:24 این پاسخ به سادگی نادرست است. سعی کنید a = ، b = ، c = d = 23 دسامبر 2012 ساعت 14:32

a + e*g = c + f*h دو خط تقاطع می کنند اگر و فقط اگر راه حل آن معادله (با فرض اینکه آنها موازی نیستند) ، هر دو ، g و h را بین 0 و 1 (بسته به اینکه باشد یا منحصر به فرد باشد ، دارد. شما در یک نقطه انتهایی لمس می کنید).

23 دسامبر 2012 ساعت 16:23 رای

من سعی کرده ام الگوریتم را که به طرز ظریف توسط جیسون در بالا توضیح داده شده است ، پیاده سازی کنم. متأسفانه هنگام کار با ریاضیات در اشکال زدایی ، موارد بسیاری را پیدا کردم که برای آن کار نمی کند.

به عنوان مثال نقاط A (10،10) B (20،20) C (10،1) D (1،10) H = . 5 را در نظر بگیرید و با این وجود با بررسی مشخص است که این بخش ها در جایی نزدیک به هر یک نیستنددیگر.

29 ژوئیه 2009 در ساعت 16:05 پاسخ داد ابتدایی 7،348 2 2 نشان های طلا 27 27 نشان نقره 33 33 نشان برنز

من موهایم را بیرون کشیدم و سعی کردم بفهمم چرا جواب پذیرفته شده برای من کار نمی کند. خیلی ممنون!

22 آگوست 2009 ساعت 18:40

همچنین قابل توجه است که شرایط مرزی در این حالت کار می کند (یعنی برای H = 0 یا H = 1 یا G = 0 یا G = 1 خطوط "فقط" لمس می کنند

7 اکتبر 2009 در 8:34

برای افرادی که در تجسم نتیجه مشکل دارند ، من این کار را در JavaScript انجام داده ام: jsfiddle. net/ferrybig/eokwl9mp

27 آگوست 2018 ساعت 14:34 رای

در اینجا پیشرفت در پاسخ گاوین وجود دارد. راه حل MARCP نیز مشابه است ، اما هیچ یک از این بخش ها را به تعویق انداخت.

این در واقع به نظر می رسد که یک کاربرد عملی از پاسخ گرت ریس نیز باشد ، زیرا معادل محصول متقابل در 2D محصول Perp-dot است ، این همان چیزی است که این کد از سه مورد استفاده می کند. تغییر به سه بعدی و با استفاده از محصول متقاطع ، هر دو S و T را در پایان درون یابی می کند ، منجر به دو نزدیکترین نقطه بین خطوط در 3D می شود. به هر حال ، راه حل 2D:

int get_line_intersection (float p0_x ، float p0_y ، float p1_x ، float p1_y ، float p2_x ، float p2_y ، float p3_x ، float p3_y ، float *i_x ، float *i_y)0 ؛s02_x = p0_x - p2_x ؛s02_y = p0_y - p2_y ؛s_numer = s10_x * s02_y - s10_y * s02_x ؛if ((s_numer<0) == denomPositive) retu 0; // No collision t_numer = s32_x * s02_y - s32_y * s02_x; if ((t_numer <0) == denomPositive) retu 0; // No collision if (((s_numer>denom) == denomPositive) || ((t_numer> denom) == denomPositive)) retu 0; // No collision // Collision detected t = t_numer / denom; if (i_x != NULL) *i_x = p0_x + (t * s10_x); if (i_y != NULL) *i_y = p0_y + (t * s10_y); retu 1;> 

در اصل این بخش را تا آخرین لحظه به تعویق می اندازد و بیشتر آزمایشات را تا قبل از انجام محاسبات خاص حرکت می دهد ، در نتیجه زودرس اضافه می شود. سرانجام ، همچنین از تقسیم توسط مورد صفر جلوگیری می شود که هنگام موازی خطوط رخ می دهد.

همچنین ممکن است بخواهید به جای مقایسه در برابر صفر ، از آزمایش اپسیلون استفاده کنید. خطوطی که بسیار نزدیک به موازی هستند می توانند نتیجه ای را کسب کنند که کمی خاموش باشند. این یک اشکال نیست ، محدودیت با ریاضی نقطه شناور است.

در 10 فوریه 2013 در 6:56 پاسخ داد ایمالس ایمالس 441 4 4 نشان نقره 3 3 نشان برنز اگر برخی از نقاط دارای مقدار 0 باشند ، شکست می خورد. این نباید درست اتفاق بیفتد؟ 20 فوریه 2013 در 15:21

من در هنگام تعویق تقسیم ، اصلاحاتی را برای اشکال معرفی کردم. T می تواند مثبت باشد که تعداد و فرقه هر دو منفی باشند.

2 آوریل 2013 در 5:05

اگر P0-P1 عمودی باشد و P2-P3 افقی باشد و دو بخش از آن عبور کند ، کار نمی کند.(بازگشت اول اجرا می شود)

9 اکتبر 2014 ساعت 14:16

مورد Coolinear دارای دو امکان است: عدم وجود و همپوشانی. اولین شول برگشتی دوم درست است. در کد شما این آزمایش نشده است. همیشه به عنوان بیشتر پاسخ ها در اینجا نادرست برمی گردد. این شرم آور است که به نظر نمی رسد هیچ راه حلی کار کند.

12 نوامبر 2014 ساعت 20:50

آیا می توانید به من روشن کنید که چرا همه اینها به جای چیزی که توصیف می کند مانند point2ydifference از چنین متغیرهای مبهمی مانند S32_Y استفاده می کند؟

23 ژانویه 2017 در 15:03 رای

سؤال C: چگونه می توانید تشخیص دهید که آیا دو بخش خط از هم عبور می کنند یا نه؟

من همان موضوع را جستجو کرده ام و از پاسخ ها راضی نبودم. بنابراین من مقاله ای را نوشتم که توضیح می دهد که چگونه می توان بررسی کرد که آیا دو بخش خط با تصاویر زیادی در آن قرار دارند یا خیر. جاوا کد کامل (و آزمایش شده) وجود دارد.

در اینجا مقاله است که به مهمترین قسمت ها بریده شده است:

این الگوریتم ، که بررسی می کند که آیا قطعه خط A با قطعه خط B تقاطع می کند ، به نظر می رسد:

جعبه های محدود چیست؟در اینجا دو جعبه محدود از دو بخش خط وجود دارد:

اگر هر دو جعبه محدود یک تقاطع داشته باشند ، شما بخش خط A را حرکت می دهید تا یک امتیاز در (0 | 0) باشد. اکنون شما یک خط از طریق مبدا تعریف شده توسط a دارید. اکنون بخش خط B را به همان روش جابجا کنید و بررسی کنید که آیا نقاط جدید بخش خط B در طرف های مختلف خط A قرار دارند یا خیر. اگر اینگونه است ، آن را به روش دیگر بررسی کنید. اگر این مورد نیز باشد ، بخش های خط تقاطع می کنند. اگر اینطور نیست ، آنها تلاقی نمی کنند.

سوال الف: دو بخش خط از کجا تقاطع می کنند؟

شما می دانید که دو بخش خط A و B تقاطع می کنند. اگر این را نمی دانید ، آن را با ابزارهایی که در "سوال C" به شما دادم بررسی کنید.

اکنون می توانید مواردی را طی کنید و با ریاضی کلاس هفتم راه حل دریافت کنید (به کد و مثال تعاملی مراجعه کنید).

سوال B: چگونه می توانید تشخیص دهید که آیا دو خط از هم عبور می کنند یا نه؟

بیایید نکته خود را بگوییم a = (x1 ، y1) ، نقطه b = (x2 ، y2) ، c = (x_3 ، y_3) ، d = (x_4 ، y_4). خط اول شما توسط AB (با A! = B) تعریف شده است ، و دوم شما توسط CD (با C! = D).

عملکرد Dolinesintersect (AB ، CD)دیگری اگر (x3 == x4)دیگر> 

سوال D: دو خط از کجا تلاقی می کنند؟

اگر اصلاً از هم تلاقی می کنند ، با سوال B بررسی کنید.

خطوط A و B برای هر خط با دو نقطه تعریف می شوند. شما اساساً می توانید همان منطق را در سوال A استفاده کنید.

31K 21 21 نشان های طلا 105 105 نشان نقره 126 126 نشان برنز 21 فوریه 2013 در ساعت 11:31 پاسخ داد مارتین توما مارتین توما 120K 153 153 نشان های طلا 603 603 نشان نقره 924 924 نشان های برنز

برای روشن شدن ، سؤال B در این پاسخ واقعاً مربوط به دو خط در حال تقاطع است ، نه بخش های خط. من شکایت نمیکنم؛نادرست نیستفقط نمی خواهم کسی گمراه شود.

16 ژوئیه 2013 در 3:46 "بدون" سوال C "وجود ندارد. و سوال D فقط به سوال A بازگردد. 22 سپتامبر 2016 ساعت 20:44 رای

جواب یک بار پذیرفته شده در اینجا نادرست است (از آن زمان غیرقابل قبول است ، بنابراین هورا!). این به درستی همه عدم تقاطع ها را از بین نمی برد. به طور کلی ممکن است به نظر برسد که کار کند اما می تواند شکست بخورد ، به خصوص در این مورد که 0 و 1 برای H معتبر تلقی می شوند.

مورد زیر را در نظر بگیرید:

خطوط در (4،1)-(5،1) و (0،0)-(0،2)

اینها خطوط عمود هستند که به وضوح با هم همپوشانی ندارند.

با توجه به پاسخ فوق ، این دو بخش خط در یک نقطه پایانی (مقادیر 0 و 1) ملاقات می کنند. این نقطه پایانی خواهد بود:

بنابراین ، ظاهراً دو بخش خط در (0/0) ملاقات می کنند ، که روی CD خط است ، اما در خط AB نیست. بنابراین چه اشتباهی رخ می دهد؟پاسخ این است که مقادیر 0 و 1 معتبر نیستند و فقط گاهی اوقات برای پیش بینی صحیح تقاطع نقطه پایانی اتفاق می افتد. هنگامی که گسترش یک خط (اما نه دیگر) بخش خط را برآورده می کند ، الگوریتم تقاطع بخش های خط را پیش بینی می کند ، اما این درست نیست. من تصور می کنم که با آزمایش شروع با AB در مقابل CD و سپس آزمایش با CD در مقابل AB ، این مشکل از بین می رود. فقط اگر هر دو بین 0 تا 1 به طور فراگیر سقوط کنند ، می توان گفت که از هم تقاطع می کنند.

اگر باید نقاط پایانی را پیش بینی کنید ، توصیه می کنم از روش محصول وکتور استفاده کنید.

پاسخ 4 آوریل 2009 در 0:26 1،803 16 16 نشان نقره 18 18 نشان برنز

پاسخ "پذیرفته شده" می تواند تغییر کند ، بنابراین شما باید آن را چیز دیگری بنامید.(در واقع ، من فکر می کنم از نظر شما تغییر کرده است)

15 فوریه 2013 در 21:21 رای

نسخه پایتون پاسخ ایمالس:

def find_intersection( p0, p1, p2, p3 ) : s10_x = p1[0] - p0[0] s10_y = p1[1] - p0[1] s32_x = p3[0] - p2[0] s32_y = p3[1] - p2[1] denom = s10_x * s32_y - s32_x * s10_y if denom == 0 : retu None # collinear denom_is_positive = denom>0 s02_x = p0 [0] - p2 [0] s02_y = p0 [1] - p2 [1] s_numer = s10_x * s02_y - s10_y * s02_x if (s_numer<0) == denom_is_positive : retu None # no collision t_numer = s32_x * s02_y - s32_y * s02_x if (t_numer <0) == denom_is_positive : retu None # no collision if (s_numer>denom) == denom_is_positive or (t_numer>فرقه) == DENOM_IS_POSITITY: بازگشت به هیچ # بدون برخورد # برخورد # برخورد t = t_numer / denom تقاطع_point = [p0 [0] + (t * s10_x) ، p0 [1] + (t * s10_y)] بازگشت تقاطع_point_point 

23 اکتبر 2013 در 19:42 پاسخ داد کریس کریس 183 1 1 نشان نقره 8 8 نشان های برنز به یاد داشته باشید که باید شماره های خود را شناور کنید یا خط 8 را تغییر دهید تا از denom = float استفاده کنید (.) 4 اکتبر 2017 در 2:27 رای

پیدا کردن تقاطع صحیح دو بخش خط یک کار غیر مهم است و موارد زیادی در آن وجود دارد. در اینجا یک راه حل خوب مستند ، کار و آزمایش شده در جاوا آورده شده است.

در اصل ، سه مورد وجود دارد که می تواند هنگام یافتن تقاطع دو بخش خط اتفاق بیفتد:

1. بخش ها تقاطع نمی کنند
2. یک نقطه تقاطع منحصر به فرد وجود دارد
3. تقاطع بخش دیگری است

توجه: در کد فرض می کنم که یک بخش خط (x1 ، y1) ، (x2 ، y2) با x1 = x2 و y1 = y2 یک بخش خط معتبر است. از نظر ریاضی ، یک بخش خط از نکات متمایز تشکیل شده است ، اما من به بخش ها اجازه می دهم تا در این اجرای برای کامل بودن امتیاز داشته باشند.

کد از repo github من گرفته شده است

/*** این قطعه تقاطع دو بخش خط را پیدا می کند.* تقاطع ممکن است خالی باشد ، یک نقطه واحد یا * تقاطع * یک زیرمجموعه است که یک همپوشانی وجود دارد.*/ واردات java. lang. math. abs ؛واردات java. lang. math. max ؛واردات java. lang. math. min ؛وارد کردن java. util. arraylist ؛وارد کردن java. util. list ؛کلاس عمومی LinesegmentLineseMentinentersIctionBoolean Public Equals (PT PT)>// جهت گیری نقطه "C" را نسبت به بخش خط (a ، b) // اگر هر سه نقطه خطی باشد ، 0 را برمی گرداند.// بازگش ت-1 اگر 'c' در جهت عقربه های ساعت به بخش (a ، b) باشد ، یعنی حق خط که توسط بخش تشکیل شده است.// اگر "C" خلاف جهت عقربه های ساعت با بخش (A ، B) باشد ، یعنی سمت چپ خط // که توسط بخش تشکیل شده است ، بازگشت. جهت گیری عمومی استاتیک عمومی (PT A ، Pt B ، Pt C)0) ? -1 : +1;>// آزمایش کنید که آیا نقطه "C" در بخش خط است (A ، B).// اطمینان حاصل کنید که ابتدا نقطه C به بخش (a ، b) و // collinear است و سپس بررسی کنید که آیا C در مستطیل تشکیل شده توسط (a ، b) pointonline استاتیک عمومی (pt a ، pt b ، pt c) است.لیست استاتیک عمومی GetCommonEndPoints (PT P1 ، PT P2 ، PT P3 ، PT P4)() ؛if (p1. equals (p3))دیگری اگر (p1. Equals (p4))دیگری اگر (p2. equals (p3))دیگری اگر (p2. equals (p4))retu points;>// نقطه (های) تقاطع دو بخش خط را پیدا می کند. برخلاف بخش های خط معمولی // ، بخش هایی که نقاط هستند (x1 = x2 و y1 = y2) مجاز هستند. عمومی استاتیک PT [] LinesementlineseMentinentersection (PT P1 ، Pt P2 ، Pt P3 ، Pt P4)؛// هر دو بخش یک نقطه واحد هستند. if (p1. equals (p2) && p2. equals (p3) && p3. equals (p4)) pt جدید را برگردانید [] ؛نقاط پایانی لیست = getCommonEndPoints (P1 ، P2 ، P3 ، P4) ؛int n = endpoints. size () ؛// یکی از بخش های خط یک نقطه متقاطع است.// توجه: بررسی فقط n == 1 برای بازگشت زودرس کافی نیست // زیرا راه حل ممکن است یک بخش فرعی باشد. Boolean Singleton = P1. Equals (P2) ||P3. Equals (P4) ؛if (n == 1 && Singleton) PT جدید را برگردانید [] ؛// بخش ها برابر هستند. if (n == 2) PT جدید را برگردانید [] ؛boolean collinearsegments = (جهت گیری (p1 ، p2 ، p3) == 0) && (جهت گیری (p1 ، p2 ، p4) == 0) ؛// تقاطع یک بخش زیر از دو بخش // خواهد بود زیرا آنها با هم همپوشانی دارند. if (collinearsegments)/* فراتر از این نقطه یک نقطه تقاطع منحصر به فرد وجود دارد.*/ // بخش شماره 1 یک خط عمودی است. if (abs (p1. x - p2. x)// بخش شماره 2 یک خط عمودی است. if (abs (p3. x - p4. x) double m1 = (p2.y - p1.y) / (p2.x - p1.x); double m2 = (p4.y - p3.y) / (p4.x - p3.x); double b1 = p1.y - m1 * p1.x; double b2 = p3.y - m2 * p3.x; double x = (b2 - b1) / (m1 - m2); double y = (m1 * b2 - m2 * b1) / (m1 - m2); retu new Pt[];>> 

در اینجا یک مثال استفاده ساده وجود دارد:

 عمومی خالی استاتیک اصلی (رشته [] args) < Pan> ؛// هر دو بخش یک نقطه واحد هستند. if (p1. equals (p2) && p2. equals (p3) && p3. equals (p4)) pt جدید را برگردانید [] ؛نقاط پایانی لیست = getCommonEndPoints (P1 ، P2 ، P3 ، P4) ؛int n = endpoints. size () ؛// یکی از بخش های خط یک نقطه متقاطع است.// توجه: بررسی فقط n == 1 برای بازگشت زودرس کافی نیست // زیرا راه حل ممکن است یک بخش فرعی باشد. Boolean Singleton = P1. Equals (P2) ||P3. Equals (P4) ؛if (n == 1 && Singleton) PT جدید را برگردانید [] ؛// بخش ها برابر هستند. if (n == 2) PT جدید را برگردانید [] ؛boolean collinearsegments = (جهت گیری (p1 ، p2 ، p3) == 0) && (جهت گیری (p1 ، p2 ، p4) == 0) ؛// تقاطع یک بخش زیر از دو بخش // خواهد بود زیرا آنها با هم همپوشانی دارند. if (collinearsegments)