https://wiki.hsoub.com/index.php?title=Algorithms/two_line_segments_intersect&feed=atom&action=history
Algorithms/two line segments intersect - تاريخ المراجعة
2024-03-28T18:54:43Z
تاريخ التعديل لهذه الصفحة في الويكي
MediaWiki 1.35.0
https://wiki.hsoub.com/index.php?title=Algorithms/two_line_segments_intersect&diff=29638&oldid=prev
جميل-بيلوني في 10:26، 3 مارس 2020
2020-03-03T10:26:58Z
<p></p>
<table class="diff diff-contentalign-right diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ar">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">→ مراجعة أقدم</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">مراجعة 10:26، 3 مارس 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >سطر 1:</td>
<td colspan="2" class="diff-lineno">سطر 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><noinclude>{{DISPLAYTITLE:تقاطع قطعتين مستقيمتين}}</noinclude></div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div><noinclude>{{DISPLAYTITLE:تقاطع قطعتين مستقيمتين}}</noinclude></div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;"></del></div></td><td colspan="2"> </td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتين (لتكونا (p1, q1) و (p2, q2))، وتعتمد في ذلك على مفهوم التوجيه Orientation.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتين (لتكونا (p1, q1) و (p2, q2))، وتعتمد في ذلك على مفهوم التوجيه Orientation.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
</table>
جميل-بيلوني
https://wiki.hsoub.com/index.php?title=Algorithms/two_line_segments_intersect&diff=29223&oldid=prev
Mohammed Taher: أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:تقاطع قطعتين مستقيمتين}}</noinclude> تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتي...'
2019-10-25T22:41:29Z
<p>أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:تقاطع قطعتين مستقيمتين}}</noinclude> تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتي...'</p>
<p><b>صفحة جديدة</b></p><div><noinclude>{{DISPLAYTITLE:تقاطع قطعتين مستقيمتين}}</noinclude><br />
<br />
تتحقق هذه الخوارزمية من تقاطع قطعتين مستقيمتين (لتكونا (p1, q1) و (p2, q2))، وتعتمد في ذلك على مفهوم التوجيه Orientation.<br />
<br />
هناك ثلاثة طرق لتوجيه ثلاث نقاط مرتبة على مستوى معين:<br />
<br />
# عكس عقارب الساعة<br />
# مع عقارب الساعة<br />
# على خط واحد colinear<br />
<br />
يعرض الشكل التالي طرق التوجيه الثلاثة الواردة في أعلاه للنقاط (a, b, c):<br />
<br />
تكون القطعتان المستقيمتان (p1, q1) و (p2, q2) متقاطعتين إذا -وفقط إذا- تحقق أحد الشرطين التاليين:<br />
<br />
# الحالة العامة:<br />
<br />
* إذا امتلكت النقاط (p1, q1, p2) و (p1, q1, q2) توجيهاً مختلفًا.<br />
* وإذا امتلكت النقاط (p2, q2, p1) و (p2, q2, q1) توجيهًا مختلفًا.<br />
<br />
# حالة خاصة:<br />
<br />
* إذا كانت النقاط (p1, q1, p2) و (p1, q1, q2) و (p2, q2, p1) و (p2, q2, q1) على استقامة واحدة.<br />
* إذا تقاطع الإسقاط على المحور السيني للقطعتين المستقيمتين (p1, q1) و (p2, q2).<br />
* إذا تقاطع الإسقاط على المحور الصادي للقطعتين المستقيمتين (p1, q1) و (p2, q2).<br />
<br />
== تنفيذ الخوارزمية ==<br />
<br />
تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:<br />
<br />
* C++:<br />
<br />
<source lang="c++">#include <iostream> <br />
using namespace std; <br />
<br />
struct Point <br />
{ <br />
int x; <br />
int y; <br />
}; <br />
<br />
// تتحقق الدالة من أن النقطة المعطاة الأولى تقع على القطعة المستقيمة الناتجة من النقطتين الأخرتين<br />
bool onSegment(Point p, Point q, Point r) <br />
{ <br />
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && <br />
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y)) <br />
return true; <br />
<br />
return false; <br />
} <br />
<br />
// تعيد الدالة القيم التالية بعد تحديد التوجيه الخاص بالنقاط الثلاثة المعطاة<br />
// 0 ---> النقاط الثلاثة على استقامة واحدة<br />
// 1 ---> التوجيه مع عقارب الساعة<br />
// 2 ---> التوجيه عكس عقارب الساعة<br />
int orientation(Point p, Point q, Point r) <br />
{ <br />
int val = (q.y - p.y) * (r.x - q.x) - <br />
(q.x - p.x) * (r.y - q.y); <br />
<br />
if (val == 0) return 0; // على استقامة واحدة<br />
<br />
return (val > 0)? 1: 2; // مع أو عكس عقارب الساعة<br />
} <br />
<br />
// الدالة الرئيسية التي تعيد قيمة صحيحة إذا كانت القطعتان المستقيمتان متقاطعتين<br />
<br />
bool doIntersect(Point p1, Point q1, Point p2, Point q2) <br />
{ <br />
// تحديد التوجيهات المطلوبة للحالتين العامة والخاصة<br />
int o1 = orientation(p1, q1, p2); <br />
int o2 = orientation(p1, q1, q2); <br />
int o3 = orientation(p2, q2, p1); <br />
int o4 = orientation(p2, q2, q1); <br />
<br />
// الحالة العامة<br />
if (o1 != o2 && o3 != o4) <br />
return true; <br />
<br />
// الحالات الخاصة<br />
<br />
// النقاط p1 و q1 و p2 على استقامة واحدة والنقطة p2 تقع على القطعة المستقيمة p1q1<br />
if (o1 == 0 && onSegment(p1, p2, q1)) return true; <br />
<br />
// النقاط p1 و q1 و p2 على استقامة واحدة والنقطة q2 تقع على القطعة المستقيمة p1q1<br />
if (o2 == 0 && onSegment(p1, q2, q1)) return true; <br />
<br />
// النقاط p2 و q2 و q1 على استقامة واحدة والنقطة p1 تقع على القطعة المستقيمة p2q2<br />
if (o3 == 0 && onSegment(p2, p1, q2)) return true; <br />
<br />
// النقاط p2 و q2 و q1 على استقامة واحدة والنقطة q1 تقع على القطعة المستقيمة p2q2<br />
if (o4 == 0 && onSegment(p2, q1, q2)) return true; <br />
<br />
return false; // لا تنتمي النقاط إلى أيٍّ من الحالات السابقة<br />
} <br />
<br />
// اختبار الدوال السابقة <br />
int main() <br />
{ <br />
struct Point p1 = {1, 1}, q1 = {10, 1}; <br />
struct Point p2 = {1, 2}, q2 = {10, 2}; <br />
<br />
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; <br />
<br />
p1 = {10, 0}, q1 = {0, 10}; <br />
p2 = {0, 0}, q2 = {10, 10}; <br />
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; <br />
<br />
p1 = {-5, -5}, q1 = {0, 0}; <br />
p2 = {1, 1}, q2 = {10, 10}; <br />
doIntersect(p1, q1, p2, q2)? cout << "Yes\n": cout << "No\n"; <br />
<br />
return 0; <br />
} <br />
</source><br />
* بايثون:<br />
<br />
<source lang="python"></source><br />
* جافا:<br />
<br />
<source lang="java">class GFG <br />
{ <br />
<br />
static class Point <br />
{ <br />
int x; <br />
int y; <br />
<br />
public Point(int x, int y) <br />
{ <br />
this.x = x; <br />
this.y = y; <br />
} <br />
<br />
}; <br />
<br />
// تتحقق الدالة من أن النقطة المعطاة الأولى تقع على القطعة المستقيمة الناتجة من النقطتين الأخرتين<br />
static boolean onSegment(Point p, Point q, Point r) <br />
{ <br />
if (q.x <= Math.max(p.x, r.x) && q.x >= Math.min(p.x, r.x) && <br />
q.y <= Math.max(p.y, r.y) && q.y >= Math.min(p.y, r.y)) <br />
return true; <br />
<br />
return false; <br />
} <br />
<br />
// تعيد الدالة القيم التالية بعد تحديد التوجيه الخاص بالنقاط الثلاثة المعطاة<br />
// 0 ---> النقاط الثلاثة على استقامة واحدة<br />
// 1 ---> التوجيه مع عقارب الساعة<br />
// 2 ---> التوجيه عكس عقارب الساعة<br />
static int orientation(Point p, Point q, Point r) <br />
{ <br />
int val = (q.y - p.y) * (r.x - q.x) - <br />
(q.x - p.x) * (r.y - q.y); <br />
<br />
if (val == 0) return 0; // على استقامة واحدة <br />
<br />
return (val > 0)? 1: 2; // مع أو عكس عقارب الساعة <br />
} <br />
<br />
// الدالة الرئيسية التي تعيد قيمة صحيحة إذا كانت القطعتان المستقيمتان متقاطعتين<br />
static boolean doIntersect(Point p1, Point q1, Point p2, Point q2) <br />
{ <br />
// تحديد التوجيهات المطلوبة للحالتين العامة والخاصة <br />
int o1 = orientation(p1, q1, p2); <br />
int o2 = orientation(p1, q1, q2); <br />
int o3 = orientation(p2, q2, p1); <br />
int o4 = orientation(p2, q2, q1); <br />
<br />
// الحالة العامة <br />
if (o1 != o2 && o3 != o4) <br />
return true; <br />
<br />
// الحالات الخاصة <br />
// النقاط p1 و q1 و p2 على استقامة واحدة والنقطة p2 تقع على القطعة المستقيمة p1q1 <br />
if (o1 == 0 && onSegment(p1, p2, q1)) return true; <br />
<br />
// النقاط p1 و q1 و p2 على استقامة واحدة والنقطة q2 تقع على القطعة المستقيمة p1q1 <br />
if (o2 == 0 && onSegment(p1, q2, q1)) return true; <br />
<br />
// النقاط p2 و q2 و q1 على استقامة واحدة والنقطة p1 تقع على القطعة المستقيمة p2q2 <br />
if (o3 == 0 && onSegment(p2, p1, q2)) return true; <br />
<br />
// النقاط p2 و q2 و q1 على استقامة واحدة والنقطة q1 تقع على القطعة المستقيمة p2q2 <br />
if (o4 == 0 && onSegment(p2, q1, q2)) return true; <br />
<br />
return false; // لا تنتمي النقاط إلى أيٍّ من الحالات السابقة<br />
} <br />
<br />
// اختبار الدوال السابقة<br />
public static void main(String[] args) <br />
{ <br />
Point p1 = new Point(1, 1); <br />
Point q1 = new Point(10, 1); <br />
Point p2 = new Point(1, 2); <br />
Point q2 = new Point(10, 2); <br />
<br />
if(doIntersect(p1, q1, p2, q2)) <br />
System.out.println("Yes"); <br />
else<br />
System.out.println("No"); <br />
<br />
p1 = new Point(10, 1); q1 = new Point(0, 10); <br />
p2 = new Point(0, 0); q2 = new Point(10, 10); <br />
if(doIntersect(p1, q1, p2, q2)) <br />
System.out.println("Yes"); <br />
else<br />
System.out.println("No"); <br />
<br />
p1 = new Point(-5, -5); q1 = new Point(0, 0); <br />
p2 = new Point(1, 1); q2 = new Point(10, 10);; <br />
if(doIntersect(p1, q1, p2, q2)) <br />
System.out.println("Yes"); <br />
else<br />
System.out.println("No"); <br />
} <br />
} </source><br />
تعطي الشيفرات السابقة المخرجات التالية:<br />
<br />
<source lang="text">No<br />
Yes<br />
No</source><br />
== مصادر ==<br />
<br />
* صفحة [https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ How to check if two given line segments intersect?] في توثيق الخوارزميات في موقع GeeksforGeeks.<br />
<br />
[[تصنيف: الخوارزميات]]<br />
[[تصنيف: الخوارزميات الهندسية]]</div>
Mohammed Taher