我想做的是想出一种在图形上生成 n 个随机点的方法(不需要显示它)。随机选择一个点并将其连接到离它最近的点(如果它已经连接到最佳选项，则连接到下一个最接近的点)，以便没有两条线相交。重复此过程，直到不再有可能的连接为止。顶点代表 map 上的区域，连接代表邻接。到目前为止，我的以下代码如下，摘自 http://javaingrab.blogspot.com/2012/12/m-way-graph-coloring-with-backtracking.html :
public class MWayGrColor{
/*G is graph's adjacency matrix and x is solution vector */
private int G[][],x[],n,m,soln;
public void mColoring(int k){ //backtracking function
for(int i=1;i<=n;i++){
next_color(k); //coloring kth vertex
if(x[k]==0)
return; //if unsuccessful then backtrack
if(k==n) //if all colored then show
write();
else
mColoring(k+1); /* successful but still left to color */
}
}
private void next_color(int k){
do{
int i=1;
x[k]=(x[k]+1)%(m+1);
if(x[k]==0)
return;
for(i=1;i<=n;i++)
if(G[i][k]!=0 && x[k]==x[i]) /* checking adjacency and not same color */
break;
if(i==n+1) return; //new color found
}while(true);
}
private void write(){
System.out.print("\nColoring(V C) # "+(++soln)+"-->");
for(int i=1;i<=n;i++)
System.out.print("\t("+i+" "+x[i]+")"); //solution vector
}
public void input(){
java.util.Scanner sc=new java.util.Scanner(System.in);
System.out.print("Enter no. of vertices : ");
n=sc.nextInt();
G=new int[n+1][n+1];
x=new int[n+1];
System.out.print("Enter no. of colors : ");
m=sc.nextInt();
System.out.println("Enter adjacency matrix-->");
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
G[i][j]=sc.nextInt();
}
public static void main (String[] args) {
MWayGrColor obj=new MWayGrColor();
obj.input();
obj.mColoring(1);
if(obj.soln==0)
System.out.println("\nNeed more than "+obj.m+" colors");
else
System.out.print("\nTOTAL SOLN : "+obj.soln);
}
}
如前所述， map 不需要以视觉方式表示，因为当前的显示方法已经足够了。我知道 Point2D.Double 类和 Line2D 类，我原本打算开始生成点并使用线来创建代码中已经显示的邻接矩阵，但是连接点和避免重复的方法是我对如何实现它们感到非常困惑。如何完成邻接矩阵的生成？
最佳答案
目前还不清楚实际问题是什么。听起来像是“这太复杂了，我做不完”。但是，除非对方法及其运行时间等有严格要求，否则可以务实地写下必须要做的事情:
do
{
V v0 = randomVertex();
V v1 = findClosestUnconnected(v0);
if (line(v0,v1).intersectsNoOtherLine())
{
insert(line(v0,v1));
}
} while (insertedNewLine);
当然，这意味着一些搜索。对于大图，可能有一些复杂的数据结构来加速这一点。特别是使用 KD 树等经典结构可能会加快对最近(未连接)邻居的搜索。但这似乎与原始问题无关。
使用提供允许更“自然”描述的方法的包装器可以使邻接矩阵的处理更方便一些:
class Graph
{
private final boolean matrix[][];
void addEdge(V v0, V v1)
{
matrix[v0.index][v1.index] = true;
matrix[v1.index][v0.index] = true;
}
boolean hasEdge(V v0, V v1)
{
return matrix[v0.index][v1.index];
}
}
但在这种情况下，这只是次要的语法简化。
一个例子，只是作为一个非常的q&d草图:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.SwingUtilities;
public class NonIntersectingAdjacencies
{
public static void main(String[] args)
{
Random random = new Random(0);
int numVertices = 25;
List<AdjacencyVertex> vertices =
createRandomVertices(numVertices, random);
final AdjacencyGraph adjacencyGraph =
new AdjacencyGraph(vertices);
boolean createdNewLine = true;
while (createdNewLine)
{
createdNewLine = false;
List<Integer> indices =
createShuffledList(numVertices, random);
for (int i=0; i<numVertices; i++)
{
int randomIndex = indices.get(i);
AdjacencyVertex randomVertex = vertices.get(randomIndex);
AdjacencyVertex closest =
findClosestUnconnected(randomVertex, adjacencyGraph);
if (closest != null)
{
if (!intersectsOtherLine(
randomVertex, closest, adjacencyGraph))
{
adjacencyGraph.addEdge(randomVertex, closest);
createdNewLine = true;
}
}
}
}
AdjacencyGraphPanel.show(adjacencyGraph);
}
private static List<AdjacencyVertex> createRandomVertices(
int numVertices, Random random)
{
List<AdjacencyVertex> vertices = new ArrayList<AdjacencyVertex>();
for (int i=0; i<numVertices; i++)
{
AdjacencyVertex v = new AdjacencyVertex();
v.index = i;
v.x = random.nextDouble();
v.y = random.nextDouble();
vertices.add(v);
}
return vertices;
}
private static List<Integer> createShuffledList(
int maxValue, Random random)
{
List<Integer> list = new ArrayList<Integer>();
for (int i=0; i<maxValue; i++)
{
list.add(i);
}
Collections.shuffle(list, random);
return list;
}
private static boolean intersectsOtherLine(
AdjacencyVertex v0, AdjacencyVertex v1,
AdjacencyGraph adjacencyGraph)
{
Line2D newLine = new Line2D.Double(
v0.x, v0.y, v1.x, v1.y);
List<AdjacencyVertex> vertices = adjacencyGraph.getVertices();
for (int i=0; i<vertices.size(); i++)
{
for (int j=0; j<vertices.size(); j++)
{
if (i == j)
{
continue;
}
AdjacencyVertex oldV0 = vertices.get(i);
AdjacencyVertex oldV1 = vertices.get(j);
if (adjacencyGraph.hasEdge(oldV0, oldV1))
{
Line2D oldLine = new Line2D.Double(
oldV0.x, oldV0.y, oldV1.x, oldV1.y);
if (Intersection.intersect(oldLine, newLine))
{
return true;
}
}
}
}
return false;
}
private static AdjacencyVertex findClosestUnconnected(
AdjacencyVertex v,
AdjacencyGraph adjacencyGraph)
{
double minDistanceSquared = Double.MAX_VALUE;
AdjacencyVertex closest = null;
List<AdjacencyVertex> vertices = adjacencyGraph.getVertices();
for (int i=0; i<vertices.size(); i++)
{
AdjacencyVertex other = vertices.get(i);
if (other.index == v.index)
{
continue;
}
if (adjacencyGraph.hasEdge(v, other))
{
continue;
}
double dx = other.x - v.x;
double dy = other.y - v.y;
double distanceSquared = Math.hypot(dx, dy);
if (distanceSquared < minDistanceSquared)
{
minDistanceSquared = distanceSquared;
closest = other;
}
}
return closest;
}
}
class AdjacencyVertex
{
double x;
double y;
int index;
}
class AdjacencyGraph
{
private final boolean matrix[][];
private final List<AdjacencyVertex> vertices;
AdjacencyGraph(List<AdjacencyVertex> vertices)
{
this.vertices = vertices;
this.matrix = new boolean[vertices.size()][vertices.size()];
}
List<AdjacencyVertex> getVertices()
{
return vertices;
}
void addEdge(AdjacencyVertex v0, AdjacencyVertex v1)
{
matrix[v0.index][v1.index] = true;
matrix[v1.index][v0.index] = true;
}
boolean hasEdge(AdjacencyVertex v0, AdjacencyVertex v1)
{
return matrix[v0.index][v1.index];
}
}
//============================================================================
// Only helper stuff below this line...
class AdjacencyGraphPanel extends JPanel
{
public static void show(final AdjacencyGraph adjacencyGraph)
{
SwingUtilities.invokeLater(new Runnable()
{
@Override
public void run()
{
createAndShowGUI(adjacencyGraph);
}
});
}
private static void createAndShowGUI(AdjacencyGraph adjacencyGraph)
{
JFrame f = new JFrame();
f.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
f.getContentPane().add(new AdjacencyGraphPanel(adjacencyGraph));
f.setSize(600,600);
f.setLocationRelativeTo(null);
f.setVisible(true);
}
private final AdjacencyGraph adjacencyGraph;
public AdjacencyGraphPanel(AdjacencyGraph adjacencyGraph)
{
this.adjacencyGraph = adjacencyGraph;
}
@Override
protected void paintComponent(Graphics gr)
{
super.paintComponent(gr);
Graphics2D g = (Graphics2D)gr;
int offsetX = 30;
int offsetY = 30;
int w = getWidth() - offsetX - offsetX;
int h = getHeight() - offsetY - offsetY;
g.setColor(Color.BLACK);
List<AdjacencyVertex> vertices = adjacencyGraph.getVertices();
for (int i=0; i<vertices.size(); i++)
{
for (int j=0; j<vertices.size(); j++)
{
if (i == j)
{
continue;
}
AdjacencyVertex v0 = vertices.get(i);
AdjacencyVertex v1 = vertices.get(j);
if (adjacencyGraph.hasEdge(v0, v1))
{
Line2D newLine = new Line2D.Double(
offsetX + v0.x*w,
offsetY + v0.y*h,
offsetX + v1.x*w,
offsetY + v1.y*h);
g.draw(newLine);
}
}
}
g.setColor(Color.BLUE);
for (int i=0; i<vertices.size(); i++)
{
AdjacencyVertex v = vertices.get(i);
int ix = (int)(offsetX + v.x * w);
int iy = (int)(offsetY + v.y * h);
g.fill(new Ellipse2D.Double(
ix - 5, iy - 5, 10, 10));
g.drawString(String.valueOf(i), ix, iy+16);
}
}
}
class Intersection
{
static boolean intersect(Line2D line0, Line2D line1)
{
Point2D location = new Point2D.Double();
Point2D intersection =
Intersection.computeIntersectionSegmentSegment(
line0, line1, location);
if (intersection == null)
{
return false;
}
return !isAtLineAnd(location);
}
private static boolean isAtLineAnd(Point2D location)
{
double EPSILON = 0.05;
if (Math.abs(location.getX()) < EPSILON)
{
return true;
}
if (Math.abs(location.getX()-1) < EPSILON)
{
return true;
}
if (Math.abs(location.getY()) < EPSILON)
{
return true;
}
if (Math.abs(location.getY()-1) < EPSILON)
{
return true;
}
return false;
}
/**
* Epsilon for floating point computations
*/
private static final double epsilon = 1e-6f;
/**
* Computes the intersection of the specified line segments and returns
* the intersection point, or <code>null</code> if the line segments do
* not intersect.
*
* @param line0 The first line segment
* @param line1 The second line segment
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionSegmentSegment(
Line2D line0, Line2D line1, Point2D location)
{
return computeIntersectionSegmentSegment(
line0.getX1(), line0.getY1(), line0.getX2(), line0.getY2(),
line1.getX1(), line1.getY1(), line1.getX2(), line1.getY2(),
location);
}
/**
* Computes the intersection of the specified line segments and returns
* the intersection point, or <code>null</code> if the line segments do
* not intersect.
*
* @param s0x0 x-coordinate of point 0 of line segment 0
* @param s0y0 y-coordinate of point 0 of line segment 0
* @param s0x1 x-coordinate of point 1 of line segment 0
* @param s0y1 y-coordinate of point 1 of line segment 0
* @param s1x0 x-coordinate of point 0 of line segment 1
* @param s1y0 y-coordinate of point 0 of line segment 1
* @param s1x1 x-coordinate of point 1 of line segment 1
* @param s1y1 y-coordinate of point 1 of line segment 1
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionSegmentSegment(
double s0x0, double s0y0,
double s0x1, double s0y1,
double s1x0, double s1y0,
double s1x1, double s1y1,
Point2D location)
{
if (location == null)
{
location = new Point2D.Double();
}
Point2D result = computeIntersectionLineLine(
s0x0, s0y0, s0x1, s0y1, s1x0, s1y0, s1x1, s1y1, location);
if (location.getX() >= 0 && location.getX() <= 1.0 &&
location.getY() >= 0 && location.getY() <= 1.0)
{
return result;
}
return null;
}
/**
* Computes the intersection of the specified lines and returns the
* intersection point, or <code>null</code> if the lines do not
* intersect.
*
* Ported from
* http://www.geometrictools.com/LibMathematics/Intersection/
* Wm5IntrSegment2Segment2.cpp
*
* @param s0x0 x-coordinate of point 0 of line segment 0
* @param s0y0 y-coordinate of point 0 of line segment 0
* @param s0x1 x-coordinate of point 1 of line segment 0
* @param s0y1 y-coordinate of point 1 of line segment 0
* @param s1x0 x-coordinate of point 0 of line segment 1
* @param s1y0 y-coordinate of point 0 of line segment 1
* @param s1x1 x-coordinate of point 1 of line segment 1
* @param s1y1 y-coordinate of point 1 of line segment 1
* @param location Optional location that stores the
* relative location of the intersection point on
* the given line segments
* @return The intersection point, or <code>null</code> if
* there is no intersection.
*/
public static Point2D computeIntersectionLineLine(
double s0x0, double s0y0,
double s0x1, double s0y1,
double s1x0, double s1y0,
double s1x1, double s1y1,
Point2D location)
{
double dx0 = s0x1 - s0x0;
double dy0 = s0y1 - s0y0;
double dx1 = s1x1 - s1x0;
double dy1 = s1y1 - s1y0;
double len0 = Math.sqrt(dx0*dx0+dy0*dy0);
double len1 = Math.sqrt(dx1*dx1+dy1*dy1);
double dir0x = dx0 / len0;
double dir0y = dy0 / len0;
double dir1x = dx1 / len1;
double dir1y = dy1 / len1;
double c0x = s0x0 + dx0 * 0.5;
double c0y = s0y0 + dy0 * 0.5;
double c1x = s1x0 + dx1 * 0.5;
double c1y = s1y0 + dy1 * 0.5;
double cdx = c1x - c0x;
double cdy = c1y - c0y;
double dot = dotPerp(dir0x, dir0y, dir1x, dir1y);
if (Math.abs(dot) > epsilon)
{
double dot0 = dotPerp(cdx, cdy, dir0x, dir0y);
double dot1 = dotPerp(cdx, cdy, dir1x, dir1y);
double invDot = 1.0/dot;
double s0 = dot1*invDot;
double s1 = dot0*invDot;
if (location != null)
{
double n0 = (s0 / len0) + 0.5;
double n1 = (s1 / len1) + 0.5;
location.setLocation(n0, n1);
}
double x = c0x + s0 * dir0x;
double y = c0y + s0 * dir0y;
return new Point2D.Double(x,y);
}
return null;
}
/**
* Returns the perpendicular dot product, i.e. the length
* of the vector (x0,y0,0)x(x1,y1,0).
*
* @param x0 Coordinate x0
* @param y0 Coordinate y0
* @param x1 Coordinate x1
* @param y1 Coordinate y1
* @return The length of the cross product vector
*/
private static double dotPerp(double x0, double y0, double x1, double y1)
{
return x0*y1 - y0*x1;
}
}
关于Java - 基于顶点之间距离的邻接矩阵，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23164131/