Dis que j'ai un chemin avec 150 nœuds / verticiennes. Comment pourrais-je simplifier si de manière à ce que, par exemple, une ligne droite avec 3 verticyes, retirerait le milieu, car elle ne fait rien à ajouter au chemin. Aussi comment pourrais-je éviter de détruire des coins tranchants? Et comment puis-je supprimer de minuscules variations et avoir des courbes lisses restantes.
merci
5 Réponses :
Comment pourrais-je simplifier si de manière à ce que, par exemple, une ligne droite avec 3 verticyes, retirerait le milieu puisqu'il ne fait rien à ajouter au chemin.
Pour chaque ensemble de trois sommets consécutifs, testez-le, qu'ils soient tous en ligne droite. S'ils sont, retirez le sommet du milieu.
Aussi comment puis-je éviter de détruire des coins tranchants?
Si vous n'élevez que des sommets qui tombent sur une ligne droite entre deux autres, vous n'aurez pas de problème avec cela.
Vous pouvez également vouloir vous assurer que le sommet "moyen" (second) des trois est en fait entre les deux "points de terminaison". Cela peut ne jamais arriver si vous pouvez vous garantir que vous commencez avec un polygone valide, mais si jamais, le retrait du deuxième sommet vous donnera généralement une forme différente de celle que vous avez commencé.
Pour tous les 3 sommets, choisissez le milieu et calculer sa distance au segment de ligne entre les deux autres. Si la distance est inférieure à la tolérance, vous êtes prêt à accepter, supprimez-le.
Si le sommet du milieu est très proche de l'un des points d'extrémité, vous devez serrer la tolérance pour éviter d'éliminer les coins arrondis par exemple.
Soit A, B, C Soyez quelques points.
Le moyen le plus simple de vérifier qu'ils se trouvent sur la même ligne consiste à compter le chiffroducteur des vecteurs. Ba, ca. P>
Si cela est égal à zéro, ils se trouvent sur la même ligne: P>
float innerproduct = X_ab * X_ac + Y_ab * Y_ac;
if (innerproduct > 0) {
// B is between A and C.
} else {
// B is not between A and C.
}
L'approche plus simple. Prenez 3 sommets A, B et C et calculez l'angle / inclinaison entre les sommets.
std::vector<VERTEX> path;
//fill path
std::vector<int> removeList;
//Assure that the value is in the same unit as the return of angleOf function.
double maxTinyVariation = SOMETHING;
for (int i = 0; i < quantity-2; ++i) {
double a = path[i], b = path[i + 1] , c = path[i + 2]
double abAngle = angleOf(a, b);
double bcAngle = angleOf(b, c);
if (abs(ab - bc) <= maxTinyVariation) {
//a, b and c are colinear
//remove b later
removeList.push_back(i+1);
}
}
//Remove vertecies from path using removeList.
Ne devriez-vous pas prendre en compte des situations telles que lorsque Abangle = 359 et BCangle = 1 ? (en degrés, c'est). Ils sont proches mais des côtés opposés de zéro.
Utilisez epsilon code> paramètre définit le niveau de "simplicité": p> private List<Point> douglasPeucker (List<Point> points, float epsilon){
int count = points.size();
if(count < 3) {
return points;
}
//Find the point with the maximum distance
float dmax = 0;
int index = 0;
for(int i = 1; i < count - 1; i++) {
Point point = points.get(i);
Point lineA = points.get(0);
Point lineB = points.get(count-1);
float d = perpendicularDistance(point, lineA, lineB);
if(d > dmax) {
index = i;
dmax = d;
}
}
//If max distance is greater than epsilon, recursively simplify
List<Point> resultList;
if(dmax > epsilon) {
List<Point> recResults1 = douglasPeucker(points.subList(0,index+1), epsilon);
List<Point> recResults2 = douglasPeucker(points.subList(index, count), epsilon);
List<Point> tmpList = new ArrayList<Point>();
tmpList.addAll(recResults1);
tmpList.remove(tmpList.size()-1);
tmpList.addAll(recResults2);
resultList = tmpList;
} else {
resultList = new ArrayList<Point>();
resultList.add(points.get(0));
resultList.add(points.get(count-1));
}
return resultList;
}
private float perpendicularDistance(Point point, Point lineA, Point lineB){
Point v1 = new Point(lineB.x - lineA.x, lineB.y - lineA.y);
Point v2 = new Point(point.x - lineA.x, point.y - lineA.y);
float lenV1 = (float)Math.sqrt(v1.x * v1.x + v1.y * v1.y);
float lenV2 = (float)Math.sqrt(v2.x * v2.x + v2.y * v2.y);
float angle = (float)Math.acos((v1.x * v2.x + v1.y * v2.y) / (lenV1 * lenV2));
return (float)(Math.sin(angle) * lenV2);
}
Moindres carrés, je suppose. Supprimez ces nœuds avec la moindre contribution à la "forme" globale. Vous devez être plus précis sur quel "chemin" vous avez et pourquoi il serait correct de supprimer les nœuds. Parlez-vous d'un chemin géométrique?
Dupliqué possible de distance la plus courte entre un point et un segment de ligne