top of page

כמה משולשים יש כאן? פתרון בעזרת Geometry

לפני זמן מה פרסמתי פתרון SQL-י לאתגר הבא - כמה משולשים יש בשרטוט הבא:

בפוסט הזה אציג פתרון המבוסס על Geometry, קצת "נלכלכך" את הידיים במתימטיקה (גיאומטריה אנאליטית) ברמה של חטיבת ביניים, הפתרון בסוף מאוד לא יעיל מבחינת הביצועים,אבל כמו הרבה דברים בחיים - העיקר אינו היעד אלא הדרך.

אדלג על המבוא ל-Geometry ורק אזכיר שמדובר בתמיכה בטיפול והצגה של נתונים גיאומטריים, ושזה מבוסס על דוטנט, ולכן אם תהיה שגיאה לא נקבל הודעה ידידותית כמו "Divide by zero error encountered." אלא הודעה מסובכת בדוטנטית ספרותית..


ולמלאכה: ניצור טבלה עבור 20 הקודקודים שבציור -

If            Object_ID('T_VerticesG') Is Null

Create Table T_VerticesG --"kodkodim"

              (Name Int,

              Place Geometry,

              Constraint PK_GVertices Primary Key Clustered(Name));

עמודה Name תכלול את מספר הקודקוד (1-20), ועמודה Place את מיקומו הגיאומטרי במערכת הצירים.

זה קצת מאתגר כי צריך לדייק ולא לכתוב "בערך" ומיקומי הנקודות צריכים להיות כך שנקודות 1-5-6-7-8 יהיו על קו ישר.

נוודא שהטבלה ריקה ונכניס את 3 קודקודי המשולש הכללי, כשאת מקומם נקבע "לפי העין":

Truncate Table T_VerticesG;

Insert

Into   T_VerticesG(Name,Place)

Select Name, Place

From   (Values       (1,geometry::STPointFromText('POINT(6 6)', 0)),

                             (4,geometry::STPointFromText('POINT(0 0)', 0)),

                             (20,geometry::STPointFromText('POINT(12 0)', 0))) T(Name,Place);

זו הדרך ליצג את הנקודות (6,6) קודקוד1, (0,0) קודקוד 4, (12,0) קודקוד 20 בתור Geometry Datatype.

נעבור לנקודות שעל צלעות המשולש: 12 היא על הצלע 4-20, כאשר X=6, לא מסובך לחשב את הקואורדינטות שלה, אבל ניצור פונקציה שתחזיר את ערך Y על הצלע 4-20 עבור X=6.

נקודות 3 & 19 הן על הצלעות 1-4 ו- 1-20 בהתאמה, כאשר Y=3; וגם עבור זה ניצור פונקציה סקלארית.

נקודות 2 & 8 הן על הצלעות 1-4 ו- 1-20 בהתאמה, כאשר Y=5 (אותה הפונקציה).

כל שאר הנקודות מתבססות על הנקודות הנ"ל, או על נקודות שמתבססות על הנקודות הנ"ל.

הפונקציה למציאת נקודה על הקו המחבר שתי נקודות עבור X נתון:

CREATE OR ALTER Function [Fn_PointY]

              (@Point1 Int,

              @Point2 Int,

              @X Float)

              Returns Geometry

              As

Begin

Declare       @X1 Int,

              @Y1 Int,

              @X2 Int,

              @Y2 Int,

              @Y Float,

              @G Geometry;

 

Select @X1=Place.STX,

              @Y1=Place.STY

From   T_VerticesG

Where  Name=@Point1;

 

Select @X2=Place.STX,

              @Y2=Place.STY

From   T_VerticesG

Where  Name=@Point2;

 

Select @Y=@X1-(@Y1-@X)*Cast((@X1-@X2) As Float)/NullIf(@Y1-@Y2,0);

Select @Y=Coalesce(@Y,@Y1,@Y2);

Select @G=geometry::STPointFromText(Concat('POINT(',@X,' ',@Y,') '),0);

Return @G;

