wake-up-neo.com

Gleichung zum Testen, ob sich ein Punkt innerhalb eines Kreises befindet

Wenn Sie einen Kreis mit dem Mittelpunkt (center_x, center_y) und dem Radius radius haben, wie testen Sie, ob ein bestimmter Punkt mit Koordinaten (x, y) im Kreis liegt?

275
directedition

Im Allgemeinen müssen x und y(x - center_x)^2 + (y - center_y)^2 < radius^2 erfüllen.

Bitte beachten Sie, dass Punkte, die der obigen Gleichung entsprechen, wobei < durch == ersetzt ist, als Punkte auf dem Kreis und die Punkte, die der obigen Gleichung entsprechen, wobei < durch > ersetzt wird, werden als außerhalb Kreis angesehen.

447
jason

Mathematisch ist Pythagoras wahrscheinlich eine einfache Methode, wie viele bereits erwähnt haben.

(x-center_x)^2 + (y - center_y)^2 < radius^2

Rechentechnisch gibt es schnellere Wege. Definieren:

dx = abs(x-center_x)
dy = abs(y-center_y)
R = radius

Wenn ein Punkt eher außerhalb dieses Kreises ist / stelle dir ein Quadrat vor, das so gezeichnet ist, dass seine Seiten Tangenten zu diesem Kreis sind: 

if dx>R then 
    return false.
if dy>R then 
    return false.

Stellen Sie sich nun einen quadratischen Diamanten vor, der innerhalb dieses Kreises so gezeichnet ist, dass die Scheitelpunkte diesen Kreis berühren:

if dx + dy <= R then 
    return true.

Jetzt haben wir den größten Teil unseres Raums bedeckt und nur ein kleiner Bereich dieses Kreises bleibt zwischen unserem Quadrat und dem zu testenden Diamanten. Hier kehren wir zu Pythagoras wie oben zurück.

if dx^2 + dy^2 <= R^2 then 
    return true
else 
    return false.

Wenn ein Punkt eher innerhalb dieses Kreises ist dann umgekehrte Reihenfolge der ersten 3 Schritte:

if dx + dy <= R then 
    return true.
if dx > R then 
    return false.
if dy > R 
    then return false.
if dx^2 + dy^2 <= R^2 then 
    return true
else
    return false.

Alternative Methoden stellen sich ein Quadrat innerhalb dieses Kreises anstelle eines Diamanten vor, dies erfordert jedoch etwas mehr Tests und Berechnungen ohne Rechenvorteile (inneres Quadrat und Diamanten haben identische Bereiche):

k = R/sqrt(2)
if dx <= k and dy <= k then 
    return true.

Aktualisieren:

Für Performance-Interessierte habe ich diese Methode in c implementiert und mit -O3 kompiliert.

Ich erhielt Ausführungszeiten von time ./a.out

Ich habe diese Methode implementiert, eine normale Methode und eine Dummy-Methode, um den Zeitaufwand zu ermitteln.

Normal: 21.3s This: 19.1s Overhead: 16.5s

Es scheint also, dass diese Methode bei dieser Implementierung effizienter ist.

// compile gcc -O3 <filename>.c
// run: time ./a.out

#include <stdio.h>
#include <stdlib.h>

#define TRUE  (0==0)
#define FALSE (0==1)

#define ABS(x) (((x)<0)?(0-(x)):(x))

int xo, yo, R;

int inline inCircle( int x, int y ){  // 19.1, 19.1, 19.1
  int dx = ABS(x-xo);
  if (    dx >  R ) return FALSE;
  int dy = ABS(y-yo);
  if (    dy >  R ) return FALSE;
  if ( dx+dy <= R ) return TRUE;
  return ( dx*dx + dy*dy <= R*R );
}

int inline inCircleN( int x, int y ){  // 21.3, 21.1, 21.5
  int dx = ABS(x-xo);
  int dy = ABS(y-yo);
  return ( dx*dx + dy*dy <= R*R );
}

int inline dummy( int x, int y ){  // 16.6, 16.5, 16.4
  int dx = ABS(x-xo);
  int dy = ABS(y-yo);
  return FALSE;
}

#define N 1000000000

int main(){
  int x, y;
  xo = Rand()%1000; yo = Rand()%1000; R = 1;
  int n = 0;
  int c;
  for (c=0; c<N; c++){
    x = Rand()%1000; y = Rand()%1000;
//    if ( inCircle(x,y)  ){
    if ( inCircleN(x,y) ){
//    if ( dummy(x,y) ){
      n++;
    }
  }
  printf( "%d of %d inside circle\n", n, N);
}
119
philcolbourn

Sie können Pythagoras verwenden, um den Abstand zwischen Ihrem Punkt und der Mitte zu messen und festzustellen, ob er niedriger als der Radius ist:

def in_circle(center_x, center_y, radius, x, y):
    dist = math.sqrt((center_x - x) ** 2 + (center_y - y) ** 2)
    return dist <= radius

