gpt4 book ai didi

java - 获取由Voronoi线段形成的凸多边形集的最快方法

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:23:34 25 4
gpt4 key购买 nike

我使用 Fortune 算法找到一组点的 Voronoi 图。我得到的是一个线段列表,但我需要知道哪些线段形成闭合多边形,并将它们放在一个由它们围绕的原始点散列的对象中。

找到这些内容的最快方法是什么??我应该从算法中保存一些重要信息吗?如果是什么?

这是我在 Java 中从 C++ 实现移植的 fortune 算法的实现 here

class Voronoi {

// The set of points that control the centers of the cells
private LinkedList<Point> pts;
// A list of line segments that defines where the cells are divided
private LinkedList<Edge> output;
// The sites that have not yet been processed, in acending order of X coordinate
private PriorityQueue sites;
// Possible upcoming cirlce events in acending order of X coordinate
private PriorityQueue events;
// The root of the binary search tree of the parabolic wave front
private Arc root;

void runFortune(LinkedList pts) {

sites.clear();
events.clear();
output.clear();
root = null;

Point p;
ListIterator i = pts.listIterator(0);
while (i.hasNext()) {
sites.offer(i.next());
}

// Process the queues; select the top element with smaller x coordinate.
while (sites.size() > 0) {
if ((events.size() > 0) && ((((CircleEvent) events.peek()).xpos) <= (((Point) sites.peek()).x))) {
processCircleEvent((CircleEvent) events.poll());
} else {
//process a site event by adding a curve to the parabolic front
frontInsert((Point) sites.poll());
}
}

// After all points are processed, do the remaining circle events.
while (events.size() > 0) {
processCircleEvent((CircleEvent) events.poll());
}

// Clean up dangling edges.
finishEdges();

}

private void processCircleEvent(CircleEvent event) {
if (event.valid) {
//start a new edge
Edge edgy = new Edge(event.p);

// Remove the associated arc from the front.
Arc parc = event.a;
if (parc.prev != null) {
parc.prev.next = parc.next;
parc.prev.edge1 = edgy;
}
if (parc.next != null) {
parc.next.prev = parc.prev;
parc.next.edge0 = edgy;
}

// Finish the edges before and after this arc.
if (parc.edge0 != null) {
parc.edge0.finish(event.p);
}
if (parc.edge1 != null) {
parc.edge1.finish(event.p);
}

// Recheck circle events on either side of p:
if (parc.prev != null) {
checkCircleEvent(parc.prev, event.xpos);
}
if (parc.next != null) {
checkCircleEvent(parc.next, event.xpos);
}

}
}

void frontInsert(Point focus) {
if (root == null) {
root = new Arc(focus);
return;
}

Arc parc = root;
while (parc != null) {
CircleResultPack rez = intersect(focus, parc);
if (rez.valid) {
// New parabola intersects parc. If necessary, duplicate parc.

if (parc.next != null) {
CircleResultPack rezz = intersect(focus, parc.next);
if (!rezz.valid){
Arc bla = new Arc(parc.focus);
bla.prev = parc;
bla.next = parc.next;
parc.next.prev = bla;
parc.next = bla;
}
} else {
parc.next = new Arc(parc.focus);
parc.next.prev = parc;
}
parc.next.edge1 = parc.edge1;

// Add new arc between parc and parc.next.
Arc bla = new Arc(focus);
bla.prev = parc;
bla.next = parc.next;
parc.next.prev = bla;
parc.next = bla;

parc = parc.next; // Now parc points to the new arc.

// Add new half-edges connected to parc's endpoints.
parc.edge0 = new Edge(rez.center);
parc.prev.edge1 = parc.edge0;
parc.edge1 = new Edge(rez.center);
parc.next.edge0 = parc.edge1;

// Check for new circle events around the new arc:
checkCircleEvent(parc, focus.x);
checkCircleEvent(parc.prev, focus.x);
checkCircleEvent(parc.next, focus.x);

return;
}

//proceed to next arc
parc = parc.next;
}

// Special case: If p never intersects an arc, append it to the list.
parc = root;
while (parc.next != null) {
parc = parc.next; // Find the last node.
}
parc.next = new Arc(focus);
parc.next.prev = parc;
Point start = new Point(0, (parc.next.focus.y + parc.focus.y) / 2);
parc.next.edge0 = new Edge(start);
parc.edge1 = parc.next.edge0;

}

void checkCircleEvent(Arc parc, double xpos) {
// Invalidate any old event.
if ((parc.event != null) && (parc.event.xpos != xpos)) {
parc.event.valid = false;
}
parc.event = null;

if ((parc.prev == null) || (parc.next == null)) {
return;
}

CircleResultPack result = circle(parc.prev.focus, parc.focus, parc.next.focus);
if (result.valid && result.rightmostX > xpos) {
// Create new event.
parc.event = new CircleEvent(result.rightmostX, result.center, parc);
events.offer(parc.event);
}

}

// Find the rightmost point on the circle through a,b,c.
CircleResultPack circle(Point a, Point b, Point c) {
CircleResultPack result = new CircleResultPack();

// Check that bc is a "right turn" from ab.
if ((b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y) > 0) {
result.valid = false;
return result;
}

// Algorithm from O'Rourke 2ed p. 189.
double A = b.x - a.x;
double B = b.y - a.y;
double C = c.x - a.x;
double D = c.y - a.y;
double E = A * (a.x + b.x) + B * (a.y + b.y);
double F = C * (a.x + c.x) + D * (a.y + c.y);
double G = 2 * (A * (c.y - b.y) - B * (c.x - b.x));

if (G == 0) { // Points are co-linear.
result.valid = false;
return result;
}

// centerpoint of the circle.
Point o = new Point((D * E - B * F) / G, (A * F - C * E) / G);
result.center = o;

// o.x plus radius equals max x coordinate.
result.rightmostX = o.x + Math.sqrt(Math.pow(a.x - o.x, 2.0) + Math.pow(a.y - o.y, 2.0));

result.valid = true;
return result;
}

// Will a new parabola at point p intersect with arc i?
CircleResultPack intersect(Point p, Arc i) {
CircleResultPack res = new CircleResultPack();
res.valid = false;
if (i.focus.x == p.x) {
return res;
}

double a = 0.0;
double b = 0.0;
if (i.prev != null) // Get the intersection of i->prev, i.
{
a = intersection(i.prev.focus, i.focus, p.x).y;
}
if (i.next != null) // Get the intersection of i->next, i.
{
b = intersection(i.focus, i.next.focus, p.x).y;
}

if ((i.prev == null || a <= p.y) && (i.next == null || p.y <= b)) {
res.center = new Point(0, p.y);

// Plug it back into the parabola equation to get the x coordinate
res.center.x = (i.focus.x * i.focus.x + (i.focus.y - res.center.y) * (i.focus.y - res.center.y) - p.x * p.x) / (2 * i.focus.x - 2 * p.x);

res.valid = true;
return res;
}
return res;
}

// Where do two parabolas intersect?
Point intersection(Point p0, Point p1, double l) {
Point res = new Point(0, 0);
Point p = p0;

if (p0.x == p1.x) {
res.y = (p0.y + p1.y) / 2;
} else if (p1.x == l) {
res.y = p1.y;
} else if (p0.x == l) {
res.y = p0.y;
p = p1;
} else {
// Use the quadratic formula.
double z0 = 2 * (p0.x - l);
double z1 = 2 * (p1.x - l);

double a = 1 / z0 - 1 / z1;
double b = -2 * (p0.y / z0 - p1.y / z1);
double c = (p0.y * p0.y + p0.x * p0.x - l * l) / z0 - (p1.y * p1.y + p1.x * p1.x - l * l) / z1;

res.y = (-b - Math.sqrt((b * b - 4 * a * c))) / (2 * a);
}
// Plug back into one of the parabola equations.
res.x = (p.x * p.x + (p.y - res.y) * (p.y - res.y) - l * l) / (2 * p.x - 2 * l);
return res;
}

void finishEdges() {
// Advance the sweep line so no parabolas can cross the bounding box.
double l = gfx.width * 2 + gfx.height;

// Extend each remaining segment to the new parabola intersections.
Arc i = root;
while (i != null) {
if (i.edge1 != null) {
i.edge1.finish(intersection(i.focus, i.next.focus, l * 2));
}
i = i.next;
}
}

class Point implements Comparable<Point> {

public double x, y;
//public Point goal;

public Point(double X, double Y) {
x = X;
y = Y;
}

public int compareTo(Point foo) {
return ((Double) this.x).compareTo((Double) foo.x);
}
}

class CircleEvent implements Comparable<CircleEvent> {

public double xpos;
public Point p;
public Arc a;
public boolean valid;

public CircleEvent(double X, Point P, Arc A) {
xpos = X;
a = A;
p = P;
valid = true;
}

public int compareTo(CircleEvent foo) {
return ((Double) this.xpos).compareTo((Double) foo.xpos);
}
}

class Edge {

public Point start, end;
public boolean done;

public Edge(Point p) {
start = p;
end = new Point(0, 0);
done = false;
output.add(this);
}

public void finish(Point p) {
if (done) {
return;
}
end = p;
done = true;
}
}

class Arc {
//parabolic arc is the set of points eqadistant from a focus point and the beach line

public Point focus;
//these object exsit in a linked list
public Arc next, prev;
//
public CircleEvent event;
//
public Edge edge0, edge1;

public Arc(Point p) {
focus = p;
next = null;
prev = null;
event = null;
edge0 = null;
edge1 = null;
}
}

class CircleResultPack {
// stupid Java doesnt let me return multiple variables without doing this

public boolean valid;
public Point center;
public double rightmostX;
}
}