End;

 הפונקציה מחלצת מהטבלה את ערכי X & Y של שתי הנקודות המתאימות, ובעזרת השיפוע של הקו ובהתייחס לנקודה הראשונה מבין השתיים, היא מחשבת את ערכו של Y ומחזירה נתון מסוג Geometry. השימוש ב-NullIf וב-Coalesce הוא עבור מקרי קצה בהם הקו אנכי ואין לו שיפוע.

הפונקציה המשלימה - חישוב X עבור Y נתון ושתי נקודות:

CREATE OR ALTER Function [Fn_PointX]

              (@Point1 Int,

              @Point2 Int,

              @Y Float)

              Returns Geometry

              As

Begin

Declare       @X1 Int,

              @Y1 Int,

              @X2 Int,

              @Y2 Int,

              @X Float,

              @G Geometry;

 

Select @X1=Place.STX,

              @Y1=Place.STY

From   T_VerticesG

Where  Name=@Point1;

 

Select @X2=Place.STX,

              @Y2=Place.STY

From   T_VerticesG

Where  Name=@Point2;

 

Select @X=@X1-(@Y1-@Y)*Cast((@X1-@X2) As Float)/(@Y1-@Y2);

Select @G=geometry::STPointFromText(Concat('POINT(',@X,' ',@Y,') '),0);

Return @G;

End;

וכעת להכנסת הנקודות:

Insert

Into   T_VerticesG(Name,Place)

Select 12,dbo.Fn_PointY(4,20,6)

Union All

Select 3,dbo.Fn_PointX(1,4,3)

Union All

Select 2,dbo.Fn_PointX(1,4,5)

Union All

Select 19,dbo.Fn_PointX(1,20,3)

Union All

Select 18,dbo.Fn_PointX(1,20,5);

את נקודה 10 נחשב בתור החיתוך שבין הקו 1-12 והקו 3-19. יש פונקציה ב-Geometry שמחשבת חיתוך בין שני קטעים, אבל היא פועלת על קטעים ולא על תווים. כלומר - אם החיתוך הוא בין המשכי הקטעים היא תחזיר Null; ולכן נצטרך להמציא את הגלגל וליצור פונקציה שכזו בעצמנו:

CREATE OR ALTER   Function [Fn_IntersectionAlt]

              (@Point1a Int,

              @Point2a Int,

              @Point1b Int,

              @Point2b Int)

              Returns Geometry

              As

Begin

Declare       @X1a Float,

              @Y1a Float,

              @X2a Float,

              @Y2a Float,

              @X1b Float,

              @Y1b Float,

              @X2b Float,

              @Y2b Float,

              @X Float,

              @Y Float,

              @G Geometry;

 

Select @X1a=Place.STX,

              @Y1a=Place.STY

From   T_VerticesG

Where  Name=@Point1a;

 

Select @X2a=Place.STX,

              @Y2a=Place.STY

From   T_VerticesG

Where  Name=@Point2a;

 

Select @X1b=Place.STX,

              @Y1b=Place.STY

From   T_VerticesG

Where  Name=@Point1b;

 

Select @X2b=Place.STX,

              @Y2b=Place.STY

From   T_VerticesG

Where  Name=@Point2b;

 

Declare       @Ma Float=(@Y1a-@Y2a)/NullIf(@X1a-@X2a,0),

              @Mb Float=(@Y1b-@Y2b)/NullIf(@X1b-@X2b,0);

Declare       @Ba Float=IsNull(@Y1a-@Ma*@X1a,0),

              @Bb Float=IsNull(@Y1b-@Mb*@X1b,0);

 

Select @X=Case When @Ma Is Null Then IsNull(@X1a,@X2a)

                             When @Mb Is Null Then IsNull(@X1b,@X2b)

                             Else (@Bb-@Ba)/(@Ma-@Mb)

                             End;

Select @Y=IsNull(@Ma*@X+@Ba,@Mb*@X+@Bb);

Select @G = geometry::STPointFromText(Concat('POINT(',@X,' ',@Y,')'), 0);

Return @G;

End;

