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

309

Wenn Sie einen Kreis mit Mittelpunkt (center_x, center_y)und Radius haben radius, wie testen Sie, ob sich ein bestimmter Punkt mit Koordinaten (x, y)innerhalb des Kreises befindet?

Jason
quelle
20
Diese Frage ist wirklich sprachunabhängig, ich verwende die gleiche Formel in Java, also neu markieren.
Gautam
Es scheint, dass Sie nur positive Koordinaten annehmen. Die folgenden Lösungen funktionieren nicht mit signierten Koordinaten.
CJBarth
Die meisten Lösungen unten tun Arbeit mit positiven und negativen Koordinaten. Korrigieren Sie nur diesen Leckerbissen für zukünftige Zuschauer dieser Frage.
William Morrison
Ich stimme dafür, diese Frage als nicht zum Thema gehörend zu schließen, da es eher um Mathematik in der Mittelschule als um Programmieren geht.
n. 'Pronomen' m.

Antworten:

481

Im Allgemeinen xund ymuss befriedigen (x - center_x)^2 + (y - center_y)^2 < radius^2.

Bitte beachten Sie, dass Punkte, die die obige Gleichung mit <ersetzt durch erfüllen, ==als Punkte auf dem Kreis betrachtet werden und die Punkte, die die obige Gleichung mit <ersetzt durch erfüllen, >als außerhalb des Kreises betrachtet werden.

Jason
quelle
6
Es kann einigen weniger mathematisch denkenden Leuten helfen, die Quadratwurzeloperation zu sehen, die zum Messen der Entfernung im Vergleich zum Radius verwendet wird. Mir ist klar, dass das nicht optimal ist, aber da Ihre Antwort eher wie eine Gleichung als wie Code formatiert ist, ist sie vielleicht sinnvoller? Nur ein Vorschlag.
William Morrison
30
Dies ist die verständlichste Erklärung in einem einfachen Satz und einer sofort verwendbaren Gleichung. Gut gemacht.
thgc
Dies ist ein großer Wunsch, ich würde diese Ressource schneller finden. Woher kommt der Wert x?
Devin Tripp
2
@DevinTripp 'x' ist die x-Koordinate des zu testenden Punktes.
Chris
5
Dies mag offensichtlich sein, aber es sollte angegeben werden, dass <=Punkte innerhalb des Kreises oder an seiner Kante gefunden werden.
Tyler
131

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

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

Computergestützt 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 liegt, stellen Sie sich ein Quadrat vor, das so um ihn herum gezeichnet ist, dass seine Seiten Tangenten an diesen 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 seine Eckpunkte diesen Kreis berühren:

if dx + dy <= R then 
    return true.

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

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

Wenn es wahrscheinlicher ist, dass sich ein Punkt innerhalb dieses Kreises befindet, kehren Sie die Reihenfolge der ersten drei Schritte um:

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 Rechenvorteil (inneres Quadrat und Diamanten haben identische Flächen):

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

Aktualisieren:

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

Ich habe Ausführungszeiten von erhalten time ./a.out

Ich habe diese Methode implementiert, eine normale Methode und eine Dummy-Methode, um den Timing-Overhead zu bestimmen.

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

Es scheint also, dass diese Methode in 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);
}
philcolbourn
quelle
5
Diese Antwort ist ausgezeichnet. Einige der von Ihnen vorgeschlagenen Optimierungen habe ich nie realisiert. Gut gemacht.
William Morrison
2
Ich bin gespannt, ob Sie diese Optimierungen profiliert haben. Mein Bauchgefühl ist, dass mehrere Bedingungen langsamer sind als einige mathematische und eine Bedingung, aber ich könnte mich irren.
Yooy
3
@yoyo, ich habe keine Profilerstellung durchgeführt - diese Frage bezieht sich auf eine Methode für jede Programmiersprache. Wenn jemand der Meinung ist, dass dies die Leistung seiner Anwendung verbessern könnte, sollte er, wie Sie vorschlagen, nachweisen, dass dies in normalen Szenarien schneller ist.
Philcolbourn
2
In der Funktion verwenden inCircleNSie unnötiges ABS. Wahrscheinlich ohne ABS Unterschied zwischen inCircleund inCircleNwäre kleiner.
Tzaloga
1
Das Entfernen von ABS verbessert zwar die Leistung im Kreis, reicht jedoch nicht aus. Meine Methode war jedoch auf Punkte ausgerichtet, die wahrscheinlicher außerhalb des Kreises liegen, da R = 1 ist. Mit einem zufälligen Radius [0..499] befanden sich ungefähr 25% Punkte innerhalb des Kreises und inCircleN ist schneller.
Philcolbourn
74

Mit Pythagoras können Sie den Abstand zwischen Ihrem Punkt und dem Zentrum messen und feststellen, ob er unter dem Radius liegt:

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 (Hutspitze zu Paul)

