CODEWITHSUNDEEP
java
Zaubergurke
Zaubergurke

Reputation: 1

sort points of interest by distance between each other

I have an array with point-objects as an input. I want to sort these points, that I get an Array with the shortest route covering all the points. this is my code so far, but i havent figuered out, how to delete points, once they have been used.

public Point[] poiSort(Point[] poi){
        poi = new Point[lenght+1];
        poi[0] = points[0];
        distances = new Double[lenght];
        double Distance = verybignumber;
        double Distancecompare;
        for (int i = 1; i < leght+1; i++){
            for (int j = 1; j < (lenght); j++){
                Distancecompare = points[i-1].getDistance(points[j]);
                if (Distance > Distancecompare){
                    Distance = Distancecompare;
                    poi[i] = points[j];
                    distances[i-1] = Disstance;
                }
            }
        }
        return poi;
    }

Upvotes: 0

Views: 1195

Answers (3)

Obaida
Obaida

Reputation: 1

in MaxScript it can be done this way: create 10 points. we will use the First Point as a starting point you need to define a starting point. select the other 9 points in random order.

(
    local arr = #($Point001)
    local objs = selection as array
        
    print objs; print "----------"
    
    for x = objs.count to 1 by -1 do (
        local tmparr = for i = 1 to objs.count collect (distance arr[arr.count] objs[i])
        local idx = finditem tmparr (amin tmparr)
        append arr objs[idx]
        deleteItem objs idx
    )
    print arr
)

Upvotes: 0

Stephen C
Stephen C

Reputation: 719229

The problem you are apparently trying to solve doesn't make sense.

Or at least ... the subproblem doesn't.

If you have N points, then the number of pair-wise distances between them is (N-1)^2. For each given point P, there are N - 1 distances to other points. You can't define a relevant / easily computable ordering for the points based on that. So sorting doesn't make sense.

What you could do is to take one point and order (and sort) the others based on the distance to that point. But that means for a total of N points you have N separate orderings.

Note that what you are trying to solve here is a form of the "Traveling Salesman1 Problem" (TSP). TSP has been mathematically proven to be an NP-complete problem. That should tell you that attempting to solve it by sorting (which is O(NlogN)) is not to work.

My advice would be:

  1. Do some reading on the TSP and why it is hard
  2. Try to avoid having to find an exact solution to the problem
  3. Look at the techniques / algorithms for finding approximate solutions ... rather than trying to invent your own algorithm.
  4. Look for an existing library.

1 - Or the "Traveling Salesperson Problem". No, I'm not kidding.

Upvotes: 2

papalulu
papalulu

Reputation: 78

You can build a new array during sorting and return it as result. This way you do not need to delete elements. Alternatively, you could use an ArrayList or a TreeSet for more flexibility. Here a maybe not so elegant, but working example with arrays:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Optional;

public class Main {
    
    public static void main(String... args) {
        
        Point[] points = {new Point(1,1), new Point(3,3), new Point(2,2)};
        Point[] result = sort(points);
        for (Point p : result) {
            System.out.println("point(" + p.x + ", " + p.y + ")");
        }
        
    }
    
    public static Point[] sort(Point[] in) {
        if (in == null || in.length == 0) {
            return in;
        }
        Point[] out = new Point[in.length];
        Point current = in[0];
        for (int i = 0; i < in.length; i++) {
            if (i == in.length -1) {
                out[in.length -1] = Arrays.stream(in).filter(p -> !p.visited).findAny().orElseGet(null);
                break;
            }
            final Point finalCurrent = current;     // variable must be final or effectively final as used in stream
            out[i] = finalCurrent;
            finalCurrent.visit();
            Point next = Arrays.stream(in).filter(p -> !p.visited).min(Comparator.comparingDouble(p -> p.getDistance(finalCurrent))).get();
            current = next;
        }
        return out;
    }
}



class Point {
    final double x;
    final double y;
    boolean visited;
    
    Point(double x, double y) {
        this.x = x;
        this.y = y;
    }
    
    public double getDistance(Point point) {
        return Math.abs(this.x-point.x) + Math.abs(this.y - point.y);
    }
    
    public void visit() {
        visited = true;
    }

}

Upvotes: 0

Related Questions