La marche de Jarvis

Comment en arrive-t-on en business Intelligence à parler de la marche de Jarvis (aussi appelée algorithme d'emballage ou encore algorithme du papier cadeau) ?

C'est très simple : Je suis parti d'une table contenant les coordonnées géographiques des villes françaises, et je me suis interrogé sur la possibilité à partir de ces villes de construire les polygones représentant les départements (voire les régions, puis la France)

J'ai donc cherché à construire le plus grand polygone contenant un nuage de points, autrement dit, le polygone convexe circonscrit. Je me suis donc rendu sur une page dédiée à l'algorithmique géométrique d'un cours de l'école polytechnique de Montreal.

J'ai repris l'algorithme et corrigé une erreur sur :
- calculer l'angle entre l'horizontale et la droite reliant ce point à chaque autre.
Il faut remplacer l'horizontale par le vecteur défini par le point précédent trouvé et le point en cours de calcul.

J'ai dû également supprimé les cas limites induits par l'utilisation des types Float, la fonction Arccosinus étant peu décidée à me renvoyer des valeurs pour des données entrantes supérieures à 1 ou inférieures à -1

C'est à ce moment-là que je me suis rendu compte que de toute façon l'algorithme ne me donnerait pas le résultat voulu. Mais j'ai quand même souhaité aller au bout de la démarche.


Procédure Stockée :

CREATE PROCEDURE [dbo].[DisplayPolygone] @SqlEntrant AS VARCHAR(max)
AS
DECLARE @xmin AS FLOAT
DECLARE @xminsuiv AS FLOAT
DECLARE @xsuiv AS FLOAT
DECLARE @xsuiv1 AS FLOAT
DECLARE @ymin AS FLOAT
DECLARE @yminsuiv AS FLOAT
DECLARE @ysuiv AS FLOAT
DECLARE @ysuiv1 AS FLOAT
DECLARE @str AS NVARCHAR(max)
DECLARE @stralim AS NVARCHAR(max)
DECLARE @angle AS FLOAT
DECLARE @angle1 AS FLOAT
DECLARE @xprec AS FLOAT
DECLARE @yprec AS FLOAT

CREATE TABLE #Geogr (Coordonnées GEOGRAPHY)

SET @stralim = 'Insert into #Geogr ' + @SqlEntrant

EXEC sp_executesql @stralim

SET @str = ''
SET @angle = 5000

SELECT @ymin = min([Coordonnées].Lat)
FROM #Geogr

SELECT TOP 1 @xmin = [Coordonnées].Long
FROM #Geogr
WHERE [Coordonnées].Lat = @ymin

SET @str = 'Select geometry::STGeomFromText(''POLYGON((' + cast(@xmin AS VARCHAR(50)) + ' ' + cast(@ymin AS VARCHAR(50))

DECLARE ParcoursPoint CURSOR
FOR
SELECT [Coordonnées].Long
 ,[Coordonnées].Lat
FROM #Geogr
WHERE [Coordonnées].Lat <> @ymin
 OR [Coordonnées].Long <> @xmin;

OPEN ParcoursPoint

FETCH NEXT
FROM ParcoursPoint
INTO @xsuiv1
 ,@ysuiv1

WHILE @@FETCH_STATUS = 0
BEGIN
 IF @angle > acos((@xsuiv1 - @xmin) / sqrt((@xsuiv1 - @xmin) * (@xsuiv1 - @xmin) + (@ysuiv1 - @ymin) * (@ysuiv1 - @ymin)))
 BEGIN
  SET @angle = acos((@xsuiv1 - @xmin) / sqrt((@xsuiv1 - @xmin) * (@xsuiv1 - @xmin) + (@ysuiv1 - @ymin) * (@ysuiv1 - @ymin)))
  SET @xminsuiv = @xsuiv1
  SET @yminsuiv = @ysuiv1
 END

 FETCH NEXT
 FROM ParcoursPoint
 INTO @xsuiv1
  ,@ysuiv1
END

CLOSE ParcoursPoint

DEALLOCATE ParcoursPoint

SET @xsuiv = @xminsuiv
SET @ysuiv = @yminsuiv
SET @str = @str + ',' + cast(@xsuiv AS VARCHAR(50)) + ' ' + cast(@ysuiv AS VARCHAR(50))
SET @xprec = @xmin
SET @yprec = @ymin

WHILE (
  @xmin <> @xsuiv
  OR @ymin <> @ysuiv
  )
BEGIN
 SET @angle = 500

 DECLARE ParcoursPoint CURSOR
 FOR
 SELECT [Coordonnées].Long
  ,[Coordonnées].Lat
 FROM #Geogr
 WHERE [Coordonnées].Lat <> @ysuiv
  OR [Coordonnées].Long <> @xsuiv;

 OPEN ParcoursPoint

 FETCH NEXT
 FROM ParcoursPoint
 INTO @xsuiv1
  ,@ysuiv1

 WHILE @@FETCH_STATUS = 0
 BEGIN
  IF (((@xsuiv1 - @xsuiv) * (@xsuiv - @xprec) + (@ysuiv1 - @ysuiv) * (@ysuiv - @yprec)) / (sqrt((@xsuiv1 - @xsuiv) * (@xsuiv1 - @xsuiv) + (@ysuiv1 - @ysuiv) * (@ysuiv1 - @ysuiv)) * sqrt((@xsuiv - @xprec) * (@xsuiv - @xprec) + (@ysuiv - @yprec) * (@ysuiv - @yprec)))) <= 1
   AND (((@xsuiv1 - @xsuiv) * (@xsuiv - @xprec) + (@ysuiv1 - @ysuiv) * (@ysuiv - @yprec)) / (sqrt((@xsuiv1 - @xsuiv) * (@xsuiv1 - @xsuiv) + (@ysuiv1 - @ysuiv) * (@ysuiv1 - @ysuiv)) * sqrt((@xsuiv - @xprec) * (@xsuiv - @xprec) + (@ysuiv - @yprec) * (@ysuiv - @yprec)))) >= - 1
  BEGIN
   SET @angle1 = ACOS(((@xsuiv1 - @xsuiv) * (@xsuiv - @xprec) + (@ysuiv1 - @ysuiv) * (@ysuiv - @yprec)) / (sqrt((@xsuiv1 - @xsuiv) * (@xsuiv1 - @xsuiv) + (@ysuiv1 - @ysuiv) * (@ysuiv1 - @ysuiv)) * sqrt((@xsuiv - @xprec) * (@xsuiv - @xprec) + (@ysuiv - @yprec) * (@ysuiv - @yprec))))

   IF @angle > @angle1
   BEGIN
    SET @angle = @angle1
    SET @xminsuiv = @xsuiv1
    SET @yminsuiv = @ysuiv1
   END
  END

  FETCH NEXT
  FROM ParcoursPoint
  INTO @xsuiv1
   ,@ysuiv1
 END

 CLOSE ParcoursPoint

 DEALLOCATE ParcoursPoint

 SET @xprec = @xsuiv
 SET @yprec = @ysuiv
 SET @xsuiv = @xminsuiv
 SET @ysuiv = @yminsuiv
 SET @str = @str + ',' + cast(@xsuiv AS VARCHAR(50)) + ' ' + cast(@ysuiv AS VARCHAR(50))
END

SET @str = @str + ',' + cast(@xmin AS VARCHAR(50)) + ' ' + cast(@ymin AS VARCHAR(50)) + '))'',4326)'

EXEC sp_executesql @str
GO

Quelques exemples :

La france sans la Corse :

Le Nord :

Conclusion :

Cet algorithme ne sert à rien dans notre cas. Il faudrait représenter les villes comme elles-mêmes étant des polygones et faire un union.