בקצרה: עבור כל נקודה מחשבים את משוואת הקו בתור Y=mX+b כאשר השיפוע m הוא מנת ההפרשים בין ה-Y-ים ל-X-ים, ו-b, נקודת החיתוך עם ציר Y, מתקבל מהצבת אחת הנקודות ו-m שזה עתה חושב במשוואה Y=mX+b. לאחר שיש את שתי המשוואות, משווים בין אגפיהם הימניים ומחלצים את X (בנקודת החיתוך) וכשמציבים אותו באחת המשוואות - מקבלים את Y (בנקודת החיתוך); ולא שוכחים לטפל במקרי קצה בהם אחד הקווים אנכי.

Insert

Into   T_VerticesG(Name,Place)

Select 10,dbo.Fn_IntersectionAlt(3,19,1,12);

לאחר שחישבנו את נקודה 10 ניתן לחשב בעזרתה ובעזרת נקודות 2 & 18 את נקודות 17 & 8:

Insert

Into   T_VerticesG(Name,Place)

Select 8,dbo.Fn_IntersectionAlt(18,10,4,20)

Union All

Select 17,dbo.Fn_IntersectionAlt(2,10,4,20);

כעת ניתן לחשב את סדרת הנקודות הבאה:

Insert

Into   T_VerticesG(Name,Place)

Select 5,dbo.Fn_IntersectionAlt(1,8,2,17)

Union All

Select 6,dbo.Fn_IntersectionAlt(1,8,3,19)

Union All

Select 7,dbo.Fn_IntersectionAlt(1,8,3,12)

Union All

Select 13,dbo.Fn_IntersectionAlt(1,17,8,18)

Union All

Select 14,dbo.Fn_IntersectionAlt(1,17,3,19)

Union All

Select 16,dbo.Fn_IntersectionAlt(1,17,12,19)

Union All

Select 11,dbo.Fn_IntersectionAlt(3,12,8,18)

Union All

Select 15,dbo.Fn_IntersectionAlt(2,17,12,19);

ואחרונה חביבה - נקודה 9:

Insert

Into   T_VerticesG(Name,Place)

Select 9,dbo.Fn_IntersectionAlt(3,5,13,19);

מכיוון שהשלב הזה מבלבל ומועד לטעויות, נבדוק את הקווים השונים ונוודא שכל הנקודות הן על אותו הקו, כלומר - שהשיפועים בינהן זהים. נניח - בקו 9-13-19 נצפה שהשיפוע בי 9 ל-13 יהיה כמו השיפוע בין 13 ל-19 וכמו השיפוע בין 9-ל-19. לשם כך ניצור פונקציית שיפוע:

CREATE OR ALTER   Function [Fn_Slope]

              (@Point1 Int,

              @Point2 Int)

              Returns Float

              As

Begin

Declare       @X1 Float,

              @Y1 Float,

              @X2 Float,

              @Y2 Float;

 

Select @X1=Place.STX,

              @Y1=Place.STY

From   T_VerticesG

Where  Name=@Point1;

 

Select @X2=Place.STX,

              @Y2=Place.STY

From   T_VerticesG

Where  Name=@Point2;

 

Declare       @M Float=(@Y1-@Y2)/NullIf(@X1-@X2,0);

Return @M;

End;

ולהלן הבדיקות השונות לגבי כל אחד מהקווים, לא חובה אבל מכיוון שאני עצמי טעיתי בחישוב הנקודות תוך כתיבת הפוסט, אני חולק את נסיוני:

Select dbo.Fn_Slope(1,2) [1,2],

              dbo.Fn_Slope(2,3) [2,3],

              dbo.Fn_Slope(3,4) [3,4],

              dbo.Fn_Slope(1,4) [1,4];

             

Select dbo.Fn_Slope(4,8) [4,8],

              dbo.Fn_Slope(8,12) [8,12],

              dbo.Fn_Slope(12,17) [12,17],

              dbo.Fn_Slope(17,20) [17,20],

              dbo.Fn_Slope(4,20) [4,20];

             

Select dbo.Fn_Slope(1,18) [1,18],

              dbo.Fn_Slope(18,19) [18,19],

              dbo.Fn_Slope(19,20) [19,20],

              dbo.Fn_Slope(1,20) [1,20];

 

Select dbo.Fn_Slope(1,5) [1,5],

              dbo.Fn_Slope(5,6) [5,6],

              dbo.Fn_Slope(6,7) [6,7],

              dbo.Fn_Slope(7,8) [7,8],

              dbo.Fn_Slope(1,8) [1,8];

 

