algorithm - triangle - vérifier qu un point est à l intérieur d un polygone




Equation pour tester si un point est à l'intérieur d'un cercle (9)

Calculer la distance

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

c'est en C # ... convertir pour une utilisation en python ...

Si vous avez un cercle avec le centre (center_x, center_y) et le rayon du radius , comment testez-vous si un point donné avec les coordonnées (x, y) est à l'intérieur du cercle?


Comme indiqué ci-dessus - utilisez la distance euclidienne.

from math import hypot

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

En général, x et y doivent satisfaire (x - center_x)^2 + (y - center_y)^2 < radius^2 .

S'il vous plaît noter que les points qui satisfont l'équation ci-dessus avec < remplacé par == sont considérés comme les points sur le cercle, et les points qui satisfont l'équation ci-dessus avec < remplacé par > sont considérés comme l' extérieur du cercle.


J'ai utilisé le code ci-dessous pour les débutants comme moi :).

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



    }
}}

Mathématiquement, Pythagore est probablement une méthode simple comme beaucoup l'ont déjà mentionné.

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

Informatique, il existe des moyens plus rapides. Définir:

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

Si un point est plus susceptible d'être à l' extérieur de ce cercle, alors imaginez un carré dessiné autour de lui de sorte que ses côtés soient des tangentes à ce cercle:

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

Imaginez maintenant un diamant carré dessiné à l'intérieur de ce cercle de sorte que ses sommets touchent ce cercle:

if dx + dy <= R then 
    return true.

Maintenant nous avons couvert la plus grande partie de notre espace et seulement une petite partie de ce cercle reste entre notre carré et le diamant à tester. Ici nous revenons à Pythagore comme ci-dessus.

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

Si un point est plus susceptible d'être à l' intérieur de ce cercle, inverser l'ordre des trois premières étapes:

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.

D'autres méthodes imaginent un carré à l'intérieur de ce cercle au lieu d'un diamant, mais cela nécessite un peu plus de tests et de calculs sans avantage de calcul (le carré intérieur et les diamants ont des zones identiques):

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

Mettre à jour:

Pour ceux qui s'intéressent à la performance, j'ai implémenté cette méthode en c, et compilé avec -O3.

J'ai obtenu des temps d'exécution par time ./a.out

J'ai implémenté cette méthode, une méthode normale et une méthode fictive pour déterminer le temps système.

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

Donc, il semble que cette méthode est plus efficace dans cette implémentation.

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

Passer dans le monde de la 3D si vous voulez vérifier si un point 3D est dans une sphère d'unité, vous finissez par faire quelque chose de similaire. Tout ce qui est nécessaire pour travailler en 2D est d'utiliser des opérations vectorielles 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;
    }

Vous devez vérifier si la distance entre le centre du cercle et le point est inférieure au rayon, c.-à-d.

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

Vous pouvez utiliser Pythagore pour mesurer la distance entre votre point et le centre et voir si elle est inférieure au rayon:

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 (chapeau à Paul)

En pratique, la quadrature est souvent beaucoup moins chère que la racine carrée et puisque nous ne sommes intéressés que par un ordre, nous pouvons bien sûr renoncer à prendre la racine carrée:

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

En outre, Jason a noté que <= devrait être remplacé par < et selon l'utilisation, cela peut avoir du sens même si je crois que ce n'est pas vrai au sens mathématique strict . Je me suis trompé.


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

C'est plus efficace et lisible. Cela évite l'opération coûteuse de la racine carrée. J'ai également ajouté une vérification pour déterminer si le point est dans le rectangle de délimitation du cercle.

La vérification du rectangle est inutile sauf avec beaucoup de points ou de nombreux cercles. Si la plupart des points sont à l'intérieur des cercles, le contrôle du rectangle englobant rendra les choses plus lentes!

Comme toujours, assurez-vous de considérer votre cas d'utilisation.





geometry