Persamaan untuk pengujian jika suatu titik berada di dalam lingkaran

Jika Anda memiliki lingkaran dengan pusat (center_x, center_y)dan jari-jari radius, bagaimana Anda menguji jika suatu titik dengan koordinat (x, y)berada di dalam lingkaran?

Secara umum, xdan yharus memuaskan (x - center_x)^2 + (y - center_y)^2 < radius^2.

Harap dicatat bahwa poin yang memenuhi persamaan di atas dengan <digantikan ==dianggap sebagai poin pada lingkaran, dan poin yang memenuhi persamaan di atas dengan <diganti oleh >dianggap sebagai bagian luar lingkaran.

Secara matematis, Pythagoras mungkin merupakan metode sederhana seperti yang telah banyak disebutkan.

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

Secara komputasi, ada cara yang lebih cepat. Menetapkan:

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

Jika suatu titik lebih mungkin berada di luar lingkaran ini maka bayangkan sebuah persegi yang ditarik di sekitarnya sehingga sisi-sisinya bersinggungan dengan lingkaran ini:

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

Sekarang bayangkan sebuah berlian persegi yang ditarik di dalam lingkaran ini sehingga simpul-simpulnya menyentuh lingkaran ini:

if dx + dy <= R then 
    return true.

Sekarang kita telah membahas sebagian besar ruang kita dan hanya sebagian kecil dari lingkaran ini yang tersisa di antara kotak dan berlian kita untuk diuji. Di sini kita kembali ke Pythagoras seperti di atas.

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

Jika suatu titik lebih mungkin berada di dalam lingkaran ini maka balik urutan 3 langkah pertama:

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.

Metode alternatif bayangkan persegi di dalam lingkaran ini alih-alih berlian tetapi ini membutuhkan sedikit lebih banyak tes dan perhitungan tanpa keunggulan komputasi (inner square dan berlian memiliki area yang identik):

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

Memperbarui:

Bagi mereka yang tertarik dengan kinerja saya menerapkan metode ini di c, dan dikompilasi dengan -O3.

Saya memperoleh waktu eksekusi oleh time ./a.out

Saya menerapkan metode ini, metode normal dan metode dummy untuk menentukan waktu overhead.

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

Jadi, tampaknya metode ini lebih efisien dalam implementasi ini.

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

Anda dapat menggunakan Pythagoras untuk mengukur jarak antara titik Anda dan pusat dan melihat apakah itu lebih rendah dari jari-jari:

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 (tip untuk Paul)

Dalam praktiknya, mengkuadratkan seringkali jauh lebih murah daripada mengambil akar kuadrat dan karena kami hanya tertarik pada pemesanan, tentu saja kami bisa melupakan mengambil akar kuadrat:

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

Juga, Jason mencatat itu <= harus diganti oleh <dan tergantung pada penggunaan, ini mungkin masuk akalmeskipun saya percaya bahwa itu tidak benar dalam arti matematis yang ketat. Saya berdiri dikoreksi.

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

Ini lebih efisien, dan mudah dibaca. Ini menghindari operasi root kuadrat yang mahal. Saya juga menambahkan tanda centang untuk menentukan apakah titik tersebut berada dalam persegi panjang pembatas dari lingkaran.

Pemeriksaan segi empat tidak perlu kecuali dengan banyak titik atau banyak lingkaran. Jika sebagian besar poin berada di dalam lingkaran, pemeriksaan persegi panjang terikat sebenarnya akan membuat segalanya lebih lambat!

Seperti biasa, pastikan untuk mempertimbangkan use case Anda.

Hitung Jaraknya

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

itu dalam C # ... konversikan untuk digunakan dalam python ...

Anda harus memeriksa apakah jarak dari pusat lingkaran ke titik lebih kecil dari jari-jari, yaitu

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

Seperti yang dikatakan di atas - gunakan jarak Euclidean.

from math import hypot

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

Temukan jarak antara pusat lingkaran dan titik-titik yang diberikan. Jika jarak di antara mereka kurang dari jari-jari maka titik berada di dalam lingkaran. jika jarak antara keduanya sama dengan jari-jari lingkaran maka titiknya adalah pada keliling lingkaran. jika jaraknya lebih besar dari jari-jari maka titiknya adalah di luar lingkaran.

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

Persamaan di bawah ini adalah ekspresi yang tes apakah suatu titik dalam lingkaran tertentu di mana xP & yp adalah koordinat titik, xC & yC adalah koordinat pusat lingkaran dan R adalah jari-jari lingkaran yang diberikan.

Jika ungkapan di atas benar maka intinya ada di dalam lingkaran.

Di bawah ini adalah contoh implementasi dalam 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;
    }

Ini adalah solusi yang sama seperti yang disebutkan oleh Jason Punyon , tetapi berisi contoh pseudo-code dan beberapa detail lainnya. Saya melihat jawabannya setelah menulis ini, tetapi saya tidak ingin menghapus jawaban saya.

Saya pikir cara yang paling mudah dimengerti adalah pertama-tama menghitung jarak antara pusat lingkaran dan titik. Saya akan menggunakan rumus ini:

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

Kemudian, cukup bandingkan hasil rumus itu, jarak ( d), dengan radius. Jika jarak ( d) kurang dari atau sama dengan jari-jari ( r), titik berada di dalam lingkaran (di tepi lingkaran jika ddanr sama).

Berikut ini adalah contoh kode pseudo yang dapat dengan mudah dikonversi ke bahasa pemrograman apa pun:

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

Di mana circle_xdan circle_ymerupakan pusat koordinat lingkaran,r adalah jari-jari lingkaran, dan xdan yadalah koordinat titik.

Jawaban saya dalam C # sebagai solusi cut & paste lengkap (tidak dioptimalkan):

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

Pemakaian:

if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }

Seperti yang dinyatakan sebelumnya, untuk menunjukkan jika titik di lingkaran kita dapat menggunakan yang berikut ini

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

Untuk mewakilinya secara grafis, kita dapat menggunakan:

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)

Saya menggunakan kode di bawah ini untuk pemula seperti saya :).

incirkel kelas publik {

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



    }
}}

Pindah ke dunia 3D jika Anda ingin memeriksa apakah titik 3D ada di Unit Sphere Anda akhirnya melakukan sesuatu yang serupa. Semua yang diperlukan untuk bekerja dalam 2D ​​adalah menggunakan operasi vektor 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;
    }

Saya tahu itu beberapa tahun dari jawaban pilihan terbaik, tetapi saya berhasil memotong waktu kalkulasi menjadi 4.

Anda hanya perlu menghitung piksel dari 1/4 lingkaran, lalu kalikan dengan 4.

Ini adalah solusi yang saya capai:

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

Berikut adalah kode java sederhana untuk menyelesaikan masalah ini:

dan matematika di baliknya: /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
}