شناسایی نقاط تقاطع

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

تقاطع خط خط یکی از متداول ترین کارهایی که در مشکلات هندسه پیدا خواهید کرد تقاطع خط است. با وجود این واقعیت که بسیار رایج است ، بسیاری از رمزگذارها هنوز با آن مشکل دارند. سوال اول این است که خطوط خود را به چه شکلی داده ایم و چه شکلی را دوست داریم؟در حالت ایده آل ، هر یک از خطوط ما به شکل خواهد بودتبر+توسط = c، جایی که A ، B و C اعدادی هستند که خط را تعریف می کنند. با این حال ، ما به ندرت خطوطی در این قالب داده می شود ، اما می توانیم به راحتی از دو نقطه چنین معادله ای ایجاد کنیم. بگویید به ما دو نکته مختلف داده می شود (x₁, y₁) و (x₂, y₂) ، و می خواهید A ، B و C را برای معادله فوق پیدا کنید. ما می توانیم با تنظیم این کار را انجام دهیم

صرف نظر از نحوه مشخص شدن خطوط ، شما باید بتوانید دو نقطه مختلف را در طول خط ایجاد کنید ، و سپس A ، B و C. تولید کنید ، اکنون اجازه دهید بگوییم که شما خطوط دارید ، که توسط معادلات ارائه شده است:

برای یافتن نقطه ای که در آن دو خط از هم عبور می کنند ، ما به سادگی باید دو معادله را برای دو ناشناخته ، X و Y حل کنیم.

برای دیدن این که از کجا آمده است ، در نظر بگیرید معادله برتر توسط b را ضرب کنید₂، و معادله پایین توسط b₁بشراین به شما می دهد

اکنون ، معادله پایین را از معادله بالا جدا کنید تا دریافت کنید

سرانجام ، هر دو طرف را تقسیم کنیدA₁B₂ - A₂B₁، و معادله x را دریافت می کنید. معادله y می تواند به طور مشابه حاصل شود.

این مکان محل تقاطع دو خط را به شما می دهد ، اما اگر بخش های خط داشته باشید ، نه خط. در این حالت ، باید اطمینان حاصل کنید که نکته ای که پیدا کردید در هر دو بخش خط است. اگر بخش خط شما از آن خارج شود(x₁,y₁)به(x₂,y₂)، سپس برای بررسی اینکه آیا (x ، y) در آن بخش است ، فقط باید آن را بررسی کنیدحداقل (x₁,x₂) ≤ x ≤ max (x₁,x₂)، و همین کار را برای y انجام دهید. شما باید در مورد مسائل دقیق دو برابر مراقب باشید. اگر نکته شما در لبه بخش درست باشد ، یا اگر این بخش افقی یا عمودی باشد ، یک مقایسه ساده ممکن است مشکل ساز باشد. در این موارد ، شما می توانید مقایسه های خود را با مقداری تحمل انجام دهید ، یا در غیر این صورت از یک کلاس کسری استفاده کنید.

پیدا کردن یک دایره از 3 امتیاز با 3 امتیاز که Colinear نیستند (همه در یک خط) این سه امتیاز به طور منحصر به فرد یک دایره را تعریف می کنند. اما ، چگونه می توانید مرکز و شعاع آن دایره را پیدا کنید؟این کار به نظر می رسد یک کاربرد ساده از تقاطع خط است. ما می خواهیم دوقلوهای عمود XY و YZ را پیدا کنیم و سپس تقاطع آن دو بیستور را پیدا کنیم. این به ما مرکز دایره می دهد.

برای پیدا کردن دو قطعه عمود بر XY ، خط را از x تا y به شکل پیدا کنیدتبر+توسط = cبشریک خط عمود بر این خط توسط معادله داده می شود-bx+ay = d، برای برخی D. برای یافتن D برای خط خاصی که به آن علاقه مندیم ، با گرفتن نقطه میانی اجزای X و Y به طور مستقل ، نقطه میانی بین x و y را پیدا کنید. سپس ، آن مقادیر را در معادله جایگزین کنید تا D. را پیدا کنید.

بازتاب بازتاب یک نقطه در یک خط به همان تکنیک ها نیاز به پیدا کردن یک دایره از 3 امتیاز دارد. ابتدا توجه کنید که فاصله از x به خط بازتاب همان فاصله از x تا خط بازتاب است. همچنین توجه داشته باشید که خط بین X و X عمود بر خط بازتاب است. حال ، اگر خط تأمل به عنوان ارائه شده باشدتبر+توسط = c، سپس ما از قبل می دانیم که چگونه یک خط عمود بر آن پیدا کنیم:-bx+ay = dبشربرای یافتن D ، ما به سادگی مختصات X را وصل می کنیم. اکنون می توانیم تقاطع دو خط را در Y پیدا کنیم ، و سپس پیدا کنیمx '= y - (x - y).

