Retrouver la succession des sommets d'un polygone

[brun]

Bonjour,

J'ai un polygone de n côtés dont je connais les coordonnées des points-côtés. Comment connaître l'ordre de succession de ces points sur le polygone, qui peut être connexe ou non ? Merci pour votre aide.

[Ben314]

Salut,
Y'a un truc qui m'échape : si ton polygone peut être connexe ou non, je vois vraiment pas comment tu va pouvoir retrouver quoi que ce soit dans l'ordre des sommets.
Pour moi, c'est un peu comme si tu demandait dans quel ordre tu as rangé les entiers de 1 à 10 en donnant comme seule information "il est possible qu'ils ne soient pas dans l'ordre" : ç'est un peu "short" comme info...


P.S. En plus, un polygône "non connexe", je suis pas sûr que ça ait bien du sens ce truc là : si c'est pas connexe, c'est que tu as plusieurs polygône...

[brun]

Salut,
Y'a un truc qui m'échape : si ton polygone peut être connexe ou non, je vois vraiment pas comment tu va pouvoir retrouver quoi que ce soit dans l'ordre des sommets.
Pour moi, c'est un peu comme si tu demandait dans quel ordre tu as rangé les entiers de 1 à 10 en donnant comme seule information "il est possible qu'ils ne soient pas dans l'ordre" : ç'est un peu "short" comme info...


P.S. En plus, un polygône "non connexe", je suis pas sûr que ça ait bien du sens ce truc là : si c'est pas connexe, c'est que tu as plusieurs polygône...

J'ai mal exprimé en effet mon problème, j'ai n points sur un plan, je veux une méthode qui permette de relier ces n points par des segments avec les contraintes sivantes:

1°) aucun segment ne se coupe avec un autre

2°) et pour un point quelconque, il n' a que deux segments issus de ce point (ni un de plus ni un de moins). Visuellement et humainement, on sait le faire quand on voit les points sur le plan. Mais quel algorithme informatique peut être mis en oeuvre pour qu'un ordinateur puisse trouver au moins une solution voire toutes ? Merci

[fatal_error]

slt,

ce que tu cherches s appele l enveloppe convexe.
Je crois que tu peux te referer aux Convex Hull algorithms

[Sylviel]

heu... pour moi l'enveloppe convexe c'est le plus petit convexe contenant tous les points. Cela ne permet pas de relier tous les points 2 à 2 sans que les côtés se croisent...

[fatal_error]

hum, oui effectivement, apres, il faut pas grand chose pour joindre les points internes!

un ptit 2-opt, et puis c est bon!

edit: cela dit, ca sert pas forcement de passer par l enveloppe convexe du coup

[Ben314]

