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 :

.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.

Publié dans SQL Server
2 comments on “La marche de Jarvis
  1. Fleid dit :

    Monsieur Joubert, peut-on même dire que cet algorithme ne sert à rien du tout?

  2. fleid dit :

    Et sincérement, Blogspot, en 2011? Blah!

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

Microsoft
Communauté
PASS
Twitter
Follow La BI et les outils Microsoft on WordPress.com
%d blogueurs aiment cette page :