EDIT(Hat Tipp an Paul)

In der Praxis ist das Quadrieren oft viel billiger als die Quadratwurzel zu nehmen, und da wir nur an einer Bestellung interessiert sind, können wir natürlich auf die Quadratwurzel verzichten:

def in_circle(center_x, center_y, radius, x, y):
    square_dist = (center_x - x) ** 2 + (center_y - y) ** 2
    return square_dist <= radius ** 2

Jason stellte auch fest, dass <= durch < ersetzt werden sollte und dass dies je nach Verwendung tatsächlich sinnvoll sein kann auch wenn ich glaube, dass es im strengen mathematischen Sinne nicht stimmt. Ich stehe korrigiert.

71
Konrad Rudolph
boolean isInRectangle(double centerX, double centerY, double radius, 
    double x, double y)
{
        return x >= centerX - radius && x <= centerX + radius && 
            y >= centerY - radius && y <= centerY + radius;
}    

//test if coordinate (x, y) is within a radius from coordinate (center_x, center_y)
public boolean isPointInCircle(double centerX, double centerY, 
    double radius, double x, double y)
{
    if(isInRectangle(centerX, centerY, radius, x, y))
    {
        double dx = centerX - x;
        double dy = centerY - y;
        dx *= dx;
        dy *= dy;
        double distanceSquared = dx + dy;
        double radiusSquared = radius * radius;
        return distanceSquared <= radiusSquared;
    }
    return false;
}

Dies ist effizienter und lesbarer. Es vermeidet die kostspielige Quadratwurzeloperation. Ich habe auch eine Prüfung hinzugefügt, um festzustellen, ob der Punkt innerhalb des Begrenzungsrechtecks ​​des Kreises liegt.

Die Rechteckprüfung ist außer bei vielen Punkten oder vielen Kreisen nicht erforderlich. Wenn sich die meisten Punkte innerhalb von Kreisen befinden, wird die Prüfung durch das Begrenzungsrechteck tatsächlich langsamer!

Beachten Sie wie immer Ihren Anwendungsfall.

35

Berechnen Sie die Entfernung

D = Math.Sqrt(Math.Pow(center_x - x, 2) + Math.Pow(center_y - y, 2))
return D <= radius

das ist in C # ... konvertiert für die Verwendung in Python ...

12
Jason Punyon

Sie sollten prüfen, ob der Abstand vom Mittelpunkt des Kreises zum Punkt kleiner als der Radius ist, d. H.

if (x-center_x)**2 + (y-center_y)**2 <= radius**2:
    # inside circle
10
dF.

Wie oben erwähnt - euklidische Entfernung verwenden.

from math import hypot

def in_radius(c_x, c_y, r, x, y):
    return math.hypot(c_x-x, c_y-y) <= r
5
i0cus

Finde den Abstand zwischen dem Mittelpunkt des Kreises und den angegebenen Punkten. Wenn der Abstand zwischen ihnen kleiner als der Radius ist, befindet sich der Punkt innerhalb des Kreises. Wenn der Abstand zwischen ihnen gleich dem Radius des Kreises ist, liegt der Punkt auf dem Umfang des Kreises. Wenn der Abstand liegt größer als der Radius ist, liegt der Punkt außerhalb des Kreises.

int d = r^2 - (center_x-x)^2 + (center_y-y)^2;

if(d>0)
  print("inside");
else if(d==0)
  print("on the circumference");
else
  print("outside");
3

Dies ist die gleiche Lösung wie von Jason Punyon genannt, aber es enthält ein Pseudo-Code-Beispiel und einige weitere Details. Ich sah seine Antwort, nachdem ich das geschrieben hatte, aber ich wollte meine nicht entfernen.

Ich denke, der einfachste Weg ist, zuerst den Abstand zwischen dem Mittelpunkt des Kreises und dem Punkt zu berechnen. Ich würde diese Formel verwenden:

d = sqrt((circle_x - x)^2 + (circle_y - y)^2)

Vergleichen Sie dann einfach das Ergebnis dieser Formel, die Entfernung (d), mit der radius. Wenn der Abstand (d) kleiner oder gleich dem Radius (r) ist, befindet sich der Punkt innerhalb des Kreises (am Rand des Kreises, falls d und r gleich sind).

Hier ist ein Pseudocode-Beispiel, das leicht in jede Programmiersprache konvertiert werden kann:

function is_in_circle(circle_x, circle_y, r, x, y)
{
    d = sqrt((circle_x - x)^2 + (circle_y - y)^2);
    return d <= r;
}

Wo circle_x und circle_y die Mittelpunktskoordinaten des Kreises sind, r der Radius des Kreises ist und x und y die Koordinaten des Punktes sind.

2
Daniel Kvist

Meine Antwort in C # als vollständige Cut & Paste-Lösung (nicht optimiert):

