Witam
Potrzebuję zrobić projekt który wygeneruje a następnie wyznaczy najbliżej leżące siebie punkty. Znalazłem algorytm który to oblicza lecz mam problem aby go zaimplementować ponieważ wszystko potrzebuję zrobić w programie NetBeans z graficznym interfejsem. Zrobiłem generowanie punktów i rysowanie ich na JPanelu lecz mam problem z zastosowaniem algorytmu. Niestety język Java nie jest moją mocną stroną i słabo sobie w nim radzę, czy mógłby mi ktoś pomóc jakoś to ogarnąć aby algorytm wyznaczania najbliższych punktów działał dla tych wygenerowanych puktów? Z góry bardzo dziękuję za każdą pomoc.
import java.awt.Point;
import java.util.Comparator;
public class MyPoint extends Point implements Comparable<MyPoint>{
public final int x;
public final int y;
public static final Comparator<MyPoint> sortX = new compareX();
public static final Comparator<MyPoint> sortY = new compareY();
public MyPoint(int x, int y)
{
this.x = x;
this.y = y;
}
private static class compareX implements Comparator<MyPoint>{
//comparator for comparing x-coordinates
public int compare(MyPoint o1, MyPoint o2) {
if (o1.x < o2.x) return -1;
if (o1.x > o2.x) return +1;
return 0;
}
}
private static class compareY implements Comparator<MyPoint>{
//comparator for comparing y-coordinates
public int compare(MyPoint o1, MyPoint o2) {
if (o1.y < o2.y) return -1;
if (o1.y > o2.y) return +1;
return 0;
}
}
public int compareTo(MyPoint p) {
if (x == p.x && y == p.y)
return 0;
else
if (x == p.x)
return y < p.y ? -1 : 1;
else
return x < p.x ? -1 : 1;
}
@Override
public String toString()
{
return "(" + x + ", " + y + ")";
}
Tutaj jest kod rysowania punktów oraz obliczanie najbliżej leżących:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.TreeSet;
public class NewJPanel extends javax.swing.JPanel {
@Override
public void paint(Graphics g)
{
if ( image != null)
{
g.drawImage(image, 0, 0, this);
}
else
image = createImage(getWidth(), getHeight() );
}
/**
* * czysci obszar rysowania
*/
public void clear()
{
Graphics g = image.getGraphics();
g.clearRect(0, 0, image.getWidth(this), image.getHeight(this));
}
/**
* Rysuje punkty na panelu
* @param points - tablica punktow
*/
public void drawPoints( TreeSet<MyPoint> points)
{
Graphics g = image.getGraphics();
g.setColor(color); // ustawia kolor
for (MyPoint p: points)
g.fillOval(p.x - r, p.y - r, 2 * r, 2 * r);
repaint(); // wymusza odrysowanie panela
}
private Image image; // obraz, na ktorym rysujemy
private final int r = 3; // promirn kola
private final Color color = Color.blue; // kolor punktu
/**
* Creates new form NewJPanel
*/
public NewJPanel() {
initComponents();
}
//----------------------------------------------------------------------------
private static double distance(MyPoint a, MyPoint b){
//calculate the distance between two points
double xDiff = a.x + b.x;
double yDiff = a.y + b.y;
return Math.sqrt(xDiff * xDiff + yDiff * yDiff);
}
static MyPoint[] bruteForce(MyPoint[] sortByX, MyPoint[] sortByY){
//brute force to find the closest pair when the size is small enough
double min = distance(sortByX[0],sortByX[1]);
MyPoint[] pair = new MyPoint[2];
pair[0] = sortByX[0];
pair[1] = sortByX[1];
for (int i = 0;i < sortByX.length;i++){
for (int j = i + 1;j < sortByX.length;j++){
double dist1 = distance(sortByX[i],sortByX[j]);
double dist2 = distance(sortByY[i],sortByY[j]);
if (dist1 < min) {
min = dist1;
pair[0] = sortByX[i];
pair[1] = sortByX[j];
}
if (dist2 < min) {
min = dist1;
pair[0] = sortByY[i];
pair[1] = sortByY[j];
}
}
}
return pair;
}
public static MyPoint[] closestPair(MyPoint[] a){
//create two copies of the original array
//sort each array according to the x coordinates and coordinates
MyPoint[] sortByX = new MyPoint[a.length];
MyPoint[] sortByY = new MyPoint[a.length];
for (int i = 0;i < a.length;i++){
sortByX[i] = a[i];
sortByY[i] = a[i];
}
Arrays.sort(sortByX, MyPoint.sortX);
Arrays.sort(sortByY, MyPoint.sortY);
return closest(sortByX, sortByY);
}
private static MyPoint[] closest(MyPoint[] sortByX, MyPoint[] sortByY){
if (sortByX.length <=3) return bruteForce(sortByX, sortByY); //base case of recursion: brute force when size is small
MyPoint[] pair = new MyPoint[2];
double min;
int center = sortByX.length /2;
//separate the two arrays to left half and right half
MyPoint[] leftHalfX = new MyPoint[center];
MyPoint[] rightHalfX = new MyPoint[sortByX.length - center];
MyPoint[] leftHalfY = new MyPoint[center];
MyPoint[] rightHalfY = new MyPoint[sortByX.length - center];
for (int i = 0;i < center;i++){
leftHalfX[i] = sortByX[i];
leftHalfY[i] = sortByY[i];
}
for (int i = center;i < sortByX.length;i++){
rightHalfX[i-center] = sortByX[i];
rightHalfY[i-center] = sortByY[i];
}
//independently find the closest pair of left half and right half
MyPoint[] pair1 = closest(leftHalfX, leftHalfY);
double min1 = distance(pair1[0],pair1[1]);
MyPoint[] pair2 = closest(rightHalfX, rightHalfY);
double min2 = distance(pair2[0],pair2[1]);
//set the closest pair of the smaller of the previous two
//calculate the closest distance
if (min1 < min2) {
pair = pair1;
min = min1;
}else{
pair = pair2;
min = min2;
}
//find closest "split" pairs
//generate a strip of points whose x-coordinates are within closest distance of the center of sortByX
//using ArrayList instead of Arrays for filtered data to allow for dynamic size
ArrayList<MyPoint> filtered = new ArrayList<MyPoint>();
double leftBoundary = sortByX[center].x - min;
double rightBoundary = sortByX[center].x + min;
for (int i = 0; i<sortByY.length; i++){
if (leftBoundary < sortByY[i].x && sortByY[i].x < rightBoundary){
filtered.add(sortByY[i]);
}
}
//if the closest pair p and q is a "split" pair, their positions in filtered data is at most 7 positions apart
for (int i = 0; i < (filtered.size()-1);i++){
for (int j = i + 1; j < Math.min(filtered.size(), i + 7);j++){
double dist = distance(filtered.get(i),filtered.get(j));
if (dist < min){
min = dist;
pair[0] = filtered.get(i);
pair[1] = filtered.get(j);
}
}
}
return pair;
}
}
Głównym problemem jest to że rysowanie działa na TreeSet<>, a cały algorytm wyznaczający najbliższe punkty opiera się na tablicach przez co wszystko się sypie. :/