다각형을 교란하여 가장자리의 두 개가 같은 줄에 있지 않도록하려면 어떻게해야합니까?

Question

R ^{2 점을 기준으로 정의 된 간단한 다각형이 2}입니다. 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); 
    } 
} 

Answer 1

힌트 : 모든 가장자리를 들어

, 일부 스칼라 방향 매개 변수 계산 (예 : 각도 등을, 당신은 다른 될 수 있습니다 제안하지만, 스칼라 필요로). 이것은 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로 섭동 할 수 있습니다. 아니면 그냥 혼란스럽게.

지금 방탄하지 않는 단계가 있습니다. 교란 된 지지선을 만들고 교차하여 교란 된 꼭지점의 위치를 ​​찾습니다.

실수로 새 동일 선상의 가장자리를 만들 수 있으므로 위의 절차를 다시 시작하는 것이 좋습니다. 두 번 반복 한 후에도 해결책을 얻지 못하면 문제가 생길 수 있습니다 ...