计算2D点的几何中值 [英] Calculating Geometric median of 2D points

问题描述

我正在计算Java中某些(x,y)点的几何中位数.要计算Geometric median，首先我要计算所有点的centroid，然后使用该centroid来计算Geometric median.我的代码工作正常，但有时会进入无限循环(我认为).问题出在我的while条件上.此while条件应根据输入点进行更改，但我不知道如何.我在下面放置了完整的代码.

I am calculating Geometric median of some (x,y) points in java. To calculate Geometric median, first i am calculating centroid of all the points, then this centroid is used to calculate Geometric median. My code works fine, but sometimes it goes to an infinite loop (i think.). The problem is with my while condition. This while condition should be change according to input points, but i don't know how. Below I am putting the complete code.

import java.util.ArrayList;

public class GeometricMedian {

    private static ArrayList<Point> points = new ArrayList<Point>();

    private class Point {
        private double x;
        private double y;

        Point(double a, double b) {
            x = a;
            y = b;
        }
    }

    public static void main(String[] args) {
        GeometricMedian gm = new GeometricMedian();
        gm.addPoints();
        Point centroid = gm.getCentroid();
        Point geoMedian = gm.getGeoMedian(centroid);
        System.out.println("GeometricMedian= {" + (float) geoMedian.x + ", "
                + (float) geoMedian.y + "}");
    }

    public void addPoints() {
        points.add(new Point(0, 1));
        points.add(new Point(2, 5));
        points.add(new Point(3, 1));
        points.add(new Point(4, 0));
    }

    public Point getCentroid() {
        double cx = 0.0D;
        double cy = 0.0D;
        for (int i = 0; i < points.size(); i++) {
            Point pt = points.get(i);
            cx += pt.x;
            cy += pt.y;
        }
        return new Point(cx / points.size(), cy / points.size());
    }

    public Point getGeoMedian(Point start) {
        double cx = 0;
        double cy = 0;

        double centroidx = start.x;
        double centroidy = start.y;
        do {
            double totalWeight = 0;
            for (int i = 0; i < points.size(); i++) {
                Point pt = points.get(i);
                double weight = 1 / distance(pt.x, pt.y, centroidx, centroidy);
                cx += pt.x * weight;
                cy += pt.y * weight;
                totalWeight += weight;
            }
            cx /= totalWeight;
            cy /= totalWeight;
        } while (Math.abs(cx - centroidx) > 0.5
                || Math.abs(cy - centroidy) > 0.5);// Probably this condition
                                                    // needs to change

        return new Point(cx, cy);
    }

    private static double distance(double x1, double y1, double x2, double y2) {
        x1 -= x2;
        y1 -= y2;
        return Math.sqrt(x1 * x1 + y1 * y1);
    }
}

请帮助我修复错误，如果还有更好的方法来计算某些2D点的Geometric median，请在此处编写.谢谢.

Please help me to fix the bug, also if there exitis any better way to calculate Geometric median of some 2D points, write here. Thank you.

推荐答案

一种解决方法是迭代一定次数.这类似于K-Means方法，它收敛到特定阈值或在预定义的迭代次数后停止.

One way to solve this is to iterate certain number of times. This similar to K-Means method where it either converges to a specific threshold or stops after a predefined number of iterations.

这篇关于计算2D点的几何中值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！