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
