Kreis-Kreis-Schnittpunkte

Wie berechne ich die Schnittpunkte von zwei Kreisen. Ich würde erwarten, dass es entweder zwei, eine oder keine Schnittpunkte in allen Fällen.

Habe ich die x-und y-Koordinaten des Zentrums-Punkt und der radius für jeden Kreis.

Antwort in python würde bevorzugt werden, aber jeder arbeitende Algorithmus akzeptabel wäre.

InformationsquelleAutor der Frage fmark | 2010-07-28

  1. 69

    Schnittpunkt von zwei Kreisen

    Geschrieben von Paul Bourke

    Den folgenden Hinweis beschreibt, wie Sie das Schnittpunkt(s)
    zwischen zwei Kreise auf einer Ebene, die folgende notation verwendet wird. Die
    Ziel ist es, die zwei Punkte P3 = (x3,
    y3), wenn Sie vorhanden sind.

    Kreis-Kreis-Schnittpunkte

    Zuerst berechnen Sie den Abstand d zwischen der Mitte
    der Kreise. d = ||P1 - P0 -||.

    • Wenn d > r0 + r1dann gibt es keine Lösungen,
      die Kreise sind getrennt.

    • Wenn d < |r0 -
      r1| dann gibt es keine Lösungen, weil ein Kreis ist
      innerhalb der anderen.

    • Wenn d = 0 und r0 =
      r1 dann die Kreise sind deckungsgleich und es gibt eine
      unendliche Anzahl von Lösungen.

    Unter Berücksichtigung der beiden Dreiecke P0P2P3
    und P1P2P3 können wir schreiben

    eine2 + h2 = r02 und
    b2 + h2 = r12

    Mit d = a + b wir lösen nach a,

    a =
    (r02 - r12 +
    d2 ) /(2 d)

    Es kann leicht gezeigt werden, dass diese reduziert sich auf
    r0, wenn die beiden Kreise berühren sich an einem Punkt, also: d =
    r0 + r1

    Lösen Sie für h durch Substitution von a in die erste
    Gleichung, h2 = r02 - a2

    So

    P2 = P0 + a ( P1 -
    P0 ) /d

    Und endlich, P3 =
    (x3,y3) in Bezug auf P0 =
    (x0,y0, P1 =
    (x1,y1) und P2 =
    (x2,y2), ist

    x3 =
    x2 + h ( y1 - y0 ) /d

    y3 = y2 -+ h ( x1 - x0 ) /
    d

    Quelle: http://paulbourke.net/geometry/circlesphere/

    InformationsquelleAutor der Antwort Jacob

  2. 14

    Hier ist mein C++ - Implementierung, basierend auf Paul Bourke ' s Artikel. Es funktioniert nur, wenn es zwei Schnittpunkte, die es sonst wahrscheinlich gibt NaN NAN NAN NAN.

    class Point{
    public:
        float x, y;
        Point(float px, float py) {
            x = px;
            y = py;
        }
        Point sub(Point p2) {
            return Point(x - p2.x, y - p2.y);
        }
        Point add(Point p2) {
            return Point(x + p2.x, y + p2.y);
        }
        float distance(Point p2) {
            return sqrt((x - p2.x)*(x - p2.x) + (y - p2.y)*(y - p2.y));
        }
        Point normal() {
            float length = sqrt(x*x + y*y);
            return Point(x/length, y/length);
        }
        Point scale(float s) {
            return Point(x*s, y*s);
        }
};

class Circle {
    public:
        float x, y, r, left;
        Circle(float cx, float cy, float cr) {
            x = cx;
            y = cy;
            r = cr;
            left = x - r;
        }
        pair<Point, Point> intersections(Circle c) {
            Point P0(x, y);
            Point P1(c.x, c.y);
            float d, a, h;
            d = P0.distance(P1);
            a = (r*r - c.r*c.r + d*d)/(2*d);
            h = sqrt(r*r - a*a);
            Point P2 = P1.sub(P0).scale(a/d).add(P0);
            float x3, y3, x4, y4;
            x3 = P2.x + h*(P1.y - P0.y)/d;
            y3 = P2.y - h*(P1.x - P0.x)/d;
            x4 = P2.x - h*(P1.y - P0.y)/d;
            y4 = P2.y + h*(P1.x - P0.x)/d;

            return pair<Point, Point>(Point(x3, y3), Point(x4, y4));
        }

};

    InformationsquelleAutor der Antwort robert king

  3. 6

    Hier ist eine Implementierung in Javascript mit Hilfe von Vektoren. Der code ist gut dokumentiert, Sie sollten in der Lage sein, ihm zu Folgen. Hier ist die original source

    Siehe live-demo hier:
    Kreis-Kreis-Schnittpunkte

    //Let EPS (epsilon) be a small value
var EPS = 0.0000001;

//Let a point be a pair: (x, y)
function Point(x, y) {
  this.x = x;
  this.y = y;
}

//Define a circle centered at (x,y) with radius r
function Circle(x,y,r) {
  this.x = x;
  this.y = y;
  this.r = r;
}

//Due to double rounding precision the value passed into the Math.acos
//function may be outside its domain of [-1, +1] which would return
//the value NaN which we do not want.
function acossafe(x) {
  if (x >= +1.0) return 0;
  if (x <= -1.0) return Math.PI;
  return Math.acos(x);
}

//Rotates a point about a fixed point at some angle 'a'
function rotatePoint(fp, pt, a) {
  var x = pt.x - fp.x;
  var y = pt.y - fp.y;
  var xRot = x * Math.cos(a) + y * Math.sin(a);
  var yRot = y * Math.cos(a) - x * Math.sin(a);
  return new Point(fp.x+xRot,fp.y+yRot);
}

//Given two circles this method finds the intersection
//point(s) of the two circles (if any exists)
function circleCircleIntersectionPoints(c1, c2) {

  var r, R, d, dx, dy, cx, cy, Cx, Cy;

  if (c1.r < c2.r) {
    r  = c1.r;  R = c2.r;
    cx = c1.x; cy = c1.y;
    Cx = c2.x; Cy = c2.y;
  } else {
    r  = c2.r; R  = c1.r;
    Cx = c1.x; Cy = c1.y;
    cx = c2.x; cy = c2.y;
  }

  //Compute the vector <dx, dy>
  dx = cx - Cx;
  dy = cy - Cy;

  //Find the distance between two points.
  d = Math.sqrt( dx*dx + dy*dy );

  //There are an infinite number of solutions
  //Seems appropriate to also return null
  if (d < EPS && Math.abs(R-r) < EPS) return [];

  //No intersection (circles centered at the 
  //same place with different size)
  else if (d < EPS) return [];

  var x = (dx / d) * R + Cx;
  var y = (dy / d) * R + Cy;
  var P = new Point(x, y);

  //Single intersection (kissing circles)
  if (Math.abs((R+r)-d) < EPS || Math.abs(R-(r+d)) < EPS) return [P];

  //No intersection. Either the small circle contained within 
  //big circle or circles are simply disjoint.
  if ( (d+r) < R || (R+r < d) ) return [];

  var C = new Point(Cx, Cy);
  var angle = acossafe((r*r-d*d-R*R)/(-2.0*d*R));
  var pt1 = rotatePoint(C, P, +angle);
  var pt2 = rotatePoint(C, P, -angle);
  return [pt1, pt2];

}

    InformationsquelleAutor der Antwort will.fiset

  4. 5

    Warum nicht einfach 7 Zeilen Ihrer Lieblings-prozedurale Sprache (oder programmierbare Taschenrechner!) als unten.

    Vorausgesetzt, Sie sind gegeben P0 coords (x0,y0), P1 mit Koordinaten (x1,y1), r0 und r1, und Sie wollen zu finden, P3 Koordinaten (x3,y3): 

    d=sqr((x1-x0)^2 + (y1-y0)^2)
a=(r0^2-r1^2+d^2)/(2*d)
h=sqr(r0^2-a^2)
x2=x0+a*(x1-x0)/d   
y2=y0+a*(y1-y0)/d   
x3=x2+h*(y1-y0)/d       //also x3=x2-h*(y1-y0)/d
y3=y2-h*(x1-x0)/d       //also y3=y2+h*(x1-x0)/d

    InformationsquelleAutor der Antwort CuriousMarc

  5. 0

    Versuchen Sie dieses; 

        def ri(cr1,cr2,cp1,cp2):
        int1=[]
        int2=[]
        ori=0
        if cp1[0]<cp2[0] and cp1[1]!=cp2[1]:
            p1=cp1
            p2=cp2
            r1=cr1
            r2=cr2
            if cp1[1]<cp2[1]:
                ori+=1
            elif cp1[1]>cp2[1]:
                ori+=2        
        elif cp1[0]>cp2[0] and cp1[1]!=cp2[1]:
            p1=cp2
            p2=cp1
            r1=cr2
            r2=cr1
            if p1[1]<p2[1]:
                ori+=1
            elif p1[1]>p2[1]:
                ori+=2
        elif cp1[0]==cp2[0]:
            ori+=4
            if cp1[1]>cp2[1]:
                p1=cp1
                p2=cp2
                r1=cr1
                r2=cr2
            elif cp1[1]<cp2[1]:
                p1=cp2
                p2=cp1
                r1=cr2
                r2=cr1
        elif cp1[1]==cp2[1]:
            ori+=3
            if cp1[0]>cp2[0]:
                p1=cp2
                p2=cp1
                r1=cr2
                r2=cr1
            elif cp1[0]<cp2[0]:
                p1=cp1
                p2=cp2
                r1=cr1
                r2=cr2
        if ori==1:#+
            D=calc_dist(p1,p2)
            tr=r1+r2
            el=tr-D
            a=r1-el
            b=r2-el
            A=a+(el/2)
            B=b+(el/2)
            thta=math.degrees(math.acos(A/r1))
            rs=p2[1]-p1[1]
            rn=p2[0]-p1[0]
            gd=rs/rn
            yint=p1[1]-((gd)*p1[0])
            dty=calc_dist(p1,[0,yint])

            aa=p1[1]-yint
            bb=math.degrees(math.asin(aa/dty))
            d=90-bb
            e=180-d-thta
            g=(dty/math.sin(math.radians(e)))*math.sin(math.radians(thta))
            f=(g/math.sin(math.radians(thta)))*math.sin(math.radians(d))
            oty=yint+g
            h=f+r1
            i=90-e
            j=180-90-i
            l=math.sin(math.radians(i))*h
            k=math.cos(math.radians(i))*h
            iy2=oty-l
            ix2=k
            int2.append(ix2)
            int2.append(iy2)

            m=90+bb
            n=180-m-thta
            p=(dty/math.sin(math.radians(n)))*math.sin(math.radians(m))
            o=(p/math.sin(math.radians(m)))*math.sin(math.radians(thta))
            q=p+r1
            r=90-n
            s=math.sin(math.radians(r))*q
            t=math.cos(math.radians(r))*q
            otty=yint-o
            iy1=otty+s
            ix1=t
            int1.append(ix1)
            int1.append(iy1)
        elif ori==2:#-
            D=calc_dist(p1,p2)
            tr=r1+r2
            el=tr-D
            a=r1-el
            b=r2-el
            A=a+(el/2)
            B=b+(el/2)
            thta=math.degrees(math.acos(A/r1))
            rs=p2[1]-p1[1]
            rn=p2[0]-p1[0]
            gd=rs/rn
            yint=p1[1]-((gd)*p1[0])
            dty=calc_dist(p1,[0,yint])

            aa=yint-p1[1]
            bb=math.degrees(math.asin(aa/dty))
            c=180-90-bb
            d=180-c-thta
            e=180-90-d
            f=math.tan(math.radians(e))*p1[0]
            g=math.sqrt(p1[0]**2+f**2)
            h=g+r1
            i=180-90-e
            j=math.sin(math.radians(e))*h
            jj=math.cos(math.radians(i))*h
            k=math.cos(math.radians(e))*h
            kk=math.sin(math.radians(i))*h
            l=90-bb
            m=90-e
            tt=l+m+thta
            n=(dty/math.sin(math.radians(m)))*math.sin(math.radians(thta))
            nn=(g/math.sin(math.radians(l)))*math.sin(math.radians(thta))
            oty=yint-n
            iy1=oty+j
            ix1=k
            int1.append(ix1)
            int1.append(iy1)

            o=bb+90
            p=180-o-thta
            q=90-p
            r=180-90-q
            s=(dty/math.sin(math.radians(p)))*math.sin(math.radians(o))
            t=(s/math.sin(math.radians(o)))*math.sin(math.radians(thta))
            u=s+r1
            v=math.sin(math.radians(r))*u
            vv=math.cos(math.radians(q))*u
            w=math.cos(math.radians(r))*u
            ww=math.sin(math.radians(q))*u
            ix2=v
            otty=yint+t
            iy2=otty-w
            int2.append(ix2)
            int2.append(iy2)

        elif ori==3:#y
            D=calc_dist(p1,p2)
            tr=r1+r2
            el=tr-D
            a=r1-el
            b=r2-el
            A=a+(el/2)
            B=b+(el/2)
            b=math.sqrt(r1**2-A**2)
            int1.append(p1[0]+A)
            int1.append(p1[1]+b)
            int2.append(p1[0]+A)
            int2.append(p1[1]-b)
        elif ori==4:#x
            D=calc_dist(p1,p2)
            tr=r1+r2
            el=tr-D
            a=r1-el
            b=r2-el
            A=a+(el/2)
            B=b+(el/2)
            b=math.sqrt(r1**2-A**2)
            int1.append(p1[0]+b)
            int1.append(p1[1]-A)
            int2.append(p1[0]-b)
            int2.append(p1[1]-A)
        return [int1,int2]
    def calc_dist(p1,p2):
        return math.sqrt((p2[0] - p1[0]) ** 2 +
                         (p2[1] - p1[1]) ** 2)

    InformationsquelleAutor der Antwort kulprit.001

Schreibe einen Kommentar