您会得到一个由R2中的点定义的简单多边形。您可以将x和y轴上的点移动一些小的ε（例如1e-4）。有什么算法可以移动这些点以确保多边形的两个边均不完全位于同一条线上？
通常将“在同一条线上”定义为两条线的角度之间具有足够小的差异，但是出于这个特定问题的目的，如果它们的角度或直线上的差异恰好为0，则我仅考虑它们在同一条线上方程，或者您定义它们。
编辑：
这是一些代码。它仅针对平行轴的边缘解决了该问题。
package org.tendiwa.geometry;
import com.google.common.collect.ImmutableSet;
import org.jgrapht.UndirectedGraph;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Set;
public final class SameLineGraphEdgesPerturbations {
private static Comparator<Segment2D> HORIZONTAL_COMPARATOR = (a, b) -> {
assert a.start.y == a.end.y && b.start.y == b.end.y;
double d = a.start.y - b.start.y;
if (d < 0) {
return -1;
}
if (d > 0) {
return 1;
}
return 0;
};
private static Comparator<Segment2D> VERTICAL_COMPARATOR = (a, b) -> {
assert a.start.x == a.end.x && b.start.x == b.end.x;
double d = a.start.x - b.start.x;
if (d < 0) {
return -1;
}
if (d > 0) {
return 1;
}
return 0;
};
/**
* Checks if some of graph's edges are segments of the same line, and perturbs vertices and edges of this graph
* so it contains no such segments.
* <p>
* This class is designed to work with graphs that represent simple polygons. You can use it with other classes
* of graphs, but that probably won't be useful.
*
*
* @param graph
* A planar graph to be mutated.
*/
public static void perturbIfHasSameLineEdges(UndirectedGraph<Point2D, Segment2D> graph, double magnitude) {
ArrayList<Segment2D> verticalEdges = new ArrayList<>(graph.edgeSet().size());
ArrayList<Segment2D> horizontalEdges = new ArrayList<>(graph.edgeSet().size());
for (Segment2D edge : graph.edgeSet()) {
if (edge.start.x == edge.end.x) {
verticalEdges.add(edge);
} else if (edge.start.y == edge.end.y) {
horizontalEdges.add(edge);
}
}
verticalEdges.sort(VERTICAL_COMPARATOR);
horizontalEdges.sort(HORIZONTAL_COMPARATOR);
/*
The algorithm is the following:
For each axis-parallel edge in a list of edges sorted by static coordinate,
perturb its start if the next edge in list has the same static coordinate (i.e., lies on the same line).
That way if we have N same line axis-parallel edges (placed consecutively in an array because it is sorted),
N-1 of those will be perturbed, except for the last one (because there is no next edge for the last one).
Perturbing the last one is not necessary because bu perturbing other ones the last one becomes non-parallel
to each of them.
*/
int size = verticalEdges.size() - 1;
for (int i = 0; i < size; i++) {
Point2D vertex = verticalEdges.get(i).start; // .end would be fine too
if (vertex.x == verticalEdges.get(i + 1).start.x) {
perturbVertexAndItsEdges(vertex, graph, magnitude);
}
}
size = horizontalEdges.size() - 1;
for (int i = 0; i < size; i++) {
Point2D vertex = horizontalEdges.get(i).start; // .end would be fine too
if (vertex.y == horizontalEdges.get(i + 1).start.y) {
if (!graph.containsVertex(vertex)) {
// Same edge could already be perturbed in a loop over vertical edges.
continue;
}
perturbVertexAndItsEdges(vertex, graph, magnitude);
}
}
}
private static void perturbVertexAndItsEdges(
Point2D vertex,
UndirectedGraph<Point2D, Segment2D> graph,
double magnitude
) {
Set<Segment2D> edges = ImmutableSet.copyOf(graph.edgesOf(vertex));
assert edges.size() == 2 : edges.size();
// We move by both axes so both vertical and
// horizontal edges will become not on the same line
// with those with which they were on the same line.
Point2D newVertex = vertex.moveBy(magnitude, magnitude);
graph.addVertex(newVertex);
for (Segment2D edge : edges) {
boolean removed = graph.removeEdge(edge);
assert removed;
// It should be .end, not .start, because in perturbIfHasSameLineEdges we used
// vertex = edges.get(i).start
if (edge.start == vertex) {
graph.addEdge(newVertex, edge.end);
} else {
assert edge.end == vertex;
graph.addEdge(newVertex, edge.start);
}
}
assert graph.degreeOf(vertex) == 0 : graph.degreeOf(vertex);
graph.removeVertex(vertex);
}
}
最佳答案
暗示：
对于每个边，计算一些标量方向参数（例如角度，并且建议您设置其他参数，但需要标量）。这将花费时间O（N）。
对获得的所有参数进行排序，时间为O（N Lg（N））。
在O（N）中的列表中找到重复的值。
对于每组相等的值，以确保不会产生新的巧合的方式引入扰动（找到最接近的相邻值，并以间隙大小的几分之一的不同倍数扰动每个相等的值；例如， 0.1、0.2、0.2、0.2、0.4的重复数为0.2，最接近的间隙为0.1;因此您可以将其扰动为0.1、0.2-0.001、0.2、0.2 + 0.001、0.4）。或者只是随机干扰。
现在采取非防弹措施：构建受扰的支撑线并将它们相交，以便找到受扰顶点的位置。
这不是防弹措施，因为您可能会无意间以这种方式创建新的共线边，并且最好重新启动整个过程进行检查。如果两次迭代后都没有解决方案，则可能会遇到麻烦...
关于java - 您如何扰动多边形，使其多边形的两个边都不在同一条线上？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26810468/