Comment trouver le centroid d'un polygone irrégulier concave en JavaScript?
Comment trouver le centroïde d'un polygone irrégulier concave avec ses sommets en JavaScript?
je veux passer un ensemble de x,y des points à une fonction JavaScript et une x,y du point.
var my_points = [{x:3,y:1},{x:5,y:8},{x:2,y:9}];
function get_polygon_centroid(points){
// answer
}
var my_centroid = get_polygon_centroid(my_points);
my_points variable n'est censé représenter le format des points, pas de représenter le nombre spécifique de points.
centre retourné sera un point quelque part à l'intérieur de la polygone.
l'objectif final serait d'ajouter un marqueur au centre d'un polygone dans une application Google Maps V3.
4 réponses
pour le centroïde de la surface 2D (qui est probablement ce dont vous avez besoin), Le mieux est de commencer par un peu de maths.
Je l'ai adapté ici à votre propre notation:
function get_polygon_centroid(pts) {
var first = pts[0], last = pts[pts.length-1];
if (first.x != last.x || first.y != last.y) pts.push(first);
var twicearea=0,
x=0, y=0,
nPts = pts.length,
p1, p2, f;
for ( var i=0, j=nPts-1 ; i<nPts ; j=i++ ) {
p1 = pts[i]; p2 = pts[j];
f = p1.x*p2.y - p2.x*p1.y;
twicearea += f;
x += ( p1.x + p2.x ) * f;
y += ( p1.y + p2.y ) * f;
}
f = twicearea * 3;
return { x:x/f, y:y/f };
}
C'est assez simple à faire. centre de gravité d'un ensemble fini de k points x1, x 2,... x k est décrit par la formule
(x1 + x 2+ ... + x k) / k
cela signifie Que nous pouvons ajouter tous les points, puis à les diviser par le nombre de points, comme ceci:
function getPolygonCentroid(points){
var centroid = {x: 0, y: 0};
for(var i = 0; i < points.length; i++) {
var point = points[i];
centroid.x += point.x;
centroid.y += point.y;
}
centroid.x /= points.length;
centroid.y /= points.length;
return centroid;
}
la réponse acceptée a un problème qui devient proéminent que la zone du polygone devient plus petite. Il ne serait pas visible dans la plupart des cas, mais peut entraîner des résultats bizarres à de très petites dimensions. Voici une mise à jour de cette solution pour tenir compte de ce problème.
function get_polygon_centroid(pts) {
var first = pts[0], last = pts[pts.length-1];
if (first.x != last.x || first.y != last.y) pts.push(first);
var twicearea=0,
x=0, y=0,
nPts = pts.length,
p1, p2, f;
for ( var i=0, j=nPts-1 ; i<nPts ; j=i++ ) {
p1 = pts[i]; p2 = pts[j];
f = (p1.y - first.y) * (p2.x - first.x) - (p2.y - first.y) * (p1.x - first.x);
twicearea += f;
x += (p1.x + p2.x - 2 * first.x) * f;
y += (p1.y + p2.y - 2 * first.y) * f;
}
f = twicearea * 3;
return { x:x/f + first.x, y:y/f + first.y };
}
voici un cas d'un centroïde se retrouvant à l'extérieur d'un petit polygone pour toute personne curieuse de savoir de quoi je parle:
var points = [
{x:78.0001462, y: 40.0008827},
{x:78.0000228, y: 40.0008940},
{x:78.0000242, y: 40.0009264},
{x:78.0001462, y: 40.0008827},
];
// original get_polygon_centroid(points)
// results in { x: 77.99957948181007, y: 40.00065236005001 }
console.log(get_polygon_centroid(points))
// result is { x: 78.0000644, y: 40.000901033333335 }
Si vous n'êtes pas décontractée à propos de la définition de "centre de gravité", les est la formule du centroïde d'un polygone. Comme vous pouvez le voir, c'est suffisamment plus compliqué que le centroïde d'un ensemble de points. Si vous pouvez faire avec le centroid des points, c'est très bien, mais si vous voulez le centroid du polygone, vous devez mettre en œuvre cette formule, qui btw n'est pas très difficile. N'oubliez pas que dans le cas général d'un polygone irrégulier, ce qui est ton cas, ces deux centroïdes seront différents!--4--> (sinon, cette formule n'existerait pas).