Graham Scan Algorithm in SQL Server

Problem

The Graham scan algorithm is used to find the convex hull of a finite set of points in the plane. In other words, the smallest convex polygon that encloses all points. Is it possible to implement it in SQL Server without the use of external tools?

Solution

The Graham scan algorithm is used to:

  1. Computer graphics and game development
  2. Geographic information Systems (GIS)
  3. Robotics and motion planning
  4. Image processing and computer vision
  5. Data analysis and computational geometry
  6. Telecommunications and sensor networks

Graham Scan Algorithm Logic

The basic idea of the algorithm is:

  1. Choose a pivot point, the one that has the lowest y-coordinate and the lowest x-coordinate.
  2. Sort points by its polar angle and the distance from the pivot point.
  3. Scan and discard concavities, at each step, check the orientation of the last two points on the stack and the new point.
  4. The result contains the convex hull in counterclockwise order.

Implementing Algorithm in SQL Server

Let’s create a few objects and then do a sample run.

User-defined table type

-- MSSQLTips (TSQL)
 
CREATE TYPE [dbo].[uttPoints] AS TABLE(
    [n] [int] IDENTITY(1,1) NOT NULL,
    [x] [float] NOT NULL,
    [y] [float] NOT NULL
)
GO

Table-valued function

-- =============================================
-- Author:         SCP - MSSQLTips
-- Create date:    20260113
-- Description:    Graham scan algorithm
-- =============================================
CREATE OR ALTER FUNCTION [dbo].[tvfGrahamScan] 
            (@Points dbo.uttPoints READONLY)
RETURNS         @Hull    
    TABLE    ([n] int IDENTITY
            ,[x] float
            ,[y] float) 
WITH EXECUTE AS CALLER 
AS
BEGIN
 
    DECLARE  @x0 float
            ,@y0 float
            ,@ax float
            ,@ay float
            ,@bx float
            ,@by float
            ,@cx float
            ,@cy float
            ,@n int
            ,@pivot int;
 
    SELECT TOP 1 @x0 = x
                ,@y0 = y
                ,@pivot = n
        FROM     @Points
        ORDER BY x
                ,y;
 
    INSERT INTO         @Hull
        VALUES         (@x0,@y0) 
 
    DECLARE cursorTab CURSOR FAST_FORWARD READ_ONLY FOR 
        SELECT         x
                    ,y
            FROM     @Points
            WHERE     n <> @pivot
            ORDER BY ATN2(y - @y0, x - @x0)
                    ,SQUARE(x - @x0) + SQUARE(y - @y0);
 
    OPEN cursorTab
        FETCH NEXT FROM cursorTab INTO @cx,@cy;
 
        WHILE @@FETCH_STATUS = 0 BEGIN
 
            SET @n = (SELECT COUNT(*) FROM @Hull);
 
            IF     @n >= 2 BEGIN
                SELECT TOP 1 @bx = x
                            ,@by = y
                    FROM     @Hull
                    ORDER BY n DESC;
 
                SELECT         @ax = x
                            ,@ay = y
                    FROM     @Hull
                    ORDER BY n DESC
                    OFFSET 1 ROWS FETCH NEXT 1 ROWS ONLY;
 
                IF ((@bx - @ax) * (@cy - @ay) - (@by - @ay) * (@cx - @ax)) <= 0
                    DELETE FROM     @Hull
                        WHERE     x = @bx AND
                                    y = @by;
            END
 
            INSERT INTO     @Hull
                VALUES     (@cx,@cy);
 
            FETCH NEXT FROM cursorTab INTO @cx,@cy;
        END
    CLOSE cursorTab
    DEALLOCATE cursorTab
 
    RETURN;
END
GO

Example Graham Scan Algorithm in SQL Server

-- MSSQLTips (TSQL)
 
DECLARE         @Points AS dbo.uttPoints;
 
DECLARE         @Hull AS 
    TABLE   (n int IDENTITY
            ,x float
            ,y float);
 
INSERT INTO      @Points
    VALUES       (0, 3)
                ,(1, 1)
                ,(2, 2)
                ,(4, 4)
                ,(0, 0)
                ,(1, 2)
                ,(3, 1)
                ,(3, 3);
 
INSERT INTO @Hull
    SELECT       x
                ,y 
        FROM     [dbo].[tvfGrahamScan] (@Points);
 
-- Closing the polygon to plot
INSERT INTO         @Hull
    SELECT TOP 1 x
                ,y
        FROM     @Hull;
 
SELECT * FROM @Hull;
 
DECLARE      @poly geometry
            ,@w nvarchar(MAX)
            ,@p int = 1;
 
SELECT     @w = 'POLYGON((' + STRING_AGG(CAST(x AS nvarchar(10)) + ' ' + CAST(y AS nvarchar(10)), ', ') + '))'
    FROM @Hull;
 
SET @poly = geometry::STGeomFromText(@w, 0);
 
DECLARE @Ratio float = 0.15;
 
SELECT         'Polygon' AS Id
    ,NULL AS x
    ,NULL AS y
    ,@poly.STBoundary() AS geom
 
    UNION ALL
 
SELECT       CONVERT(nvarchar(10),n)
            ,x
            ,y
            ,([geometry]::Point([x],[y],(0))).STBuffer(@Ratio)
    FROM     @Points;
GO

Resulting in

Plotted points and Hull

Next Steps

  • Instead of the use of Atn2 to sort the values it is also possible to use polar cross-product ordering.
  • WIKIPEDIA – Graham scan

Related Posts

Leave a Reply

Your email address will not be published. Required fields are marked *