לפני זמן מה פרסמתי פתרון 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
V.*
From @T T
Inner Join T_VerticesG V
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
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, ולכן למרות שהדוגמה אינה שימושית וגם אינה יעילה, היא מהווה "הצגת תכלית" מעניינת לפונקציונליות שלו.