Równanie do testowania, czy punkt znajduje się w okręgu

309

Jeśli masz okrąg o środku (center_x, center_y)i promieniu radius, jak przetestujesz, czy dany punkt o współrzędnych (x, y)znajduje się w okręgu?

Jason
źródło
20
To pytanie jest naprawdę niezależne od języka, używam tej samej formuły w java, więc ponownie taguj.
Gautam
Wygląda na to, że przyjmujesz tylko pozytywne współrzędne. Poniższe rozwiązania nie działają z podpisanymi współrzędnymi.
cjbarth
Poniżej większość rozwiązań zrobić pracę z dodatnich i ujemnych współrzędnych. Po prostu poprawiam ten smakołyk dla przyszłych widzów tego pytania.
William Morrison
Głosuję za zamknięciem tego pytania jako nie na temat, ponieważ dotyczy matematyki w szkole średniej, a nie programowania.
n. „zaimki” m.

Odpowiedzi:

481

Ogólnie rzecz biorąc xi ymusi spełniać (x - center_x)^2 + (y - center_y)^2 < radius^2.

Należy pamiętać, że punkty, które spełniają powyższe równanie z <zastąpionym przez, ==są uważane za punkty na okręgu, a punkty, które spełniają powyższe równanie z <zastąpionym przez, >są uważane za znajdujące się poza okręgiem.

Jason
źródło
6
Może pomóc niektórym mniej rozumowanym matematykom zobaczyć operację pierwiastka kwadratowego używaną do pomiaru odległości w porównaniu z promieniem. Zdaję sobie sprawę, że to nie jest optymalne, ale ponieważ twoja odpowiedź jest sformatowana bardziej jak równanie niż kod, może ma to bardziej sens? Tylko sugestia.
William Morrison
30
Jest to najbardziej zrozumiałe wyjaśnienie przedstawione w prostym zdaniu i równaniu, które można natychmiast zastosować. Dobra robota.
thgc
to wielkie życzenie, żebym szybciej znalazł ten zasób. Skąd bierze się wartość x?
Devin Tripp
2
@DevinTripp 'x' jest współrzędną x testowanego punktu.
Chris
5
Może to być oczywiste, ale należy stwierdzić, że <=znajdzie punkty wewnątrz koła lub na jego krawędzi.
Tyler,
131

Matematycznie Pitagoras jest prawdopodobnie prostą metodą, o której wielu już wspominało.

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

Obliczeniowo istnieją szybsze sposoby. Definiować:

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

Jeśli punkt prawdopodobnie znajduje się poza tym okręgiem, wyobraź sobie narysowany wokół niego kwadrat tak, że jego boki są styczne do tego koła:

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

Teraz wyobraź sobie kwadratowy diament narysowany wewnątrz tego koła, tak aby jego wierzchołki dotykały tego koła:

if dx + dy <= R then 
    return true.

Teraz zajęliśmy większość naszej przestrzeni i tylko niewielka część tego koła pozostaje pomiędzy naszym kwadratem a diamentem do przetestowania. Wracamy do Pitagorasa, jak wyżej.

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

Jeśli punkt jest bardziej prawdopodobne w tym okręgu, odwróć kolejność pierwszych 3 kroków:

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.

Alternatywne metody wyobrażają sobie kwadrat w tym okręgu zamiast diamentu, ale wymaga to nieco więcej testów i obliczeń bez przewagi obliczeniowej (wewnętrzny kwadrat i diamenty mają identyczne obszary):

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

Aktualizacja:

Dla zainteresowanych wydajnością zaimplementowałem tę metodę w c i skompilowałem z -O3.

Czasy wykonania uzyskałem przez time ./a.out

Zaimplementowałem tę metodę, metodę normalną i metodę manekina, aby określić narzut czasowy.

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

Wygląda więc na to, że ta metoda jest bardziej wydajna w tej implementacji.

// 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
źródło
5
Ta odpowiedź jest doskonała. Nigdy nie zdawałem sobie sprawy z niektórych optymalizacji, które sugerujesz. Dobra robota.
William Morrison
2
Jestem ciekawy, czy profilowałeś te optymalizacje? Mam przeczucie, że wiele warunków jest wolniejszych niż matematyka i jedna warunkowa, ale mogę się mylić.
yoyo
3
@ yoyo, nie przeprowadziłem profilowania - to pytanie dotyczy metody dla dowolnego języka programowania. Jeśli ktoś myśli, że może to poprawić wydajność jego aplikacji, powinien, jak sugerujesz, wykazać, że jest szybszy w normalnych scenariuszach.
philcolbourn
2
W funkcji inCircleNużywasz niepotrzebnego ABS. Prawdopodobnie bez różnicy ABS pomiędzy inCirclei inCircleNbyłby mniejszy.
tzaloga
1
Usunięcie ABS poprawia wydajność InCircleN, ale nie wystarcza. Jednak moja metoda była ukierunkowana na punkty bardziej prawdopodobne poza okręgiem, ponieważ R = 1. Przy losowym promieniu [0..499] około 25% punktów znajdowało się w okręgu, a inCircleN jest szybszy.
philcolbourn
74

Za pomocą Pitagorasa możesz zmierzyć odległość między punktem a centrum i sprawdzić, czy jest on mniejszy niż promień:

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

EDYCJA (czapka dla Paula)

W praktyce kwadratowanie jest często znacznie tańsze niż pierwiastek kwadratowy, a ponieważ interesuje nas tylko porządkowanie, możemy oczywiście zrezygnować z pierwiastka kwadratowego:

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 zauważył również, że <=należy go zastąpić <iw zależności od użycia może to mieć senschociaż uważam, że nie jest to prawdą w ścisłym sensie matematycznym. Poprawiono mnie.

