fork(1) download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Capsule
  9. {
  10.   Point2D c1, c2;
  11.   double r;
  12.  
  13.   public Capsule(Point2D c1, Point2D c2, double r)
  14.   {
  15.     this.c1 = c1;
  16.     this.c2 = c2;
  17.     this.r = r;
  18.   }
  19.  
  20.   public Point2D[] intersect(Point2D r1, Point2D r2)
  21.   {        
  22.     Point2D cv = Point2D.diff(c2, c1);
  23.     Point2D cu = cv.unit();
  24.     if(cu == null) return null;
  25.     Point2D ncu = cu.norm();
  26.  
  27.     Point2D p1 = Point2D.addTimes(c1, ncu, r);
  28.     Point2D p2 = Point2D.addTimes(c2, ncu, r);
  29.     Point2D p3 = Point2D.addTimes(c1, ncu, -r);
  30.     Point2D p4 = Point2D.addTimes(c2, ncu, -r);
  31.  
  32.     double[] wh = new double[6];
  33.     wh[0] = Point2D.raySeg(r1, r2, p1, p2);
  34.     wh[1] = Point2D.raySeg(r1, r2, p3, p4);
  35.     Point2D.rayCircle(r1, r2, c1, r, wh, 2);
  36.     Point2D.rayCircle(r1, r2, c2, r, wh, 4);
  37.  
  38.     double hMin = Double.POSITIVE_INFINITY;
  39.     double hMax = Double.NEGATIVE_INFINITY;
  40.     for(double h : wh)
  41.     {
  42.       if(!Double.isNaN(h))
  43.       {
  44.         hMin = Math.min(h, hMin);
  45.         hMax = Math.max(h, hMax);
  46.       }
  47.     }
  48.  
  49.     Point2D rd = Point2D.diff(r2, r1);
  50.     Point2D iMin = Point2D.addTimes(r1, rd, hMin);
  51.     if(hMin == hMax) return new Point2D[]{iMin};
  52.     Point2D iMax = Point2D.addTimes(r1, rd, hMax);    
  53.     return new Point2D[]{iMin, iMax};
  54.   }
  55.  
  56.   static class Point2D 
  57.   {
  58.     double x;
  59.     double y;
  60.  
  61.     public Point2D(double x, double y)
  62.     {
  63.       this.x = x;
  64.       this.y = y;
  65.     }
  66.  
  67.     // https://stackoverflow.com/a/1084899/6438819
  68.     public static void rayCircle(Point2D p, Point2D pe, Point2D cc, double r, double[] res, int off)
  69.     {
  70.       Point2D d = Point2D.diff(p, pe);
  71.       Point2D f = Point2D.diff(cc, p);
  72.  
  73.       double a = d.lengthSq();
  74.       double b = 2*Point2D.dot(f, d);
  75.       double c = f.lengthSq() - r*r;
  76.  
  77.       double disc = b*b-4*a*c;
  78.       if(disc < 0)
  79.       {
  80.         res[off] = res[off+1] = Double.NaN;
  81.         return;
  82.       }      
  83.       double discRoot = Math.sqrt(disc);      
  84.       res[off] = (-b - discRoot)/(2*a);
  85.       res[off+1] = (-b + discRoot)/(2*a);
  86.     }
  87.  
  88.     // https://stackoverflow.com/a/565282/6438819
  89.     public static double raySeg(Point2D p, Point2D pe, Point2D q, Point2D qe)
  90.     {
  91.       Point2D r = Point2D.diff(pe, p);
  92.       Point2D s = Point2D.diff(qe, q);
  93.  
  94.       double sr = Point2D.cross(s, r);
  95.       if(sr == 0) return Double.NaN;
  96.  
  97.       Point2D pq = Point2D.diff(p, q);
  98.       double pqr = Point2D.cross(pq, r);
  99.  
  100.       double u = pqr /sr;
  101.       if(u<0 || u>1) return Double.NaN; 
  102.  
  103.       Point2D qp = Point2D.diff(q, p);
  104.       double rs = Point2D.cross(r, s);
  105.       double qps = Point2D.cross(qp, s);
  106.       return qps / rs;
  107.     }
  108.  
  109.     private static double dot(Point2D p1, Point2D p2)
  110.     {
  111.       return p1.x*p2.x + p1.y*p2.y;
  112.     }
  113.  
  114.     private static double cross(Point2D p1, Point2D p2)
  115.     {
  116.       return p1.x*p2.y - p1.y*p2.x;
  117.     }
  118.  
  119.     public static Point2D addTimes(Point2D c, Point2D u, double r)
  120.     {
  121.       return new Point2D(c.x + u.x*r, c.y + u.y*r);
  122.     }
  123.  
  124.     // CCW
  125.     public Point2D norm()
  126.     {
  127.       return new Point2D(-y, x);
  128.     }
  129.  
  130.     public Point2D unit()
  131.     {
  132.       double d = length();
  133.       if(d == 0) return null;
  134.       return new Point2D(x/d, y/d);
  135.     }
  136.  
  137.     public double length()
  138.     {
  139.       return Math.sqrt(lengthSq());
  140.     }
  141.  
  142.     public double lengthSq()
  143.     {
  144.       return x*x+y*y;
  145.     }
  146.  
  147.     public static Point2D diff(Point2D r2, Point2D r1)
  148.     {
  149.       return new Point2D(r2.x-r1.x, r2.y-r1.y);
  150.     }
  151.  
  152.     public String toString()
  153.     {
  154.       return String.format("(%f, %f)", x, y);
  155.     }
  156.  
  157.     public static double dist(double x2, double y2, int x3, int y3)
  158.     {
  159.       return Math.sqrt((x3-x2)*(x3-x2) + (y3-y2)*(y3-y2));
  160.     }
  161.  
  162.     public void set(int x, int y)
  163.     {
  164.       this.x = x;
  165.       this.y = y;
  166.     }
  167.   }
  168.  
  169.   public static void main(String[] args)
  170.   {
  171.     Capsule cap = new Capsule(new Point2D(0, 0), new Point2D(2, 0), 0.5);
  172.     Point2D[] h = cap.intersect(new Point2D(1, -1), new Point2D(1, 1));
  173.     System.out.println(Arrays.toString(h));
  174.   }
  175. }
  176.  
Success #stdin #stdout 0.09s 2184192KB
comments (?)
stdin 
Standard input is empty
stdout 
[(1.000000, -0.500000), (1.000000, 0.500000)]
https://ideone.com/ThgLbv
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!