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 :
.SQLCode { font-size: 13px; font-weight: bold; font-family: monospace;; white-space: pre; -o-tab-size: 4; -moz-tab-size: 4; -webkit-tab-size: 4; } .SQLComment { color: #00AA00; } .SQLString { color: #AA0000; } .SQLFunction { color: #AA00AA; } .SQLKeyword { color: #0000AA; } .SQLOperator { color: #777777; }
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.
Monsieur Joubert, peut-on même dire que cet algorithme ne sert à rien du tout?
Et sincérement, Blogspot, en 2011? Blah!