public static bool PointIsWithinCircle(double circleRadius, double circleCenterPointX, double circleCenterPointY, double pointToCheckX, double pointToCheckY)
{
    return (Math.Pow(pointToCheckX - circleCenterPointX, 2) + Math.Pow(pointToCheckY - circleCenterPointY, 2)) < (Math.Pow(circleRadius, 2));
}

Verwendungszweck:

if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }
2
Adam Cox

Die folgende Gleichung ist ein Ausdruck, der prüft, ob ein Punkt innerhalb eines gegebenen Kreises liegt, in dem xP & yP sind die Koordinaten des Punktes, xC & yC sind die Koordinaten des Mittelpunkts des Kreises und R ist der Radius dieses gegebenen Kreises.

enter image description here

Wenn der obige Ausdruck wahr ist, befindet sich der Punkt innerhalb des Kreises.

Unten sehen Sie eine Beispielimplementierung in C #:

    public static bool IsWithinCircle(PointF pC, Point pP, Single fRadius){
        return Distance(pC, pP) <= fRadius;
    }

    public static Single Distance(PointF p1, PointF p2){
        Single dX = p1.X - p2.X;
        Single dY = p1.Y - p2.Y;
        Single multi = dX * dX + dY * dY;
        Single dist = (Single)Math.Round((Single)Math.Sqrt(multi), 3);

        return (Single)dist;
    }
1

Wenn Sie in die 3D-Welt einsteigen möchten, wenn Sie überprüfen möchten, ob sich ein 3D-Punkt in einer Einheitssphäre befindet, müssen Sie am Ende etwas Ähnliches tun. Um in 2D arbeiten zu können, müssen Sie lediglich 2D-Vektoroperationen verwenden.

    public static bool Intersects(Vector3 point, Vector3 center, float radius)
    {
        Vector3 displacementToCenter = point - center;

        float radiusSqr = radius * radius;

        bool intersects = displacementToCenter.magnitude < radiusSqr;

        return intersects;
    }
0
user5747799

Ich weiß, das sind einige Jahre von der besten Antwort, aber ich habe es geschafft, die Rechenzeit um 4 zu verkürzen.

Sie müssen nur die Pixel aus 1/4 des Kreises berechnen und dann mit 4 multiplizieren.

Dies ist die Lösung, die ich erreicht habe:

#include <stdio.h>
#include <stdlib.h>
#include <time.h> 

int x, y, r;
int mx, c, t;
int dx, dy;
int p;

int main() {
    for (r = 1; r < 128; r++){

        clock_t t; 
        t = clock();

        p = calculatePixels(r);

        t = clock() - t; 
        double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds 

        printf( "%d of pixels inside circle with radius %d, took %f seconds to execute \n", p, r, time_taken);
    }
}

int calculatePixels(int r){
    mx = 2 * r;
    c = (mx+1)*(mx+1);
    t = r * r;
    int a = 0;
    for (x = 0; x < r; x++){
      for (y = 0; y < r; y++){
          dx = x-r;
          dy = y-r;
          if ((dx*dx + dy*dy) > t)
              a++;
          else 
              y = r;
      }
    }
    return (c - (a * 4));
}
0
graffitiMSX

Hier ist der einfache Java-Code zur Lösung dieses Problems: 

und die Mathematik dahinter: https://math.stackexchange.com/questions/198764/how-to-know-if-a-point-is-inside-a-circle

boolean insideCircle(int[] point, int[] center, int radius) {
    return (float)Math.sqrt((int)Math.pow(point[0]-center[0],2)+(int)Math.pow(point[1]-center[1],2)) <= radius;
}
0
Ketan Ramteke

Um zu zeigen, ob sich der Punkt im Kreis befindet, können wir wie folgt Folgendes verwenden

if ((x-center_x)^2 + (y - center_y)^2 < radius^2) {
    in.circle <- "True"
} else {
    in.circle <- "False"
}

Um es grafisch darzustellen, können wir verwenden:

plot(x, y, asp = 1, xlim = c(-1, 1), ylim = c(-1, 1), col = ifelse((x-center_x)^2 + (y - center_y)^2 < radius^2,'green','red'))
draw.circle(0, 0, 1, nv = 1000, border = NULL, col = NA, lty = 1, lwd = 1)
0
Selrac

Ich habe den Code für Anfänger wie mich verwendet :).

öffentliche Klasse Incirkel {

public static void main(String[] args) {
    int x; 
    int y; 
    int middelx; 
    int middely; 
    int straal; {

// Adjust the coordinates of x and y 
x = -1;
y = -2;

// Adjust the coordinates of the circle
middelx = 9; 
middely = 9;
straal =  10;

{
    //When x,y is within the circle the message below will be printed
    if ((((middelx - x) * (middelx - x)) 
                    + ((middely - y) * (middely - y))) 
                    < (straal * straal)) {
                        System.out.println("coordinaten x,y vallen binnen cirkel");
    //When x,y is NOT within the circle the error message below will be printed
    } else {
        System.err.println("x,y coordinaten vallen helaas buiten de cirkel");
    } 
}



    }
}}
0
user5560892