(我知道它不会编译,数据结构需要初始化,并且缺少导入)

我想要的是:

LinkedList<Poly> polys;
//contains all polygons created by Voronoi edges

class Poly {
//defines a single polygon
public Point locus;
public LinkedList<Points> verts;
}

我能想到的最直接的蛮力方法是创建图中点(边的端点)的无向图,每个点有一个条目,每个点有一个连接一个点之间的边缘(没有重复)然后去找到这个图中的所有循环,然后对于共享 3 个或更多点的每组循环,丢弃除最短循环之外的所有内容。然而,这太慢了。

最佳答案

Voronoi 图的对偶是 Delaunay 三角剖分。这意味着 Voroni 图上的每个顶点都连接到三个边 - 这意味着每个顶点属于三个区域。

我使用它的算法是:

for each vertex in Voronoi Diagram
for each segment next to this point
"walk around the perimeter" (just keep going counter-clockwise)
until you get back to the starting vertex

这应该是 O(N) 因为每个顶点只有 3 个线段。您还必须做一些簿记,以确保您不会在同一个区域做两次(一个简单的方法是为每个传出边保留一个 boolean 值,然后在您走路时将其标记出来),并记住这一点在无穷远,但这个想法应该足够了。

关于java - 获取由Voronoi线段形成的凸多边形集的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2346148/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com