Je pense (à vérifier...) qu'il suffit de prendre un point bien choisi O (l'isobarycentre des points doit faire l'affaire) puis de trier les points Mi en fonction de l'angle ( Ox, OMi ) mesuré de 0 à 2pi à l'aide d'un quelconque algorithme de tri et on aura UNE des solutions (il me semble plus que probable qu'il y ait en général plusieurs solutions...)
En plus, le polygône obtenu sera "étoilé" (pour ceux qui savent ce que ça veut dire...)

Je laisse les férus d'info faire les tests... :zen:

[fatal_error]

voici un exemple avec 2opt

Code: Tout sélectionner





 
[961,964],
[120,802],
[541,978],
[10,923],
[17,616],
[584,933],
[405,424],
[710,803],
[590,410],
[203,592]




function d(a,b){
  return Math.sqrt(Math.pow(a[0]-b[0], 2)+Math.pow(a[1]-b[1], 2));
}
//remove crossing segments
function twoOpt(tour){
  function updateTour(tour, i1, j1){
    var cities=tour.slice(0);
    var first=tour.slice(0, i1);
    var last = tour.slice(j1);
    var ji1=tour.slice(i1, j1).reverse();
    var newT = first.concat(ji1).concat(last);
    return newT;
  }
 
  var better = false;
  var t=tour;
  var newT=t;
  for(var j=1; jd(t[j], t[i1])+ d(t[0], t[j1])){
      var cities=t.slice(0);
      var newT = cities.slice(0, j1);
      newT=newT.concat(cities.slice(j1, i1+1).reverse());
      better=true;
    }
  }
  for(var i=0; i

//only useful for printing.
function gMap(canvas,op){
  var ctx = canvas.getContext('2d');
  function scale(cities){
    var xs=cities.map(x=>x[0]), ys=cities.map(x=>x[1]);
    var xmin=Math.min.apply(null, xs), xmax=Math.max.apply(null, xs);
    var ymin=Math.min.apply(null, ys), ymax=Math.max.apply(null, ys);
    return cities.map((city)=>[(city[0]-xmin)/xmax*300, (city[1]-ymin)/ymax*300]);
  }
  return {
    draw:function(cities){
      cities=scale(cities);
      ctx.clearRect(0,0,canvas.width,canvas.height);
      ctx.beginPath();
      var [x,y]=cities.slice(-1)[0];
      cities.forEach(function(city){
        ctx.moveTo(x,y);
        [x,y] = city;
        ctx.lineTo(x, y);
        ctx.stroke();
      });
      ctx.stroke();
      ctx.closePath();
    }
  }
}


function getPolygone(cities){
  var nbTries=0;
  var res={tour:cities,better:true};
  while(res.better &&nbTries

//main.js
function oneTag(t){return document.getElementsByTagName(t)};
var mapRef=gMap(oneTag('canvas')[0]);
var map=gMap(oneTag('canvas')[1]);
window.onload=function(){
  oneTag('form')[0].onsubmit=function(e){
    try{
      var cities=JSON.parse('['+this.citiesLocation.value+']');
      mapRef.draw(cities);
      var sortedCities=getPolygone(cities);
      map.draw(sortedCities);
    }catch(e){
      console.log(e);
    }
    e.preventDefault();
    return false;
  }
}





Et avec la methode de Ben

Code: Tout sélectionner





 
[15,361],
[272,295],
[55,16],
[971,79],
[653,919],
[842,659],
[143,46],
[343,708],
[314,202],
[391,213]





function getAngle(A,B,O){
  var [ux,uy]=[A[0]-O[0],A[1]-O[1]];
  var [rx,ry]=[B[0]-O[0],B[1]-O[1]];
  return Math.atan2(uy*rx-ux*ry,ux*rx+uy*ry);
}
function Ben314(tour){
  tour=tour.map(x=>[+x[0],+x[1]]);
  var res=tour.reduce((a,b)=>{return [a[0]+b[0], a[1]+b[1]]});
  var barycenter=[res[0]/tour.length, res[1]/tour.length];
  var t=tour[0];
  return tour.map(x=>{
    return {x:x,angle:getAngle(x,t,barycenter)}
  }).sort((a,b)=>a.angle-b.angle).map(x=>x.x);
}


//only useful for printing.
function scale(cities){
  var xs=cities.map(x=>x[0]), ys=cities.map(x=>x[1]);
  var xmin=Math.min.apply(null, xs), xmax=Math.max.apply(null, xs);
  var ymin=Math.min.apply(null, ys), ymax=Math.max.apply(null, ys);
  return cities.map((city)=>[(city[0]-xmin)/xmax*300, (city[1]-ymin)/ymax*300]);
}
function gMap(canvas,op){
  var ctx = canvas.getContext('2d');
  return {
    draw:function(cities){
      cities=scale(cities);
      ctx.clearRect(0,0,canvas.width,canvas.height);
      ctx.beginPath();
      var [x,y]=cities.slice(-1)[0];
      cities.forEach(function(city){
        ctx.moveTo(x,y);
        [x,y] = city;
        ctx.lineTo(x, y);
        ctx.stroke();
      });
      ctx.stroke();
      ctx.closePath();
    }
  }
}


function getPolygone(cities){
  return Ben314(cities);
}


//main.js
function oneTag(t){return document.getElementsByTagName(t)};
var mapRef=gMap(oneTag('canvas')[0]);
var map=gMap(oneTag('canvas')[1]);
window.onload=function(){
  oneTag('form')[0].onsubmit=function(e){
    try{
      var cities=scale(JSON.parse('['+this.citiesLocation.value+']'));
      mapRef.draw(cities);
      var sortedCities=getPolygone(cities);
      map.draw(sortedCities);
    }catch(e){
      console.log(e);
    }
    e.preventDefault();
    return false;
  }
}





Horrible les angles, perdu deux heures avec l'arctangente è_é. J'ai toujours pas compris pourquoi
atan(x) différait de atan2(y,x) mais bon, le ventre remporte le combat..

[Ben314]

Sinon, pour "classer" les points par angle, tu peut éviter de calculer l'angle (donc éviter la fonction arctangente) en utilisant le fait que, si et alors (qui en fait vaut si tu as normalisé tes vecteurs) et classer par rapport à , c'est pareil que de classer par rapport à .
Le seul problème, c'est si et où et ...

[fatal_error]

coolos la comparaison avec y/(1+x)!!!
Au revoir l'arctangente et les prises de tete modulo pi

Le seul problème, c'est si où et ...

d'apres ton égalité au dessus,
vu que x=rcos(theta) et y=rsin(theta)
si on norme, on a pour y=0, x=+-1
comme de toute facon on compte de -pi à pi, c'est juste que le point il est soit au début, soit à la fin de la liste de points.

Comme c'est un polygone, ca change rien!

[fatal_error]

bon en fait, si ca change un peu


L'algo que je mets en place c'est
soit un point O (le barycentre)
soit un point A.

Je considère le repère (O,i,j) orthonormé.
J'exprime mon point A en A' dans ce nouveau repère.
Donc A'=A+O

Et je calcule

tan(theta/2)=A'_y/(A'_x+sqrt(A.A))

Mais vraisemblablement, les deux points extremes ont décidé de tout couper

edit: il fallait faire une soustraction :mur:
A'=A-O

[Ben314]

Il a quand même une "salle tronche" le polygone en question.
(Mais je sais pas si on peut en faire un "plus joli" avec des points "en bordel" dans le plan...)

[fatal_error]

par exemple, avec le 2opt, on obtient


mais j'aime bien l'étoilé, c'est juste que là ca rend pas très bien sur cette série de point, sur d'autres séries, ca fait un peu vortex :zen: