AIDEZ MOI SVP Sommets d'un polygone Fermé

Question

SVP !! Par un prog java,je parviens à récupérer les coordonnées de tous les points de tout polygone (convexes ou non):
(en fait ces polygones constituent l'enveloppe extérieur(contour) d' images).
mon PROBLEME SVP :
je souhaite récupérer dans mon nuage de point UNIQUEMENT les sommets .
Sauriez vous comment y parvenir?
NB : je programme avec JAVA.
Merci d'avance !!

HackTrack · Answer

Qu'appelles-tu les sommets?

Ces 4 points?
Le point dont la valeur de l'abcisse est la plus élevée
Le point dont la valeur de l'abcisse est la moins élevée
Le point dont la valeur de l'ordonnée est la plus élevée
Le point dont la valeur de l'ordonnée est la moins élevée

Ou plutôt chaque point délimitant une rupture dans un segment (un angle)?

HackTrack
Java Developer
;-)

teebo · Answer

HAckTrack, les sommets d'un polygone sont ses "angles"...
La propriete d'un angle est de changer de direction
Si 3 de tes points consecutifs ne sont pas alignes, le point mediant est alors le sommet...Remarque que si cette methode prend tu temps (en foncion du nombre de points de ton polygone) tu peux privilegier la vitesse a la precision en ne prenant qu'un point sur 2 ou 3 (ou plus,mais tu perds vite en precision...)

J'espere que ca va etre utile...
Bon courage...

*,*
\_/

HackTrack · Answer

Cette classe te permet d'initialiser une liste de points et de tester le fonctionnement de la classe PolySummitFinder

/*
* PolySummitFinderLauncher.java
*
* Created on July 10, 2002, 8:12 AM
*/

package CCM;
import java.util.*;
import java.awt.Point;

/**
*
* @author HackTrack
* @version 1.0
*/
public class PolySummitFinderLauncher {

public static void main(String args[]) {
ArrayList allPoints = new ArrayList();
allPoints.add(new Point(0,0));
allPoints.add(new Point(0,3));
allPoints.add(new Point(0,6));
allPoints.add(new Point(3,6));
allPoints.add(new Point(6,6));
allPoints.add(new Point(11,6));
allPoints.add(new Point(8,2));
allPoints.add(new Point(6,2));
allPoints.add(new Point(4,2));
allPoints.add(new Point(3,2));
PolySummitFinder finder = new PolySummitFinder();
List summits = finder.findSummits(allPoints);
Iterator it = summits.iterator();
int summitCounter = 1;
while(it.hasNext()){
Point p = (Point)it.next();
System.out.println("Sommet " + summitCounter +": ");
System.out.println(" x = " + p.getX());
System.out.println(" y = " + p.getY());
}
System.out.println("Terminé!");
}
}

------------------------------------------------------------------
Cette classe te permet de récupérer une liste de sommets hors d'une liste de points grâce à la méthode findSummit.

/*
* PolySummitFinder.java
*
* Created on July 10, 2002, 8:10 AM
*/

package CCM;
import java.awt.Point;
import java.util.*;

/**
*
* @author HackTrack
* @version 1.0
*/
public class PolySummitFinder {
private ArrayList summits;

public PolySummitFinder() {
summits = new ArrayList();
}

public List findSummits(ArrayList points){
int pointsCount = points.size();
if(pointsCount<3){
System.out.println("Le nuage de points doit compter 3 points au minimum");
}else{
for(int i=0 ; i<pointsCount-2 ; i++){
checkAlignment((Point)points.get(i),(Point)points.get(i+1),(Point)points.get(i+2));
}
checkAlignment((Point)points.get(pointsCount-2),(Point)points.get(pointsCount-1),(Point)points.get(0));
checkAlignment((Point)points.get(pointsCount-1),(Point)points.get(0),(Point)points.get(1));
}
return summits;
}

private void checkAlignment(Point p1, Point p2, Point p3){
//Calcul des valeurs de a et b dans y=ax+b pour les points p1 et p2
if(p1.getX()-p2.getX()==0){
if(p3.getX()!=p1.getX()){
addSummit(p2);
}
}else{
double a = (p1.getY()-p2.getY())/(p1.getX()-p2.getX());
double b = p1.getY()-a*p1.getX();
if(p3.getY()!=a*p3.getX()+b){
addSummit(p2);
}
}
}

private void addSummit(Point newSummit){
summits.add(newSummit);
}
}

;-)
HackTrack

teebo · Answer

Toutes ces jolies reponses et personne pour dire merci  :-(*,*\_/

choubaka · Answer

sidérantChouba"Les Schtroumpfs sont mes amis passk'ils sont petits"

andré · Answer

je reçois à l'instant même vos précieuses réponses et je vous en remercie. j'essaye les differentes methodes pour vous faire part du resultat.
Merci en particulier à HackTrack et à Teebo .
cordialement.

teebo · Answer

Haaa :-)))))))))*,*\_/

André · Answer

je tiens à confirmer le bon fonctionnement du programme de
HackTrack ! idée géniale,programme génial qui marche dès le premier test!!
Merci encore à HackTrack , à Teebo et à Choubaka!
Bravo HackTrack !!
cordialement
André

pamela · Answer

j'ai aussi testé le programe de HackTrack et je constate qu'il ne marche pas pour les polygone ayant 1 ou plusieurs courbes comme côtés.
donc j'invite André à revérifier le bon fonctionnement du dit programme.

andré · Answer

merci à Marden pour la méthode proposée.
comme la compris HackTrack nous disposons au depart un ensemble de points non ordonnés décrivant le contour (avec éventuellement des bruits) d'une image et l'on souhaite avoir les sommets .il est à noter que le cas où les côtés sont des segments a été résolu par HackTrack .
cordialement

Eaulive · Answer

Oulàlà quel mal de bloc...après tout ça je retourne au café moi...Ils sont fous ces informaticiens ;-);-);-)Eaulive...Vaut mieux un p'tit piment qu'un avion en plastique

EauLiveLess · Answer

EauLive?????????????

HackTrack · Answer

Chose promise, chose dûe!

Voici le code de l'utilitaire qui permet de trouver, sur base d'un nuage de points fournis, les points représentant les sommets du polygône irrégulier contenant tout le nuage de point.

