Création de carte avec Delphi

Version imprimable

03/02/2007, 22h23
accoustic

Création de carte avec Delphi

Salut tout le monde,

j'essaie de programmer un logiciel qui va pouvoir produire une carte à partir de certaines donnés que je lui donne.

Mais voilà où je suis coincé, j'ai une Timage blanche avec quelques pixels coloriés dessus. Mon but serait de créé des secteurs à partir de ces pixels.

j'essaie pour le moment de relier chaque pixel colorié au pixel qui lui est le plus proche afin que des zones se découpe. Malgré mes nombreuses tentative avec l'aide du théorème de pithagorre, c'est sans succès.

Si quelqu'un aurait une idée, ce serait très apprécié!

MERCI!
03/02/2007, 22h32
macumba

Je ne comprends pas bien à quel niveau tu bloques.
- sur la façon de dessiner sur la TImage
- ou sur l'algorythme
03/02/2007, 22h42
accoustic

sur l'agorithme,

Je ne suis pas capable d'identifier le pixel le plus proche de celui que j'évalue.....et ce n'est pas faute d'avoir essayer
04/02/2007, 01h03
macumba

Il faudrait que tu ailles faire un tour dans la section algorithme.
Ton problème est certainement celui du voyageur de commerce, un problème vieux comme la programmation ou presque... ;)

Tu peux consulter également l'algo de Dijkstra:

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
04/02/2007, 04h15
accoustic

Ouais c'est un algo du même genre,

MAIS je ne peux pas utiliser celui-ci, pcq'il regroupe la totalité des points dans un seul et même secteur. Moi, je doit pouvoir créer un nombre infinie de secteur.

En gros, si quelqu'un aurait une idée pour pouvoir :

-Prendre un point dans une tImage,
-Trouver l'autre point le plus proche de celui-ci.
-Dessiner une ligne du premier au deuxième point

Si quelqu'un aurait une idéé pour une de ces étapes...

MERCI!

je vais vous montrez ce que j'ai essayer,

- toutes le coordonné de chaque point de couleur de la TImage sont dans deux TListbox.....une pour les coordonnées X, l'autre pour les Y

voila le code (qui ne fonctionne pas bien entendu...)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
procedure TForm1.Button15Click(Sender: TObject);
var
indx1, indx2 : integer;
numeroitemcomparemaster, numeroitemcompareslave : integer;
distance : integer;
catheteX, catheteY : real;
PlusCourteDistance : integer;
PlusCourteDistanceX, PlusCourteDistanceY : integer;
coorX, coorY : integer;
begin
numeroitemcomparemaster := 0;
 For indx1 := 1 to ListboxX.items.count do
  begin
  numeroitemcompareslave := 0;
  plusCourteDistance := 40000;
  coorX:= StrToInt(ListBoxX.items[numeroitemcomparemaster]);
  coorY:= StrToInt(ListBoxY.items[numeroitemcomparemaster]);
  For indx2 := 1 to ListboxX.items.count do
  begin
  catheteX := ( (StrToFloat(ListBoxX.Items[numeroitemcomparemaster])) -
  (StrToFloat(ListboxX.items[numeroitemcompareslave])) );
  catheteY := ( (StrToFloat(ListBoxY.Items[numeroitemcomparemaster])) -
  (StrToFloat(ListboxY.items[numeroitemcompareslave])) );
  Distance := Round(sqrt(
  (CatheteX*CatheteX)  +  (CatheteY*CatheteY)
  ));
  If (pluscourteDistance = 40000) or (Distance < pluscourtedistance) then
   begin
   PlusCourteDistance := Distance;
   PlusCourteDistanceX := StrToInt(ListboxX.Items[numeroitemcompareslave]);
   PlusCourteDistanceY := StrToInt(ListboxY.Items[numeroitemcompareslave]);
   end;
  numeroitemcompareslave := numeroitemcompareslave + 1;
  end;
  //dessin des lignes
  Form2.Image2.Canvas.Brush.color := clred;
  Form2.Image2.Canvas.MoveTo(coorX, coorY);
  Form2.Image2.Canvas.LineTo(PlusCourteDistanceX, PlusCourteDistanceY);
  //fin
  numeroitemcomparemaster := numeroitemcomparemaster + 1;
  end;
end;

Tu devrais essayer ca plutot

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
procedure TForm1.Button1Click(Sender: TObject);
var
  indx1, indx2 : integer;
  numeroitemcomparemaster, numeroitemcompareslave : integer;
  distance : integer;
  catheteX, catheteY : real;
  PlusCourteDistance : integer;
  PlusCourteDistanceX, PlusCourteDistanceY : integer;
  coorX, coorY : integer;
