Уравнение для тестирования, если точка находится внутри круга

algorithm language-agnostic geometry

221306 просмотра

15 ответа

Если у вас есть круг с центром (center_x, center_y)и радиусом radius, как вы можете проверить, находится ли данная точка с координатами (x, y)внутри круга?

Источник Размещён: 17.05.2019 03:39

Ответы (15)


434 плюса

В общем, xи yдолжен удовлетворять (x - center_x)^2 + (y - center_y)^2 < radius^2.

Обратите внимание, что точки, которые удовлетворяют приведенному выше уравнению с <заменой ==, считаются точками на окружности, а точки, которые удовлетворяют уравнению с <заменой >, считаются вне круга.

Автор: jason Размещён: 26.01.2009 08:09

115 плюса

Математически Пифагор, вероятно, является простым методом, о котором многие уже упоминали.

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

Вычислительно, есть более быстрые пути. Определение:

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

Если точка, скорее всего, окажется вне этого круга, тогда представьте квадрат, нарисованный вокруг него, так что его стороны касаются этого круга:

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

Теперь представьте квадратный алмаз, нарисованный внутри этого круга, так что его вершины касаются этого круга:

if dx + dy <= R then 
    return true.

Теперь мы покрыли большую часть нашего пространства, и только небольшая область этого круга остается между нашей площадью и бриллиантом для тестирования. Здесь мы возвращаемся к Пифагору, как указано выше.

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

Если точка, скорее всего, находится внутри этого круга, тогда обратный порядок первых трех шагов:

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.

Альтернативные методы представляют собой квадрат внутри этого круга вместо алмаза, но для этого требуется немного больше тестов и вычислений без каких-либо вычислительных преимуществ (внутренний квадрат и алмазы имеют одинаковые области):

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

Обновить:

Для тех, кто заинтересован в производительности, я реализовал этот метод в c и скомпилировал с -O3.

Я получил время выполнения time ./a.out

Я реализовал этот метод, обычный метод и манекен, чтобы определить временные накладные расходы.

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

Таким образом, кажется, что этот метод более эффективен в этой реализации.

// 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 Размещён: 29.08.2011 07:00

70 плюса

Вы можете использовать Pythagoras для измерения расстояния между вашей точкой и центром и посмотреть, меньше ли он радиуса:

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 (подсказка шляпы к Полю)

На практике квадратирование часто намного дешевле, чем использование квадратного корня, и поскольку нас интересует только упорядочение, мы можем, конечно, отказаться от квадратного корня:

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

Кроме того, Джейсон отметил, что его <=следует заменить, <и в зависимости от использования это может иметь смыслхотя я считаю, что это неверно в строгом математическом смысле, Я стою исправлено.

Автор: Konrad Rudolph Размещён: 26.01.2009 08:10

35 плюса

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

Это более эффективно и удобочитаемо. Это позволяет избежать дорогостоящей работы с квадратным корнем. Я также добавил проверку, чтобы определить, находится ли точка в пределах ограничивающего прямоугольника круга.

Проверка прямоугольника не нужна, за исключением множества точек или многих кругов. Если большинство точек находится внутри кругов, проверка ограничивающего прямоугольника на самом деле замедляет работу!

Как всегда, обязательно рассмотрите свой вариант использования.

Автор: William Morrison Размещён: 10.06.2011 08:01

12 плюса

Рассчитать расстояние

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

это в C # ... конвертировать для использования в python ...

Автор: Jason Punyon Размещён: 26.01.2009 08:10

10 плюса

Вы должны проверить, меньше ли расстояние от центра круга до точки, чем радиус, т. Е.

if (x-center_x)**2 + (y-center_y)**2 <= radius**2:
    # inside circle
Автор: dF. Размещён: 26.01.2009 08:10

5 плюса

Как сказано выше, используйте евклидову дистанцию.

from math import hypot

def in_radius(c_x, c_y, r, x, y):
    return math.hypot(c_x-x, c_y-y) <= r
Автор: i0cus Размещён: 28.01.2009 02:45

2 плюса

Это то же самое решение, о котором упоминал Джейсон Пуньон , но он содержит пример псевдокода и некоторые подробности. Я видел его ответ, написав это, но я не хотел удалять меня.

Я думаю, что наиболее понятным способом является сначала рассчитать расстояние между центром круга и точкой. Я бы использовал эту формулу:

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

Затем просто сравните результат этой формулы, расстояние ( d), с radius. Если расстояние ( d) меньше или равно радиусу ( r), точка находится внутри круга (на краю круга, если dи rравны).

Вот пример псевдокода, который можно легко преобразовать в любой язык программирования:

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

Где circle_xи circle_yэто координаты центра окружности, rрадиус окружности, а xи yэто координата точки.

Автор: Daniel Kvist Размещён: 09.06.2015 02:35

2 плюса

Найдите расстояние между центром круга и указанными точками. Если расстояние между ними меньше радиуса, то точка находится внутри круга. если расстояние между ними равно радиусу круга, то точка находится на окружности круга. если расстояние больше радиуса, то точка находится за пределами круга.

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 Размещён: 06.07.2016 07:31

2 плюса

Мой ответ на C # как полное решение для вырезания и вставки (не оптимизированное):

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

Использование:

if (!PointIsWithinCircle(3, 3, 3, .5, .5)) { }
Автор: Adam Cox Размещён: 21.01.2017 09:21

0 плюса

Я использовал код ниже для новичков вроде меня :).

публичный класс 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");
    } 
}



    }
}}
Автор: Halil Özkal Размещён: 14.11.2015 11:37

0 плюса

Как указывалось ранее, чтобы показать, находится ли точка в круге, мы можем использовать следующее

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

Чтобы представить его графически, мы можем использовать:

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 Размещён: 15.09.2016 12:52

0 плюса

Перейдя в мир 3D, если вы хотите проверить, находится ли 3D-точка в единице измерения, вы делаете что-то подобное. Все, что необходимо для работы в 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;
    }
Автор: user5747799 Размещён: 16.11.2017 03:11

0 плюса

Я знаю, что это несколько лет от лучшего голосового ответа, но мне удалось сократить время расчета на 4.

Вам нужно всего лишь вычислить пиксели с 1/4 круга, а затем умножить на 4.

Это решение, которое я достиг:

#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 Размещён: 03.11.2018 09:39

0 плюса

Вот простой Java-код для решения этой проблемы:

и математика за ней: https://math.stackexchange.com/questions/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 Размещён: 17.11.2018 04:26
32x32