Konrad Rudolph
źródło
1
Zamień dist <= promień na dist <promień, aby sprawdzić, czy punkt znajduje się w okręgu.
jason
16
sqrt jest drogi. Jeśli to możliwe, unikaj - porównaj x ^ 2 + y ^ y do r ^ 2.
Paul Tomblin
Jason: nasze definicje mogą się nie zgadzać, ale dla mnie punkt, który znajduje się na obwodzie koła, jest najbardziej widoczny także w kręgu i jestem całkiem pewien, że mój zgadza się z formalną, matematyczną definicją.
Konrad Rudolph
3
Formalna matematyczna definicja wnętrza koła jest taka, jaką podałem w swoim poście. Z Wikipedii: Ogólnie rzecz biorąc, wnętrze czegoś odnosi się do przestrzeni lub jego części, z wyłączeniem jakiejkolwiek ściany lub granicy wokół jego zewnętrznej strony. en.wikipedia.org/wiki/Interior_(topology)
jason
1
W pascal, delphi i FPC, zarówno moc, jak i sqrt są drogie i nie ma operatora mocy EG: **lub ^. Najszybszy sposób to zrobić, kiedy po prostu trzeba x ^ 2 lub x ^ 3 jest to zrobić „ręcznie”: 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;
}

Jest to bardziej wydajne i czytelne. Pozwala to uniknąć kosztownej operacji pierwiastkowej. Dodałem również zaznaczenie, aby ustalić, czy punkt znajduje się w prostokącie ograniczającym okrąg.

Kontrola prostokąta jest niepotrzebna, z wyjątkiem wielu punktów lub wielu okręgów. Jeśli większość punktów znajduje się w okręgach, sprawdzanie prostokąta ograniczającego spowoduje spowolnienie!

Jak zawsze, weź pod uwagę swój przypadek użycia.

William Morrison
źródło
12

Oblicz odległość

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

to jest w C # ... konwersja do użycia w python ...

Jason Punyon
źródło
11
Możesz uniknąć dwóch kosztownych wywołań Sqrt, porównując kwadrat D do kwadratu promienia.
Paul Tomblin
10

Należy sprawdzić, czy odległość od środka koła do punktu jest mniejsza niż promień, tj

if (x-center_x)**2 + (y-center_y)**2 <= radius**2:
    # inside circle
dF.
źródło
5

Jak wspomniano powyżej - użyj odległości euklidesowej.

from math import hypot

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

źródło
4

Znajdź odległość między środkiem okręgu a podanymi punktami. Jeśli odległość między nimi jest mniejsza niż promień, wówczas punkt znajduje się wewnątrz okręgu. jeśli odległość między nimi jest równa promieniu koła, wówczas punkt znajduje się na obwodzie koła. jeśli odległość jest większa niż promień, wówczas punkt znajduje się poza okręgiem.

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
źródło
4

Poniższe równanie jest wyrażeniem, które sprawdza, czy punkt znajduje się w danym okręgu, gdzie xP i yP są współrzędnymi punktu, xC i yC są współrzędnymi środka koła, a R jest promieniem danego koła.

wprowadź opis zdjęcia tutaj

Jeśli powyższe wyrażenie jest prawdziwe, wówczas punkt znajduje się w okręgu.

Poniżej znajduje się przykładowa implementacja w języku 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;
    }
Mistrz kapusty
źródło
2

Jest to to samo rozwiązanie, o którym wspomniał Jason Punyon , ale zawiera przykład pseudokodu i kilka innych szczegółów. Po napisaniu tego zobaczyłem jego odpowiedź, ale nie chciałem usuwać mojej.

Myślę, że najłatwiej zrozumiałym sposobem jest najpierw obliczyć odległość między środkiem okręgu a punktem. Chciałbym użyć tej formuły:

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

Następnie po prostu porównaj wynik tej formuły, odległość ( d), z radius. Jeśli odległość ( d) jest mniejsza lub równa promieniu ( r), punkt znajduje się wewnątrz koła (na krawędzi koła, jeśli di rsą równe).

Oto przykład pseudokodu, który można łatwo przekonwertować na dowolny język programowania:

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

Gdzie circle_xi circle_yjest środkowymi współrzędnymi koła, rjest promieniem koła xi yjest współrzędnymi punktu.

Daniel Kvist
źródło
2

Moja odpowiedź w języku C # jako kompletne rozwiązanie do wycinania i wklejania (niezoptymalizowane):

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

Stosowanie:

if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }
Adam Cox
źródło
1

Jak wspomniano wcześniej, aby pokazać, czy punkt znajduje się w okręgu, możemy użyć następujących elementów

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

Aby przedstawić to graficznie, możemy użyć:

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
źródło
0

Użyłem kodu poniżej dla początkujących takich jak ja :).

incirkel klasy publicznej {

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



    }
}}

źródło
0

Przechodząc do świata 3D, jeśli chcesz sprawdzić, czy punkt 3D znajduje się w Sferze Jednostkowej, w końcu robisz coś podobnego. Wszystko, co jest potrzebne do pracy w 2D, to użycie operacji wektorowych 2D.

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

źródło
0

Wiem, że upłynęło kilka lat od najlepszej głosowanej odpowiedzi, ale udało mi się skrócić czas obliczeń o 4.

Musisz tylko obliczyć piksele z 1/4 koła, a następnie pomnożyć przez 4.

Oto rozwiązanie, do którego dotarłem:

#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
źródło
0

Oto prosty kod Java do rozwiązania tego problemu:

i matematyka: /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
źródło
0

PHP

if ((($x - $center_x) ** 2 + ($y - $center_y) ** 2) <=  $radius **2) {
    return true; // Inside
} else {
    return false; // Outside
}
Sadee
źródło