Comment déterminer si un point est à l'intérieur d'un polygone convexe 2D?
j'ai un polygone convexe (typiquement juste un carré rotatif), et je connais tous les 4 points. Comment puis-je déterminer si un point donné (jaune/vert) est à l'intérieur le polygone?
EDIT: pour ce projet particulier, je n'ai pas accès à toutes les bibliothèques du JDK, comme AWT.
8 réponses
j'ai une implémentation Java de ceci, mais elle est trop grande pour être postée ici dans son intégralité. Cependant, vous devriez être en mesure de le faire:
class Boundary {
private final Point[] points; // Points making up the boundary
...
/**
* Return true if the given point is contained inside the boundary.
* See: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
* @param test The point to check
* @return true if the point is inside the boundary, false otherwise
*
*/
public boolean contains(Point test) {
int i;
int j;
boolean result = false;
for (i = 0, j = points.length - 1; i < points.length; j = i++) {
if ((points[i].y > test.y) != (points[j].y > test.y) &&
(test.x < (points[j].x - points[i].x) * (test.y - points[i].y) / (points[j].y-points[i].y) + points[i].x)) {
result = !result;
}
}
return result;
}
}
et voici un croquis de la classe de Point
/**
* Two dimensional cartesian point.
*/
public class Point {
public final double x;
public final double y;
...
}
Pour ceux qui souhaitent comprendre comment la méthode écrit par Dean Povey ci-dessus fonctionne, voici l'explication:
La méthode regarde un "rayon" qui commence à l'endroit testé et s'étend à l'infini du côté droit de l'axe des X. Pour chaque polygone segment, il vérifie si le rayon traverse. Si le nombre total de segments est impair, alors le point testé est considéré à l'intérieur du polygone, sinon - il est à l'extérieur.
Pour comprendre la façon dont la traversée est calculé, considérons le chiffre suivant:
v2
o
/
/ c (intersection)
o--------x----------------------> to infinity
t /
/
/
o
v1
Pour l'intersection de se produire, testé.y doit se trouver entre les valeurs y des sommets du segment (v1 et v2). C'est la première condition de l'instruction if dans la méthode. Si c'est ce qui se produit, alors la ligne horizontale doit croiser le segment. Il ne reste qu'à établir si l'intersection se produit à la droite de la point d'essai ou à gauche de celui-ci. Cela nécessite de trouver la coordonnée x de l'intersection point, qui est:
t.y - v1.y
c.x = v1.x + ----------- * (v2.x - v1.x)
v2.y - v1.y
il ne reste plus qu'à examiner les subtilités:
- si v1.y = = v2.puis le rayon passe le long du segment et par conséquent, le segment n'a aucune influence sur le résultat. En effet, la première partie de la déclaration si retourne false dans ce cas.
- le code se multiplie d'abord puis se divise. Ceci est fait pour soutenir très petites différences entre v1.x et v2.x, qui pourrait conduire à un zéro après la division, en raison de l'arrondissement.
- enfin, le problème de traverser exactement sur un sommet devrait être aborder. Considérons les deux cas suivants:
o o
| \ o
| A1 C1 \ /
| \ / C2
o--------x-----------x------------x--------> to infinity
/ / \
A2 / B1 / \ B2
/ / \
o / o
o
Maintenant, pour vérifier si cela fonctionne, vérifiez par vous-même ce qui est retourné pour chaque des 4 segments par la condition if dans le corps de la méthode. Vous devriez trouver que les segments au-dessus du rayon (A1, C1, C2) reçoivent un résultat positif, alors que ceux en dessous (A2, B1, B2) reçoivent un résultat négatif un. Cela signifie que le sommet contribue Nombre Impair (1) au croisement B et C contribuent un nombre pair (0 et 2, respectivement), qui est exactement ce qui est souhaité. A est en effet un vrai croisement du polygone, alors que B et C sont juste deux cas de "fly-by".
en supposant que votre point est à la coordonnée Y, calculez simplement les positions x où chaque des lignes (non horizontales) du polygone traversent Y. Compter le nombre de positions x qui sont moins que la position x de votre point. Si le nombre de positions x est impair, votre point est à l'intérieur du polygone. Remarque: cela fonctionne pour tous les polygones, pas seulement convexe. Pensez-y de cette façon: tracez une ligne à partir d'infiniment loin directement dans votre point de vue. Quand cette ligne franchit une polygone ligne, il est maintenant à l'intérieur de la polygone. Traverser à nouveau la ligne, à l'extérieur. Traverser de nouveau, à l'intérieur (et ainsi de suite). Espérons que cette aide!
juste pour ajouter une implémentation Java (simple) du code original en C à partir de code suggéré par @Dean Povey (je ne sais pas pourquoi @Dean Povey est en se référant à une grande mise en œuvre):
static boolean pnpoly(double[] vertx, double[] verty, double testx, double testy)
{
int nvert = vertx.length;
int i, j;
boolean c = false;
for (i = 0, j = nvert-1; i < nvert; j = i++) {
if ( ((verty[i]>testy) != (verty[j]>testy)) &&
(testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) )
c = !c;
}
return c;
}
Je n'ai pas changé le cas pour me conformer à la règle Java pour montrer les modifications minimales requises. Je l'ai également testé dans des cas simples et il fonctionne très bien.
vérifiez si c'est du même côté des 4 demi-plans définis par les lignes qui contiennent les segments de ligne qui constituent les côtés du quad.
Ici est une bonne explication.
Dire, x[] est la matrice de points x et y[] est la matrice de y points de.
Vous êtes censé retourner 1 si le point n'existe dans le polygone et 2 sinon. où (planeX,planeY) est le point que vous devez vérifier.
//check like this
return new Polygon(x,y,x.length).contains(planeX, planeY)?1:2;
abscisses de polygone x_array: Array[Integer]
ordonnées des polygones:y_array: Array[Integer]
Point:x: Integer, y: Integer
import java.awt.Polygon
import java.awt.Point
...
final boolean isInPolygon =
new Polygon(x_array,y_array,x_array.length).contains(new Point(x, y));
Dans cet exemple, nous créons un objet java.awt.Polygon et utilisez la méthode contains pour vérifier si vos coordonnées sont dans la forme que vous avez conçu.
j'utilise l'objet java.awt.Point pour représenter les coordonnées pour rendre le code élégant mais c'est facultatif, vous pouvez directement utiliser .contains(x, y)