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

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?

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.

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

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.

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.

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 ...

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

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

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

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.

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

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.

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

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)

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



    }
}}

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

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

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

PHP

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