Select dbo.Fn_Slope(1,13) [1,13],

              dbo.Fn_Slope(13,14) [13,14],

              dbo.Fn_Slope(14,16) [14,16],

              dbo.Fn_Slope(16,17) [16,17],

              dbo.Fn_Slope(1,17) [1,17];

 

Select dbo.Fn_Slope(1,9) [1,9],

              dbo.Fn_Slope(9,10) [9,10],

              dbo.Fn_Slope(10,12) [10,12],

              dbo.Fn_Slope(1,12) [1,12];

                        

Select dbo.Fn_Slope(2,5) [2,5],

              dbo.Fn_Slope(5,10) [5,10],

              dbo.Fn_Slope(10,15) [10,15],

              dbo.Fn_Slope(15,17) [15,17],

              dbo.Fn_Slope(2,17) [2,17];

 

Select dbo.Fn_Slope(8,11) [8,11],

              dbo.Fn_Slope(11,10) [11,10],

              dbo.Fn_Slope(10,13) [10,13],

              dbo.Fn_Slope(13,18) [13,18],

              dbo.Fn_Slope(8,18) [8,18];

             

Select dbo.Fn_Slope(9,13) [9,13],

              dbo.Fn_Slope(13,19) [13,19],

              dbo.Fn_Slope(9,19) [9,19];

 

Select dbo.Fn_Slope(3,5) [9,13],

              dbo.Fn_Slope(5,9) [13,19],

              dbo.Fn_Slope(3,9) [9,19];

 

Select dbo.Fn_Slope(3,7) [3,7],

              dbo.Fn_Slope(7,11) [7,11],

              dbo.Fn_Slope(11,12) [11,12],

              dbo.Fn_Slope(3,12) [3,12];

 

Select dbo.Fn_Slope(12,15) [12,15],

              dbo.Fn_Slope(15,16) [15,16],

              dbo.Fn_Slope(16,19) [16,19],

              dbo.Fn_Slope(12,19) [12,19];

ניתן בשלב הזה לשלוף את 20 הנקודות מהטבלה וגם להציג את ערכי X & Y של כל אחת כך:

Select *,

              Place.STX X,

              Place.STY Y,

              Cast(Place As Varchar(Max)) PlaceV

From   T_VerticesG;

סיכום קצרצר: הכנסנו את 20 הנקודות לטבלה, וכעת יש ליצור טבלת קווים קטעים, לשמור את הקטעים בתור Geometry:

CREATE TABLE T_LinesG

              (PointFrom int NOT NULL,

              PointTo int NOT NULL,

              Line geometry NULL,

              Constraint PK_T_LinesG Primary Key Clustered(PointFrom,PointTo));

העמודות PointFrom & PointTo (מאיזו נקודה לאיזו נקודה הקו) היא לצרכי הבנה. זו לא חובה ואפשר לוותר עליהם.

כעת ניצור פרוצדורה שתקבל את הנקודות השונות לאורך הקו ותחולל מהם את הקטעים השונים המרכיבים אותו. למשל - מהנקודות לאורך הקו 9-13-19 ליצור את הקטעים 9-13, 9-19, 13-19. כדי להעביר את המספר המשתנה של נקודות בכל קו ניצור סוג נתון טבלה זמנית:

Create Type TypeVerticesG

              As Table(Name Int);

Go

והפרוצדורה שמקבל את הנ"ל, מחוללת את כל הקטעים, ומכניסה לטבלה:

Create Or Alter Procedure P_LinesG

              @T TypeVerticesG ReadOnly

              As

With T As

(Select       Format(Min(V.Name) Over(),'00')+Format(Max(V.Name) Over(),'00') GeneralLine,

              V.*

From   @T T

Inner Join T_VerticesG V

              On T.Name=V.Name)

Insert

Into   T_LinesG(PointFrom,PointTo,Line)

Select T1.Name PointFrom,T2.Name PointTo,geometry::STGeomFromText(Concat('LINESTRING (',T1.Place.STX,' ',T1.Place.STY,', ',T2.Place.STX,' ',T2.Place.STY,')'), 0) Line