چرخش چرخش واقعاً با تقاطع خط مطابقت ندارد ، اما احساس کردم که خوب است که آن را با تأمل گروه بندی کنیم. در حقیقت ، راه دیگر برای یافتن نقطه منعکس شده ، چرخش نقطه اصلی 180 درجه در مورد Y است.

تصور کنید که ما می خواهیم یک نقطه را به دور دیگری بچرخانیم ، خلاف جهت عقربه های ساعت با درجه θ. برای سادگی ، فرض می کنیم که ما در مورد منشاء می چرخیم. در این حالت ، ما می توانیم آن را پیدا کنیمx '= x cos (θ) - y sin (θ)وتy '= x sin (θ) + y cos (θ)بشراگر در حال چرخش در حدود یک نقطه غیر از مبدا هستیم ، می توانیم با تغییر سیستم مختصات خود به گونه ای که منشأ در نقطه چرخش است ، چرخش را با فرمول های فوق انجام دهیم و سپس سیستم مختصات را به جایی برگردانیم. آن آغاز شده.

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

ابتدا همه نکات خود را حلقه کنید و سمت چپ را پیدا کنید. اگر کراوات وجود دارد ، بالاترین نقطه را انتخاب کنید. شما به یقین می دانید که این نکته در بدنه محدب خواهد بود ، بنابراین ما با آن شروع خواهیم کرد. از اینجا ، ما قصد داریم در جهت عقربه های ساعت در لبه بدنه حرکت کنیم و نقاط را روی پوسته انتخاب کنیم ، یک بار. سرانجام ، ما به نقطه شروع باز خواهیم گشت. برای یافتن نکته بعدی در اطراف بدنه ، ما از محصولات متقاطع استفاده خواهیم کرد. اول ، ما یک نکته بلااستفاده را انتخاب خواهیم کرد و نکته بعدی ، n را به آن نقطه تنظیم خواهیم کرد. در مرحله بعد ، ما از طریق هر نقطه استفاده نشده ، x و اگر تکرار خواهیم کرد(X-P) X (N-P)(جایی که P نکته قبلی است) منفی است ، ما N را به X تنظیم خواهیم کرد. برای تصویرگری از نحوه عملکرد الگوریتم به نمودار زیر مراجعه کنید. ما با P به عنوان چپ ترین نقطه شروع می کنیم. حال بگویید که ما N و X را همانطور که در سمت چپ ترین قاب نشان داده شده است ، داریم. در این حالت ، محصول متقاطع منفی خواهد بود ، بنابراین ما n = x را تنظیم خواهیم کرد ، و هیچ نکات بلااستفاده دیگری وجود نخواهد داشت که محصول متقابل را منفی کند ، و از این رو ، ما در حال تنظیم P = N. در قاب بعدی خواهیم بود.، ما دوباره تنظیم N = x را به پایان می رسانیم ، زیرا محصول متقاطع در اینجا منفی خواهد بود. با این حال ، ما هنوز انجام نشده ایم زیرا هنوز نکته دیگری وجود دارد که محصول متقابل را منفی می کند ، همانطور که در قاب نهایی نشان داده شده است.

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

محدب (نقطه [] x) int n = طول (x) ؛int p = 0 ؛// ابتدا چپ ترین نقطه را برای (int i = 1 ؛ iint start = p ؛doint n = -1 ؛برای (int i = 0 ؛ i

// به همان نقطه ای که از آن آمده اید برنگردید اگر (i == P) ادامه دهید.

// اگر هنوز N وجود ندارد ، اگر (n == -1) n = i آن را روی i تنظیم کنید. int cross = (x [i] - x [p]) x (x [n] - x [p]) ؛

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

// اگر OnEdge صحیح است ، تا حد امکان از نقاط برای // بدنه محدب استفاده کنید ، در غیر این صورت تا حد امکان. CONVEXHULL (نقطه [] x ، Boolean OnEdge) int n = طول (x) ؛int p = 0 ؛boolean [] استفاده = boolean جدید [n] ؛// ابتدا چپ ترین نقطه را برای (int i = 1 ؛ iint start = p ؛doint n = -1 ؛int dist = onEdge؟ inf: 0 ؛برای (int i = 0 ؛ i

// به همان نقطه ای که از آن آمده اید برنگردید اگر (i == P) ادامه دهید.

// اگر ([i] استفاده می شود) به یک نقطه بازدید نشوید.

// اگر هنوز N وجود ندارد ، آن را روی x تنظیم کنید اگر (n == -1) n = i ؛int cross = (x [i] - x [p]) x (x [n] - x [p]) ؛

// d فاصله از p تا x int d = (x [i] - x [p]) ⋅ (x [i] - x [p]) ؛if (صلیب<0)//As described above, set N=X n = i; dist = d;>دیگری اگر (صلیب == 0) // در این حالت ، هر دو n و x در جهت // یکسان قرار دارند. اگر OnEdge درست است ، // نزدیکترین را انتخاب کنید ، در غیر این صورت دورترین را انتخاب کنید. if (onEdge && delse if(!onEdge && d> dist)dist = d; n = i;>>> p = n; used[p] = true;>while(start!=p);>