1
我對涉及尋找沃羅努瓦分佈式球體的表面上點問題的工作。據我所知，我的蠻力方法很有效，因爲它在視覺上似乎找到了點的Delaunay三角剖分。然而，我的算法在使用頂點定義每個人臉的邊緣順序時似乎失敗了。球沃羅努瓦與Java 7：繞線頂點需要修復周圍面臨
至於什麼我要去爲我的一個例子，這裏是一個使用通過確定兩個頂點是否共享多個形成點決定邊緣的一個黑客在正常地判定邊緣的版本的圖片。請注意，我想使用曲面細分來計算面的立體角併爲3D渲染API（如OpenGL）生成幾何圖形，因此這種方法不夠好。
紅色圓圈是分佈在球體的表面上的點。黃線顯示這些點的Delaunay三角剖分，綠線顯示哪些點用於定義Voronoi單元之間的頂點，黑線顯示由頂點形成的邊緣。每個單元格通過將每個像素不是靠近點或線設置爲通過將單元格的定義點轉換爲顏色而確定的顏色來着色;這與曲面細分過程分開執行。它可能需要使用工具來比較臉部顏色值，但可以顯示臉部被臉部正確包圍。這似乎表明我的代碼正確地確定了Delaunay三角剖分和Voronoi鑲嵌的頂點。
當我刪除了黑客和使用我寫了一張臉的點逆時針排序的功能，我得到的結果我無法解釋。請注意，我的程序的每次運行都會生成一組不同的隨機點，因此這兩個圖不能表示相同的點分佈。
我畫周圍的說明問題的面孔紅色框。請注意，這些單元格的黑色線條貫穿其臉部，並可能導致某些邊緣根本無法呈現（請參見右下方的框）。
我使用在this StackOverflow question描述的算法來確定點的逆時針順序。我使用相同的函數來確定細胞周圍的頂點順序並確定三點的外心。如果代碼中存在缺陷，人們會認爲代碼在三點情況下會失敗，從而引入Delaunay鑲嵌問題（因爲順序中的錯誤會導致將外接中心置於球體），但數十次運行從未崩潰，也沒有發現Delaunay鑲嵌的缺陷。我已經用我的代碼摔了幾個小時了，而且我找不到問題。 有人可以看到爲什麼會出現此問題嗎？
以下是代碼的什麼希望都在要點中列出的總結上市。它是我編寫的多個文件中的一個代碼混合體，用於獲取某些內容;在我的算法運行之前，我傾向於不嘗試清理代碼。如果沒有使用，我也沒有放入包含或必需的接口方法實現。
public class SphericalVoronoiTessellation {
private Map<Point, List<Point>> faces = new HashMap<>();
private Set<Pair<Point, Point>> edges = new HashSet<>();
private Set<Pair<Point, Point>> neighbors = new HashSet<>();
private Map<Point, Set<Point>> vertices = new HashMap<>();
public SphericalVoronoiTessellation(List<Point> points) {
List<Point> copy = new ArrayList<>(points);
Collections.sort(copy);
for (Point p : copy) {
faces.put(p, new ArrayList<Point>());
}
final int n = points.size();
for (int i = 0; i < n - 2; i++) {
Point p = copy.get(i);
for (int j = i + 1; j < n - 1; j++) {
Point q = copy.get(j);
for (int k = j + 1; k < n; k++) {
Point r = copy.get(k);
Point c = getCircumcenter(p, q, r);
double d = p.getSphericalDistanceTo(c);
if (circleIsEmpty(c, d, i, j, k, copy)) {
faces.get(p).add(c);
faces.get(q).add(c);
faces.get(r).add(c);
neighbors.add(pair(p, q));
neighbors.add(pair(p, r));
neighbors.add(pair(q, r));
Set<Point> formedBy;
if (!vertices.containsKey(c)) {
formedBy = new HashSet<>();
vertices.put(c, formedBy);
} else {
formedBy = vertices.get(c);
}
formedBy.add(p);
formedBy.add(q);
formedBy.add(r);
}
}
}
}
// TODO: Determine why using getCounterClockwiseOrder does not correctly
// order the vertices. It seems to correctly order three vertices
// every time, but that might just be luck...
for (Map.Entry<Point, List<Point>> face : faces.entrySet()) {
List<Point> vertices = getCounterClockwiseOrder(face.getValue());
// Store the vertices in the counter-clockwise order so that they
// can be used to determine the face's surface.
faces.put(face.getKey(), vertices);
// Builds a set of edges for the whole diagram. I use this set for
// duplicate-free testing of the edges on the diagram.
for (int k = 0; k < vertices.size(); k++) {
Point a = vertices.get(k);
Point b = vertices.get(k + 1 == vertices.size() ? 0 : k + 1);
edges.add(pair(a, b));
}
}
}
private static Point getCircumcenter(Point a, Point b, Point c) {
List<Point> ccw = new ArrayList<Point>();
ccw.add(a);
ccw.add(b);
ccw.add(c);
ccw = getCounterClockwiseOrder(ccw);
return
getPlaneNormal(
ccw.get(2),
ccw.get(1),
ccw.get(0)
).times(a.getRadius());
}
// This function is the one that may be broken...
private static List<Point> getCounterClockwiseOrder(List<Point> points) {
List<Point> ordered = new ArrayList<Point>(points);
final Point c = getCentroid(points);
final Point n = c.getNormalized();
final Point s = points.get(0);
final Point toS = s.minusCartesian(c);
Collections.sort(
ordered,
new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if (o1.equals(o2)) {
return 0;
} else {
return Double.compare(
getDistanceFromS(o1),
getDistanceFromS(o2)
);
}
}
private double getDistanceFromS(Point p) {
if (s.equals(p)) {
return 0;
}
double distance = s.getSphericalDistanceTo(p);
Point toP = p.minusCartesian(c);
Point cross = toS.cross(toP);
if (n.dot(cross) < 0) {
distance = RotationDisplacement.REVOLUTION - distance;
}
return distance;
}
}
);
return ordered;
}
private static Point getCentroid(List<Point> points) {
Point centroid = Point.ORIGIN;
for (Point p : points) {
centroid = centroid.plus(p);
}
return centroid.times(1./points.size());
}
private static Point getPlaneNormal(Point a, Point b, Point c) {
Point d = a.minusCartesian(b);
Point e = c.minusCartesian(b);
return d.cross(e).getNormalized();
}
private static boolean circleIsEmpty(
Point center,
double distance,
int i,
int j,
int k,
List<Point> points
) {
int m = 0;
for (; m < points.size(); m++) {
if (m == i || m == j || m == k) {
continue;
}
if (center.getSphericalDistanceTo(points.get(m)) < distance) {
break;
}
}
return m == points.size();
}
private static Pair<Point, Point> pair(Point a, Point b) {
if (b.compareTo(a) < 0) {
Point swap = b;
b = a;
a = swap;
}
return new ImmutablePair<Point, Point>(a, b);
}
}
public class Point implements Comparable<Point> {
private double radius;
private RotationDisplacement spherical;
private VectorDisplacement cartesian;
public Point(VectorDisplacement coordinates) {
this.cartesian = coordinates;
this.calculateSpherical();
}
public Point(double radius, RotationDisplacement rotations) {
this.radius = Math.abs(radius);
if (radius < 0) {
rotations = rotations.getNormalizedRepresentation();
rotations = new RotationDisplacement(
Math.PI - rotations.getColatitude(),
rotations.getLongitude() + Math.PI
);
}
this.spherical = rotations.getNormalizedRepresentation();
this.calculateCartesian();
}
private void calculateSpherical() {
this.radius = Math.sqrt(
this.getX() * this.getX() +
this.getY() * this.getY() +
this.getZ() * this.getZ()
);
double c =
this.radius > 0 ?
Math.acos(this.getY()/this.radius) :
0;
double l =
c > 0 && c < Math.PI ?
Math.atan2(-this.getZ(), this.getX()) :
0;
this.spherical =
new RotationDisplacement(
c,
l
).getNormalizedRepresentation();
}
public double getX() {
return this.cartesian.getX();
}
public double getY() {
return this.cartesian.getY();
}
public double getZ() {
return this.cartesian.getZ();
}
private void calculateCartesian() {
this.cartesian = new VectorDisplacement(
this.radius * Math.cos(
this.getLongitude()) * Math.sin(this.getColatitude()
),
this.radius * Math.cos(this.getColatitude()),
this.radius * -Math.sin(
this.getLongitude()) * Math.sin(this.getColatitude()
)
);
}
public double getLongitude() {
return this.spherical.getLongitude();
}
public double getColatitude() {
return this.spherical.getColatitude();
}
public Point plus(Point that) {
return new Point(
(VectorDisplacement) this.cartesian.add(that.cartesian)
);
}
public Point times(double scalar) {
return new Point(this.radius * scalar, this.spherical);
}
public Point getNormalized() {
return new Point(1, this.spherical);
}
public Point minusCartesian(Point that) {
return new Point(
(VectorDisplacement) this.cartesian.subtract(that.cartesian)
);
}
public double getSphericalDistanceTo(Point that) {
if (this.radius == 0 || that.radius == 0) {
return 0;
}
return this.radius * Math.abs(
Math.acos(this.dot(that)/(this.radius * that.radius))
);
}
public double dot(Point that) {
return
this.getX() * that.getX() +
this.getY() * that.getY() +
this.getZ() * that.getZ();
}
@Override
public boolean equals(Object other) {
if (!(other instanceof Point)) {
return false;
}
Point that = (Point) other;
return
this.cartesian.equals(that.cartesian) ||
this.radius == that.radius &&
this.spherical.equals(that.spherical);
}
public Point cross(Point that) {
double ux = this.getX();
double uy = this.getY();
double uz = this.getZ();
double vx = that.getX();
double vy = that.getY();
double vz = that.getZ();
return new Point(
new VectorDisplacement(
uy * vz - uz * vy,
uz * vx - ux * vz,
ux * vy - uy * vx
)
);
}
}
public interface Displacement {
public Displacement add(Displacement that);
public Displacement subtract(Displacement that);
public Displacement scale(double coefficient);
}
public class VectorDisplacement implements Displacement {
private double x;
private double y;
private double z;
public VectorDisplacement(double x, double y, double z) {
this.x = x;
this.y = y;
this.z = z;
}
public double getX() {
return x;
}
public double getY() {
return y;
}
public double getZ() {
return z;
}
@Override
public Displacement add(Displacement that) {
if (!(that instanceof VectorDisplacement)) {
throw new IllegalArgumentException(
"VectorDisplacement.add needs a VectorDisplacement"
);
}
VectorDisplacement other = (VectorDisplacement) that;
return new VectorDisplacement(
this.x + other.x,
this.y + other.y,
this.z + other.z
);
}
@Override
public boolean equals(Object other) {
if (!(other instanceof VectorDisplacement)) {
return false;
}
VectorDisplacement that = (VectorDisplacement) other;
return this.x == that.x && this.y == that.y && this.z == that.z;
}
@Override
public Displacement subtract(Displacement that) {
if (!(that instanceof VectorDisplacement)) {
throw new IllegalArgumentException(
"VectorDisplacement.subtract needs a VectorDisplacement"
);
}
VectorDisplacement other = (VectorDisplacement) that;
return new VectorDisplacement(
this.x - other.x,
this.y - other.y,
this.z - other.z
);
}
}
public class RotationDisplacement implements Displacement {
public static double REVOLUTION = Math.PI * 2;
private double colatitude;
private double longitude;
public RotationDisplacement(double colatitude, double longitude) {
this.colatitude = colatitude;
this.longitude = longitude;
}
public double getColatitude() {
return this.colatitude;
}
public double getLongitude() {
return this.longitude;
}
public RotationDisplacement getNormalizedRepresentation() {
double c = clampAngle(colatitude);
double l = 0;
if (c != 0 && c != Math.PI) {
if (c > Math.PI) {
c = RotationDisplacement.REVOLUTION - c;
l = Math.PI;
}
l = clampAngle(longitude + l);
}
return new RotationDisplacement(c, l);
}
@Override
public boolean equals(Object other) {
if (!(other instanceof RotationDisplacement)) {
return false;
}
RotationDisplacement my = this.getNormalizedRepresentation();
RotationDisplacement his =
((RotationDisplacement) other).getNormalizedRepresentation();
return
my.colatitude == his.colatitude &&
my.longitude == his.longitude;
}
private double clampAngle(double radians) {
radians %= RotationDisplacement.REVOLUTION;
if (radians < 0) {
radians += RotationDisplacement.REVOLUTION;
}
return radians;
}
}
任何有關解決這一特定問題的意見將不勝感激。