From   T T1

Inner Join T T2

              On T1.Name<T2.Name

Where  Not Exists (Select   *

                                    From   T_LinesG L

                                    Where  L.PointFrom=T1.Name

                                                  And L.PointTo=T2.Name);

וכעת נכניס לטבלה את הקווים השונים: את הנקודות לאורכו נכניס למשתנה הטבלה, ונעביר אותו כפרמטר לפרוצדורה; כך עם כל הקווים:

Truncate Table T_LinesG;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (1),(2),(3),(4);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (1),(5),(6),(7),(8);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (1),(9),(10),(12);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (1),(13),(14),(16),(17);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (1),(18),(19),(20);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (4),(8),(12),(17),(20);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (2),(5),(10),(15),(17);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (3),(5),(9);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (3),(6),(10),(14),(19);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (3),(7),(11),(12);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (9),(13),(19);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (12),(15),(16),(19);

Exec   P_LinesG @T;

Go

 

Declare @T As TypeVerticesG;

Insert

Into   @T

Values (8),(11),(10),(13),(18);

Exec   P_LinesG @T;

Go

ובשעה טובה ומוצלחת הגענו לשלב בו אנחנו בודקים כמה משולשים יש:

Select T1.PointFrom,

              T1.PointTo,

              T2.PointFrom,

              T2.PointTo,

              T3.PointFrom,

              T3.PointTo,

              Cast(seg As Varchar(Max)) Triangle

From   T_LinesG T1

Inner Join T_LinesG T2

              On Cast(T1.Line As VarChar(Max))<Cast(T2.Line As VarChar(Max))

              And T1.Line.STIntersects(T2.Line)=1

Inner Join T_LinesG T3

              On Cast(T2.Line As VarChar(Max))<Cast(T3.Line As VarChar(Max))

              And T2.Line.STIntersects(T3.Line)=1

              And T1.Line.STIntersects(T3.Line)=1

Cross Apply (SELECT geometry::UnionAggregate([seg]) [seg]

                      FROM   (Select T1.Line [seg]

                                    Union All

                                    Select T2.Line [seg]

                                    Union All

                                    Select T3.Line [seg]) T) CA

Where  CA.[seg].STIsClosed()=1

              And geometry::STGeomFromText(Replace(Cast(seg As Varchar(Max)),'LINESTRING','POLYGON(')+')', 0).STArea()>0

Order By T1.PointFrom,

              T1.PointTo,

              T2.PointFrom,

              T2.PointTo,

              T3.PointFrom;

  • השליפה יוצרת Join משולש של הטבלה עם עצמה, כדי ליצור את כל השלושת האפשריות שמהוות משולשים.

  • התנאי On Cast(T1.Line As VarChar(Max))<Cast(T2.Line As VarChar(Max)) נועד למנוע יצירת אותו משולש מספר פעמים, בכל פעם בסדראחר של קודקודים.

  • התנאי T1.Line.STIntersects(T2.Line)=1 בודק שהקווים נפגשים.

  • הביטוי Cast(seg As Varchar(Max))  שב-Select מציג את משתנה Geometry (משולש במקרה הזה) טקסט קריא.

  • התנאי CA.[seg].STIsClosed()=1 שב-Where נועד לוודא שמתקבלת צורה סגורה (=משולש) משלושת הקווים (העובדה שהם שונים ונפגשים אינה ראייה לכך שזה משולש).

  • התנאי הארוך ב-Where המתחיל ב-geometry::STGeomFromText(Replace מחשב את שטח המשולש ובודק שהוא גדול מ-0. הסיבה לכך היא שהשליפה מוצאת גם משולשים "שטוחים", למשל הקטעים (11 10) (10 13) (11 13) שמהווים קו ישר, ושטחם אפס.

  • ה-Cross Apply נועד לשרשר את שלושת הקטעים עבור ה-Polygon הנ"ל.

הביצועים לא משהו, אבל השליפה הזו עושה שימוש ביכולת שונות של ה-Geometry, ולכן למרות שהדוגמה אינה שימושית וגם אינה יעילה, היא מהווה "הצגת תכלית" מעניינת לפונקציונליות שלו.

0 comments