In der Praxis ist das Quadrieren oft viel billiger als die Quadratwurzel 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

Außerdem bemerkte Jason, dass <=dies durch ersetzt werden sollte <und dies je nach Verwendung tatsächlich sinnvoll sein kannobwohl ich glaube, dass es nicht im streng mathematischen Sinne wahr ist. Ich stehe korrigiert.

Konrad Rudolph
quelle
1
Ersetzen Sie dist <= Radius durch dist <Radius, um zu testen, ob sich der Punkt innerhalb des Kreises befindet.
Jason
16
sqrt ist teuer. Vermeiden Sie es wenn möglich - vergleichen Sie x ^ 2 + y ^ y mit r ^ 2.
Paul Tomblin
Jason: Unsere Definitionen mögen nicht übereinstimmen, aber für mich ist ein Punkt, der sich auf dem Umfang des Kreises befindet, auch im Kreis am nachdrücklichsten, und ich bin mir ziemlich sicher, dass meine mit der formalen, mathematischen Definition übereinstimmt.
Konrad Rudolph
3
Die formale mathematische Definition des Inneren eines Kreises ist die, die ich in meinem Beitrag angegeben habe. Aus Wikipedia: Im Allgemeinen bezieht sich das Innere von etwas auf den Raum oder Teil innerhalb von etwas, ausgenommen jede Art von Wand oder Grenze um sein Äußeres. en.wikipedia.org/wiki/Interior_(topology)
Jason
1
In Pascal, Delphi und FPC sind sowohl Strom als auch Quadratmeter zu teuer , und es gibt keinen Stromversorger EG: **oder ^. Der schnellste Weg, dies zu tun, wenn Sie nur x ^ 2 oder x ^ 3 benötigen, besteht darin, es "manuell" zu tun : x*x.
JHolta
37
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 Überprüfung hinzugefügt, um festzustellen, ob der Punkt innerhalb des Begrenzungsrechtecks ​​des Kreises liegt.

Die Rechteckprüfung ist nur mit vielen Punkten oder vielen Kreisen erforderlich. Wenn sich die meisten Punkte innerhalb von Kreisen befinden, verlangsamt die Prüfung des Begrenzungsrechtecks ​​die Dinge tatsächlich!

Berücksichtigen Sie wie immer Ihren Anwendungsfall.

William Morrison
quelle
12

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 # ... konvertieren für die Verwendung in Python ...

Jason Punyon
quelle
11
Sie können zwei teure Sqrt-Aufrufe vermeiden, indem Sie das D-Quadrat mit dem Radius-Quadrat vergleichen.
Paul Tomblin
10

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
dF.
quelle
5

Wie oben erwähnt - verwenden Sie den euklidischen Abstand.

from math import hypot

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

quelle
4

Finden Sie 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 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");
DEEPAK KUMAR SINGH
quelle
4

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

Geben Sie hier die Bildbeschreibung ein

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

Unten finden 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;
    }
Kohlmeister
quelle
2

Dies ist die gleiche Lösung wie von Jason Punyon erwähnt , enthält jedoch ein Pseudocode-Beispiel und einige weitere Details. Ich sah seine Antwort, nachdem ich dies geschrieben hatte, aber ich wollte meine nicht entfernen.

Ich denke, der am einfachsten verständliche 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, den Abstand ( d), mit dem radius. Wenn der Abstand ( d) kleiner oder gleich dem Radius ( r) ist, befindet sich der Punkt innerhalb des Kreises (am Rand des Kreises, wenn dund rgleich 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_xund circle_yist die Mittelpunktskoordinate des Kreises, rist der Radius des Kreises und xund yist die Koordinaten des Punktes.

Daniel Kvist
quelle
2

Meine Antwort in C # als vollständige Lösung zum Ausschneiden und Einfügen (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)) { }
Adam Cox
quelle
1

Wie bereits erwähnt, können wir Folgendes verwenden, um zu zeigen, ob sich der Punkt im Kreis befindet

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)
Selrac
quelle
0

Ich habe den folgenden 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");
    } 
}



    }
}}

quelle
0

Wenn Sie in die Welt des 3D einsteigen und überprüfen möchten, ob sich ein 3D-Punkt in einer Einheitskugel befindet, tun Sie am Ende etwas Ähnliches. Für die Arbeit in 2D müssen lediglich 2D-Vektoroperationen verwendet werden.

    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;
    }

quelle
0

Ich weiß, dass dies einige Jahre nach der am besten bewerteten Antwort ist, aber ich habe es geschafft, die Berechnungszeit 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));
}
graffitiMSX
quelle
0

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

und die Mathematik dahinter: /math/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;
}
Ketan Ramteke
quelle
0

PHP

if ((($x - $center_x) ** 2 + ($y - $center_y) ** 2) <=  $radius **2) {
    return true; // Inside
} else {
    return false; // Outside
}
Sadee
quelle