begin
  numeroitemcomparemaster := 0;
  For indx1 := 1 to ListboxX.items.count do
  begin
    numeroitemcompareslave := 0;
    plusCourteDistance := 0;
    coorX:= StrToInt(ListBoxX.items[numeroitemcomparemaster]);
    coorY:= StrToInt(ListBoxY.items[numeroitemcomparemaster]);
    For indx2 := 1 to ListboxX.items.count do
    begin
      catheteX := ( (StrToFloat(ListBoxX.Items[numeroitemcomparemaster])) -
                  (StrToFloat(ListboxX.items[numeroitemcompareslave])) );

      catheteY := ( (StrToFloat(ListBoxY.Items[numeroitemcomparemaster])) -
                  (StrToFloat(ListboxY.items[numeroitemcompareslave])) );

      Distance := Round(sqrt((CatheteX*CatheteX)  +  (CatheteY*CatheteY)));
      If (pluscourteDistance = 0) or (Distance < pluscourtedistance) then      begin
        PlusCourteDistance := Distance;
        PlusCourteDistanceX := StrToInt(ListboxX.Items[numeroitemcompareslave]);
        PlusCourteDistanceY := StrToInt(ListboxY.Items[numeroitemcompareslave]);
      end;
      numeroitemcompareslave := numeroitemcompareslave + 1;
    end;
    //dessin des lignes
    Image1.Canvas.Brush.color := clred;
    Image1.Canvas.MoveTo(coorX, coorY);
    Image1.Canvas.LineTo(PlusCourteDistanceX, PlusCourteDistanceY);
    //fin
    numeroitemcomparemaster := numeroitemcomparemaster + 1;
  end;
end;

Par contre ca ne dessine pas de secteurs. A mon avis il faudrait que tu traces les 3 lignes vers chacun des points les plus proches pour dessiner des secteurs.

J'ai pas compris ce que tu entendais par Prendre un point dans une TImage?
Ca veut dire plein de chose et pas grand chose.

04/02/2007, 11h58
Gaadek

Pour répondre en vrac:

-Prendre un point dans une tImage

Ca ne semble pas compliqué, encore faut-il savoir ce que tu entends exactement par "prendre un point dans une TImage"

-Trouver l'autre point le plus proche de celui-ci

Je pense qu'avec les calculs vectoriels, tu devrais t'en sortir assez facilement

-Dessiner une ligne du premier au deuxième point

En utilisant le Canvas du TImage, c'est assez simple également

Pour tout ce qui est manipulation d'image, je te conseille de passer par un tableau que directement par ton composant image, tu gagneras en temps de traitement
06/02/2007, 17h48
random

une carte est définie par un contour
c'est à dire une liste de points ordonnés

en introduisant les points dans l'ordre et en rajoutant le premier point à la fin de la ligne on obtient un polygone ferme, on peut donc définir un secteur par
un chemin qui s'arrête quand le dernier point est égal au premier

nb si un secteur passait deux fois par le même point, il suffirait de donner une infime variation aux coordonnés du second passage pour conserver l'algo

nb un polygone fermé peut recevoir une couleur de fond
07/02/2007, 09h48
sovitec
Bonjour,

J'ai 2 remarques :
1. Se contenter de tracer un trait entre chaque point et son plus proche voisin ne va pas aboutir à un ensemble de secteur mais à ce que l'on appelle une forêt en théorie des graphes (un ensemble de graphes sans cycle).
2. Je pense que ce que tu recherches est la triangulation de Delaunay
Bon courage
08/02/2007, 03h29
accoustic

oui c'est proche de la triangulation de delaunay.

Mais ce que je cherche resemblerait plus a une méthode de triangulation par sous-triangulations...comme l'image suivante.

http://www.kaddour.com/chap4/image85.gif

Le but ultime de tout sa serait de créer une cartes isorithimique a partir d'un nuage de points.

Donc ce que je ferais a la suite de la triangulation, ce serait de tracer le plus petit élipse autour de chaque secteur, et pour chacun des points du secteurs, je ferait la moyenne du point lui étant le plus proche dans l'élipse qui l'entour. Mais avec cette méthode j'arriverais encore avec le même problème de trouver le point le plus proche d'un autre.... En fait je tente d'appliquer pythagore au coordonnées mais j'ai de la difficulté niveau programmation (je développe en delphi pascal...).

Si quelqu'un aurait une idée ou un conseil, j'apprécierais!

Merci!
08/02/2007, 11h27
Rakken

Si ton point bloquant au final, c'est juste de trouver le point qui est le plus proche d'un autre, avec un nuage de point comme dans ton exemple (c'est a dire dans trop de points), une méthode simple est de calculer pour chaque point, sa distance avec tous les autres.
Tu as la formule ici.

Tu n'a plus qu'a parcouris chaque point, et trouver son copain le plus proche parmis tous les autres.

C'est un calcul un peu lourd, donc si tu as un nuage d'un million de point, il y a sans doute mieux, mais pour un exemple comme celui que tu as donné, ca se fait sans problème.
08/02/2007, 13h01
Sivrît

Un quadtree pourrait peut-être alléger le coût de la recherche du plus proche voisin, même si ce sera délicat à mettre en place.