Le package (que j'ai nommé: be.hacktrack.points) contient classes:
- PointsAreaTester qui permet de tester le package
- CircularQueue: implémentation d'une queue circulaire utilisée, dans ce package, pour stocker les sommets du polygône.
- QueueInsertException: exception jetée lors de l'insertion d'un élément dans une CircularQueue
- QueueReadException: exception jetée lors de la lecture d'un élément dans une CircularQueue
- SortException: exception jetée lors de la recherhce et du tri des sommets du polygône (par exemple: si le nombre de points à trier est strictement inférieur à 3)
- PointsArea: classe "principale" disposant de plusieurs méthodes publiques.

* public ArrayList sortPoints(Point2D.Double[] points) throws SortException: extrait les sommets du polygône et les trie suivant le sens trigonométrique
* public CircularQueue insertSummit(Point2D.Double newPoint, Point2D.Double p1, Point2D.Double p2) throws QueueReadException, QueueInsertException: insére le point newPoint entre les sommets p1 et p2
* public boolean removeSummit(Point2D.Double summitToRemove): enlève un sommet au polygône et replace ce sommet dans la liste des points non triés. Renvoi 'true' si le sommet a bien été enlevé
* public CircularQueue deleteSummit(Point2D.Double summitToDelete): supprime définitivement le sommet. Le point est alors 'perdu'
* public List getUnsortedPoint(): renvoie la liste des points non triés
* public int summitCount(): renvoie le nombre de sommets du polygône
* public Point2D.Double getNextSummit(): renvoie le sommet suivant dans le sens trigonométrique
* public Point2D.Double getNextSummit(Point2D.Double aSummit) throws QueueReadException: renvoie le sommet suivant 'aSummit' dans le sens trigonométrique
* public Point2D.Double getPreviousSummit(): renvoie le sommet précédent dans le sens trigonométrique
* public Point2D.Double getPreviousSummit(Point2D.Double aSummit) throws QueueReadException: renvoie le sommet précédant 'aSummit' dans le sens trigonométrique

Assez parlé, voici le code des différentes classes.
Si qqn est intéressé par ce package, qu'il me laisse son adresse e-mail et je le lui envoie.

------------------------ Classe SortException ---------------------------

package be.hacktrack.points;

/**
*
* @author HackTrack
* @version 1.0
*/
public class SortException extends java.lang.Exception {

public SortException() {
super("Minimum 3 points must be given to perform sort");
}
}

----------------------- Classe QueueInsertException -------------------

package be.hacktrack.points;

/**
*
* @author HackTrack
* @version 1.0
*/
public class QueueInsertException extends Exception{

/** Creates new QueueInsertException */
public QueueInsertException(String message) {
super(message);
}
}

------------------- Classe QueueReadException ------------------------
package be.hacktrack.points;

/**
*
* @author HackTrack
* @version 1.0
*/

public class QueueReadException extends java.lang.Exception {

public QueueReadException(String msg) {
super(msg);
}
}

----------------------- Classe CircularQueue ----------------------------

package be.hacktrack.points;
import java.util.*;

/**
*
* @author HackTrack
* @version 1.0
*/

public class CircularQueue{
private ArrayList queue;
private int currentIndex;

public CircularQueue() {
super();
queue = new ArrayList();
currentIndex = 0;
}

public Object getPrevious(Object o) throws QueueReadException{
int index = queue.indexOf(o);
if(index!=-1){
if(index==0){
return queue.get(queue.size()-1);
}else{
return queue.get(index--);
}
}else{
throw new QueueReadException("This Object is not in the queue");
}
}

public Object getPrevious(){
if(currentIndex==0){
currentIndex=queue.size()-1;
return queue.get(currentIndex);
}else{
currentIndex--;
return queue.get(currentIndex);
}
}

public Object getNext(Object o) throws QueueReadException{
int index = queue.indexOf(o);
if(index!=-1){
if(index==queue.size()-1){
return queue.get(0);
}else{
return queue.get(index++);
}
}else{
throw new QueueReadException("This Object is not in the queue");
}
}

public Object getNext(){
if(currentIndex==queue.size()-1){
currentIndex=0;
return queue.get(currentIndex);
}else{
currentIndex++;
return queue.get(currentIndex);
}
}

public void add(Object o){
queue.add(currentIndex,o);
}

public void insertBetween(Object newObject, Object o1, Object o2) throws QueueInsertException{
if(queue.contains(o1) && queue.contains(o2)){
int interval = queue.indexOf(o2)-queue.indexOf(o1);
if(interval==0){
throw new QueueInsertException("The two Object can't be the same");
}else if(interval==1){
queue.add(queue.indexOf(o2), newObject);
}else if(interval==-1){
queue.add(queue.indexOf(o1), newObject);
}else if(interval==queue.size()-1){
queue.add(newObject);
}else{
throw new QueueInsertException("The two Object must be contiguous");
}
}
}

public boolean remove(Object o){
return queue.remove(o);
}

public boolean contains(Object o){
return queue.contains(o);
}

public int size(){
return queue.size();
}

public String toString(){
StringBuffer s = new StringBuffer();;
Iterator it = queue.iterator();
s.append("CircularQueue" + "\n\r");
while(it.hasNext()){
s.append(it.next().toString()+"\n\r");
}
return s.toString();
}
}

-------------------------- Classe PointsArea ----------------------------

package be.hacktrack.points;
import java.awt.geom.Point2D;
import java.util.*;

/**
*
* @author HackTrack
* @version 1.0
*/

public class PointsArea {
private Point2D.Double[] pointsToSort;
private ArrayList pointsRemainingToSort;
private CircularQueue sortedPoints;
private Point2D.Double firstPoint;
private Point2D.Double lastPoint;
private double currentAngle;

public PointsArea(){
initialize();
}

public CircularQueue sortPoints(Point2D.Double[] pointsToSort) throws SortException{
if(pointsToSort.length<3)
throw new SortException();
currentAngle = 0;
//Storing points to sort
this.pointsToSort = pointsToSort;
for(int i=0 ; i<pointsToSort.length; i++){
pointsRemainingToSort.add(pointsToSort[i]);
}
//Find first point
firstPoint = getFirstPoint();
sortedPoints.add(firstPoint);
lastPoint = firstPoint;
//Find second point
pointsRemainingToSort.remove(firstPoint);
lastPoint = getNextPoint();
pointsRemainingToSort.add(firstPoint);
markAsSorted(lastPoint);
//Sorting all other points
while(true){
lastPoint = getNextPoint();

if(lastPoint==firstPoint){
break;
}else{
if(lastPoint==null)
break;
markAsSorted(lastPoint);
}
}
return sortedPoints;
}

public CircularQueue insertSummit(Point2D.Double newPoint, Point2D.Double p1, Point2D.Double p2) throws QueueReadException, QueueInsertException{
sortedPoints.insertBetween(newPoint, p1, p2);
pointsRemainingToSort.remove(newPoint);
return sortedPoints;
}

public boolean removeSummit(Point2D.Double summitToRemove){
pointsRemainingToSort.add(summitToRemove);
return sortedPoints.remove(summitToRemove);
}

public CircularQueue deleteSummit(Point2D.Double summitToDelete){
sortedPoints.remove(summitToDelete);
return sortedPoints;
}

public String toString(){
return sortedPoints.toString();
}

public List getUnsortedPoint(){
return pointsRemainingToSort;
}

public int summitCount(){
return sortedPoints.size();
}

public Point2D.Double getNextSummit(){
return (Point2D.Double)sortedPoints.getNext();
}

public Point2D.Double getNextSummit(Point2D.Double aSummit) throws QueueReadException{
return (Point2D.Double)sortedPoints.getNext(aSummit);
}

public Point2D.Double getPreviousSummit(){
return (Point2D.Double)sortedPoints.getPrevious();
}

public Point2D.Double getPreviousSummit(Point2D.Double aSummit) throws QueueReadException{
return (Point2D.Double)sortedPoints.getPrevious(aSummit);
}

/*
* Private methods
*/

private void initialize(){
pointsRemainingToSort = new ArrayList();;
sortedPoints = new CircularQueue();
lastPoint = null;
}

private Point2D.Double getNextPoint(){
Point2D.Double tempPoint = null;
Iterator it = pointsRemainingToSort.iterator();
double angle = 7;
while(it.hasNext()){
Point2D.Double aPointToSort = (Point2D.Double)it.next();
double tempAngle = calcAngle(lastPoint, aPointToSort);
if(tempAngle>currentAngle){
if(tempAngle<0){
tempAngle += Math.toRadians(360);
}
if(tempAngle==angle){
if(tempPoint==null){
angle = tempAngle;
tempPoint = aPointToSort;
}else{
if(lastPoint.distance(aPointToSort)>lastPoint.distance(tempPoint)){
angle = tempAngle;
tempPoint = aPointToSort;
}
}
}else if(tempAngle<angle){
angle = tempAngle;
tempPoint = aPointToSort;
}
currentAngle = angle;
}
}
return tempPoint;
}

private double calcAngle(Point2D.Double lastPoint, Point2D.Double aPointToSort){
double angle = 0;
double x1 = lastPoint.getX();
double y1 = lastPoint.getY();
double x2 = aPointToSort.getX();
double y2 = aPointToSort.getY();

double dx = x2-x1;
double dy = y2-y1;
if(dx==0){
if(dy==0){
//The two points are overlapping => discard aPointToSort -> pointsRemainingToSort
pointsRemainingToSort.remove(aPointToSort);
}else{
//The two points have same abcisse
if(dx>0){
angle = Math.toRadians(90);
}else{
angle = Math.toRadians(270);
}
}
}else if(dy==0){
//The two points have same ordonnée
if(dy>0){
angle = java.lang.Math.toRadians(0);
}else{
angle = java.lang.Math.toRadians(180);
}
}else{
//The two points have different abcisse and different ordonnée
angle = java.lang.Math.atan(dy/dx);
if(dx<0){
angle += java.lang.Math.toRadians(180);
}
}
return angle;
}

private void markAsSorted(Point2D.Double aPoint){
sortedPoints.add(aPoint);
pointsRemainingToSort.remove(aPoint);
}

private Point2D.Double getFirstPoint(){
firstPoint = pointsToSort[0];
for(int i=1 ; i<pointsToSort.length ; i++){
if(pointsToSort[i].getY()==firstPoint.getY()){
if(pointsToSort[i].getX()<firstPoint.getX()){
firstPoint = pointsToSort[i];
}
}else if(pointsToSort[i].getX()>firstPoint.getX()){
firstPoint = pointsToSort[i];
}
}
return firstPoint;
}
}

------------------------ Classe PointsAreaTester -----------------------

package be.hacktrack.points;
import java.util.*;
import java.awt.geom.Point2D;

/**
*
* @author HackTrack
* @version 1.0
*/

public class PointsAreaTester {

public PointsAreaTester() {
}

public static void main(String args[]) {
Point2D.Double[] pointsToSort = new Point2D.Double[10];
pointsToSort[0] = new Point2D.Double(7,10);
pointsToSort[1] = new Point2D.Double(3,9);
pointsToSort[2] = new Point2D.Double(9,7);
pointsToSort[3] = new Point2D.Double(2,5);
pointsToSort[4] = new Point2D.Double(5,6);
pointsToSort[5] = new Point2D.Double(11,5);
pointsToSort[6] = new Point2D.Double(5,4);
pointsToSort[7] = new Point2D.Double(8,4);
pointsToSort[8] = new Point2D.Double(2,2);
pointsToSort[9] = new Point2D.Double(9,2);
PointsArea area = new PointsArea();
try{
CircularQueue sortedPoints = area.sortPoints(pointsToSort);
System.out.println(sortedPoints.toString());
area.insertSummit(pointsToSort[4], pointsToSort[1], pointsToSort[0]);
System.out.println(sortedPoints.toString());
area.insertSummit(pointsToSort[7], pointsToSort[4], pointsToSort[1]);
System.out.println(sortedPoints.toString());
area.removeSummit( pointsToSort[4]);
System.out.println(sortedPoints.toString());
}catch(QueueReadException qre){
qre.printStackTrace();
}catch(QueueInsertException qie){
qie.printStackTrace();
}catch(SortException se){
se.printStackTrace();
}
}
}

Et voilà, mon cher André, une réponse concrète à la proposition que tu avais formulée ici même.

Le package peut, bien sûr, être amélioré. Si d'aventure qqn s'y attachait, qu'il me fass parvenir son code via CCM.

J'espère que cela pourra vous servir.

A+

;-)
HackTrack

HackTrack · Answer

... et désolé de 'saturer' ainsi cette page!;-)HackTrack

teebo · Answer

Pas grave, je suis sur que c'est interessant  :-DDD*,*\_/

andre · Answer

Merci   pour vos reponse s! c'est hors de mes esperances .cordialement. andre

pamela · Answer

merci Hardtrack de ta précieuse réponse .
désolé d'abord de cette rupture de dialogue puisque j'étais en vacance. j'ai vu le dernier programme que t'as écrit mais j'arrive pas à le faire tourner .je pense que la méthode se base sur la sélection des angles ) mais j'arrive pas à trouver le bon enchainement de programme.
je sais pas si andré a réussi de le faire tourner si c'est oui il a pris quoi comme donné (points ordonné ou pas ).je pense que le premier probléme était d'ordonner les points moi j'ai réussi à les ordonner
j'attend plus d'explication si c'est possible
mereci d'avance