구현 적응 기능

Question

내가 (정말 같은 두 예제를) 다음 두 가지 예에서 psuedocode을 사용하여 알고리즘

https://www.andr.mu/logs/acquiring-samples-to-plot-a-math-function-adaptive/ http://yacas.readthedocs.io/en/latest/book_of_algorithms/basic.html

내가 만난 문제를 (플로팅 적응 기능을 구현하려고 해요

(1) 중복 좌표가 생성되고 있습니다. 나는 이것이 쏟아 질 때마다 양쪽 끝이 유지되는 분할 (split) 때문이라는 것을 알고 있습니다. 그래서 한 간격의 끝은 다른 간격의 시작입니다. 동일한 x 값이 두 번 평가됩니다. 그러나 알고리즘을 설정하여 중복 된 좌표를 피할 수있는 방법이 있습니다. 더티 픽스 (아래 코드의 주석 참조)로 시작 또는 끝 좌표를 추가하는 것을 피할 수는 있지만 전체 간격 동안 하나씩 누락 될 수 있습니다.

(2) 플롯의 일부는 본질적으로 이상한 대칭 함수 인 좌표가 누락되어 있습니다. 알고리즘은 양쪽 모두 동일한 방식으로 작동해야하지만 그렇지 않습니다. 이것은 깊이> = 6 일 때 시작되며, 함수의 오른쪽으로 여분의 분할을 수행하고 원점을 중심으로 왼쪽면에 대해서는 아무것도 수행하지 않습니다. 출발점에서 떨어진 좌표의 나머지 부분은 일치하는 것처럼 보입니다. 오른쪽은 전반적으로 왼쪽보다 더 많은 스플릿을 얻는 것 같습니다. 알고리즘의

문제 (2)

내 구현

static List<Double[]> linePoints; 

public static void main(String[] args) { 
    linePoints = new ArrayList<>(); 

    double startX = -50; 
    double endX = 50; 

    sampling(startX, endX, depth, tolerance); 

    /* Print all points to be plotted - x,y coordinates */ 
    for (Double[] point : linePoints) { 
     System.out.println(point[0]+","+point[1]); 
    } 
} 

/* math function */ 
public static double f(double x){ 
    return x*Math.sin(x); 
} 


static int depth = 6; /* 8 */ 
static double tolerance = 0.005; /* just a guess */ 

/* Adaptive sampling algorithm */ 
/* mostly followed along 2st website and used 1st website variable names */ 
public static void sampling(double xa, double xc, int depth, double tolerance){ 
    /* step (1) of 2nd website - determine mid-intervals */ 
    double xb = (xa+xc)/2; /* (xc-xa)/2; tried these from 1st website - didn't work out */ 
    double xab = (xa+xb)/2; /* (xb-xa)/2; */ 
    double xbc = (xb+xc)/2; /* (xc-xb)/2; */ 

    /* evaluate the above points using math function - store in array */ 
    double[] points = new double[5]; 
    points[0] = f(xa); points[1] = f(xab); points[2] = f(xb); points[3] = f(xbc); points[4] = f(xc); 

    /* step (2) of 2nd website */ 
    if (depth <= 0){ 
     linePoints.add(new Double[]{xa, points[0]}); /* either I comment out this line for dirty fix */ 
     linePoints.add(new Double[]{xab, points[1]}); 
     linePoints.add(new Double[]{xb, points[2]}); 
     linePoints.add(new Double[]{xbc, points[3]}); 
     linePoints.add(new Double[]{xc, points[4]}); /* or comment out this line */ 
    } else { 
     /* step (3) of 2nd website */ 
     int counter = 0; 

     for (int i = 1; i < points.length-1; i++){ 
      /* Check if prev, current, next values are infinite or NaN */ 
      if ( (Double.isInfinite(points[i-1]) || Double.isNaN(points[i-1])) || 
        (Double.isInfinite(points[i]) || Double.isNaN(points[i])) || 
        (Double.isInfinite(points[i+1]) || Double.isNaN(points[i+1]))){ 
       counter++; 
       continue; 
      } 

      /* Determine the fluctuations - if current is <or> both it's left/right neighbours */ 
      boolean middleLarger = (points[i] > points[i-1]) && (points[i] > points[i+1]); 
      boolean middleSmaller = (points[i] < points[i-1]) && (points[i] < points[i+1]); 

      if (middleLarger || middleSmaller){ 
       counter++; 
      } 
     } 

     if (counter <= 2){ /* at most 2 */ 
      /* Newton-Cotes quadratures - check if smooth enough */ 
      double f1 = (3d/8d)*points[0]+(19d/24d)*points[1]-(5d/24d)*points[2]+(1d/24d)*points[3]; /* add 'd' to end of number, otherwise get 0 always */ 
      double f2 = (5d/12d)*points[2]+(2d/3d)*points[3]-(1d/12d)*points[4]; 

     if (Math.abs(f1-f2) < tolerance * f2){ 
       linePoints.add(new Double[]{xa, points[0]}); 
       linePoints.add(new Double[]{xab, points[1]}); 
       linePoints.add(new Double[]{xb, points[2]}); 
       linePoints.add(new Double[]{xbc, points[3]}); 
       linePoints.add(new Double[]{xc, points[4]}); 
      } else { 
       /* not smooth enough - needs more refinement */ 
       depth--; 
       tolerance *= 2; 
       sampling(xa, xb, depth, tolerance); 
       sampling(xb, xc, depth, tolerance); 
      } 

     } else { 
      /* else (count > 2), that means further splittings are needed to produce more accurate samples */ 
      depth--; 
      tolerance *= 2; 
      sampling(xa, xb, depth, tolerance); 
      sampling(xb, xc, depth, tolerance); 
     } 
    } 
} 

FIX - 내 코드

에 대한 수정이 창을 보면 네브라스카의 예와 0.5 대신 2에 의해 허용 곱하면, (2)

유전자의 예는이 알고리즘의 더 나은 및 클리너 구현 문제를 해결하기 위해 듯 중복 좌표

Answer 1

난 당신이 충실하게 구현했다고 생각 처리 그러나 알고리즘이 깨졌습니다. 비대칭 구적법은 비대칭 결과를 쉽게 나타낼 수 있습니다. 나는 같은 종류의 이상한 것을 얻는다.

그러나 정렬 된 집합에서이를 유지하고 재귀 분석기가 실행될 때 이미 끝점이 삽입 된 불변성을 사용하여 중복 된 점을 제거 할 수 있습니다.

import static java.lang.Double.compare; 
import static java.lang.Double.isFinite; 
import static java.lang.Math.PI; 

import java.util.List; 
import java.util.SortedSet; 
import java.util.TreeSet; 
import java.util.function.DoubleUnaryOperator; 
import static java.util.stream.Collectors.toList; 
import java.util.stream.DoubleStream; 

public class AdaptivePlot { 
    private final DoubleUnaryOperator f; 
    private final double a; 
    private final double c; 
    private final SortedSet<Point> plot = new TreeSet<>((s, t) -> compare(s.x, t.x)); 

    public AdaptivePlot(DoubleUnaryOperator f, double a, double c) { 
    this.f = f; 
    this.a = a; 
    this.c = c; 
    } 

    public static class Point { 
    final double x, y; 
    public Point(double x, double y) { 
     this.x = x; 
     this.y = y; 
    } 
    } 

    public AdaptivePlot computePlot(int depth, double eps) { 
    plot.clear(); 
    Point pa = pointAt(a); 
    Point pc = pointAt(c); 
    plot.add(pa); 
    plot.add(pc); 
    computePlot(pa, pc, depth, eps); 
    return this; 
    } 

    public List<Point> getPlot() { 
    return plot.stream().collect(toList()); 
    } 

    private Point pointAt(double x) { 
    return new Point(x, f.applyAsDouble(x)); 
    } 

    private void computePlot(Point pa, Point pc, int depth, double eps) { 
    Point pb = pointAt(0.5 * (pa.x + pc.x)); 
    Point pa1 = pointAt(0.5 * (pa.x + pb.x)); 
    Point pb1 = pointAt(0.5 * (pb.x + pc.x)); 
    plot.add(pb); 
    if (depth > 0 && 
     (oscillates(pa.y, pa1.y, pb.y, pb1.y, pc.y) 
      || unsmooth(pa.y, pa1.y, pb.y, pb1.y, pc.y, eps))) { 
     computePlot(pa, pb, depth - 1, 2 * eps); 
     computePlot(pb, pc, depth - 1, 2 * eps); 
    } 
    plot.add(pa1); 
    plot.add(pb1); 
    } 

    private static boolean oscillates(
     double ya, double ya1, double yb, double yb1, double yc) { 
    return isOscillation(ya, ya1, yb) 
     && isOscillation(ya1, yb, yb1) 
     && isOscillation(yb, yb1, yc); 
    } 

    private static boolean isOscillation(double ya, double yb, double yc) { 
    return !isFinite(ya) || !isFinite(yb) || !isFinite(yc) 
     || (yb > ya && yb > yc) || (yb < ya && yb < yc); 
    } 

    private static boolean unsmooth(
     double ya, double ya1, double yb, double yb1,double yc, double eps) { 
    double y0 = DoubleStream.of(ya, ya1, yb, yb1, yc).min().getAsDouble(); 
    double [] yg = DoubleStream.of(ya, ya1, yb, yb1, yc).map(y -> y - y0).toArray(); 
    double q4 = quadrature(yg[0], yg[1], yg[2], yg[3]); 
    double q3 = quadrature(yg[2], yg[3], yg[4]); 
    return Math.abs(q4 - q3) > eps * q3; 
    } 

    private static double quadrature(double y0, double y1, double y2, double y3) { 
    return 3d/8d * y0 + 19d/24d * y1 - 5d/24d * y2 + 1d/24d * y3; 
    } 

    private static double quadrature(double y0, double y1, double y2) { 
    return 5d/12d * y0 + 2d/3d * y1 - 1d/12d * y2; 
    } 

    public static void main(String [] args) { 
    List<Point> plot = new AdaptivePlot(x -> x * Math.sin(x), -2d * PI, 2d * PI) 
     .computePlot(6, 0.005).getPlot(); 
    for (Point p : plot) { 
     System.out.println(p.x + "\t" + p.y); 
    } 
    } 
} 

Answer 2

나는 개인적으로이 방법은 끔찍한 찾을 :

여기에 더욱 완벽하게 현대적인 자바 기능을 사용하여 단순화합니다.

단순한 규칙으로 좋은 결과를 얻을 수 있습니다 : 중간 지점과 코드의 거리가 작은 임계 값을 초과하는 경우 간격을 세분화하십시오.

주의 : 효과를 확장 방지하기 위해, 당신은 (두 축에 approppriate 규모 요인) mm의 모든 기하학적 수량을 표현한다.

Subdivide left, middle, right: 
    if DistancePointLine (middle, f(middle)), (left, f(left)), (right, f(right)) < Tolerance: 
     DrawLine (left, f(left), (right, f(right)) 
    else 
     Subdivide left, (left + middle)/2, middle 
     Subdivide middle, (middle + right)/2, right 

변곡점 주위에서 대칭 상황에서이 방법이 실패 할 수 있습니다. 극복하려면, 허용 오차가 충족 되더라도 하나의 추가 세분화를 강제 할 수 있습니다.