Gleichung zur Prüfung, ob ein Punkt innerhalb eines Kreises liegt

Question

Wenn Sie einen Kreis mit Mittelpunkt haben (center_x, center_y) und Radius radius Wie prüft man, ob ein bestimmter Punkt mit den Koordinaten (x, y) innerhalb des Kreises liegt?

Answer 1

Generell, x y y muss genügen (x - center_x)² + (y - center_y)² < radius² .

Bitte beachten Sie, dass Punkte, die die obige Gleichung mit < ersetzt durch == gelten die Punkte auf der Kreis, und die Punkte, die die obige Gleichung erfüllen, mit < ersetzt durch > werden als die außerhalb den Kreis.

Answer 2

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

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

Rechnerisch gesehen gibt es schnellere Wege. Definieren:

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

Wenn ein Punkt eher zu den außerhalb dieser Kreis dann stelle man sich ein Quadrat vor, das so um den Kreis herumgezeichnet wird, dass seine Seiten Tangenten an diesen Kreis sind:

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

Stellen Sie sich nun eine quadratische Raute vor, die innerhalb dieses Kreises so gezeichnet wird, dass ihre Eckpunkte den Kreis berühren:

if dx + dy <= R then 
    return true.

Jetzt haben wir den größten Teil unseres Raumes abgedeckt und nur noch ein kleiner Bereich dieses Kreises verbleibt zwischen unserem Quadrat und der Raute, der getestet werden muss. Hier greifen wir wie oben auf Pythagoras zurück.

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

Wenn ein Punkt eher zu den innerhalb dieser Kreis dann die Reihenfolge der ersten 3 Schritte umkehren:

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.

---

Andere Methoden stellen sich ein Quadrat innerhalb dieses Kreises anstelle einer Raute vor, was jedoch etwas mehr Tests und Berechnungen erfordert, ohne dass dies einen rechnerischen Vorteil bringt (inneres Quadrat und Rauten haben identische Flächen):

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

Aktualisierung:

Für diejenigen, die an der Leistung interessiert sind, habe ich diese Methode in c implementiert und mit -O3 kompiliert.

Die Ausführungszeiten erhalte ich durch time ./a.out

Ich habe diese Methode, eine normale Methode und eine Dummy-Methode implementiert, um den zeitlichen Mehraufwand 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);
}

Answer 3

Mit Hilfe des Pythagoras kannst du den Abstand zwischen deinem Punkt und dem Mittelpunkt messen und feststellen, ob er kleiner 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

エディトリアル (Tipp an Paul)

In der Praxis ist das Quadrieren oft viel billiger als die Quadratwurzel, und da wir nur an einer Reihenfolge 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

Außerdem stellte Jason fest, dass <= sollte ersetzt werden durch < und je nach Nutzung kann dies tatsächlich sinnvoll sein auch wenn ich glaube, dass es im strengen mathematischen Sinne nicht wahr ist . Ich nehme das zurück.

Answer 4

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 besser lesbar. Es vermeidet die kostspielige Quadratwurzeloperation. Ich habe auch eine Prüfung hinzugefügt, um festzustellen, ob der Punkt innerhalb des begrenzenden Rechtecks des Kreises liegt.

Die Rechteckprüfung ist unnötig, außer bei vielen Punkten oder vielen Kreisen. Wenn die meisten Punkte innerhalb von Kreisen liegen, macht die Prüfung des begrenzenden Rechtecks die Arbeit sogar langsamer!

Wie immer sollten Sie Ihren Anwendungsfall berücksichtigen.

Answer 5

Prüfen Sie, ob der Abstand vom Mittelpunkt des Kreises zum Punkt kleiner ist als der Radius

Python verwenden

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