Point dans le Polygone de l'Algorithme

J'ai vu le dessous de fonctionnement de l'algorithme utilisé pour vérifier si un point est dans un polygone donné à partir de ce lien:

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy)
{
  int i, j, c = 0;
  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;
}

J'ai essayé de cet algorithme et ça marche, tout simplement parfait. Mais, malheureusement, je ne comprends pas bien après avoir passé un certain temps à essayer pour se faire une idée de lui.

Donc si quelqu'un est en mesure de comprendre cet algorithme, pourriez-vous m'expliquer un peu.

Merci.

La réponse vous lien contient un lien vers sa source, et la source a une longue explication de l'algorithme: ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html Avez-vous lu cela?
J'ai trouvé erich.realtimerendering.com/ptinpoly pour être une excellente ressource pour la compréhension de "point dans le polygone" les stratégies.

InformationsquelleAutor Allan Jiang | 2012-07-30

algorithm c

47

L'algorithme est ray-casting de la droite. Chaque itération de la boucle, le point de test est vérifié à l'encontre de l'un des bords du polygone. La première ligne de la si-test réussit si le point d'y coord est dans le bord du champ. La deuxième ligne vérifie si le point de test est à la gauche de la ligne (je pense - je n'ai pas tout morceau de papier à la main pour vérifier). Si c'est vrai que la ligne dessinée rightwards à partir du test de point de croix de pointe.

À plusieurs reprises par l'inversion de la valeur de c, l'algorithme compte combien de fois la droite ligne traverse le polygone. Si elle traverse un nombre impair de fois, alors le point est à l'intérieur; si un même numéro, le point est à l'extérieur.

J'aurais des préoccupations avec a) l'exactitude de l'arithmétique à virgule flottante, et b) les effets de l'existence d'une arête horizontale, ou d'un point d'essai avec le même y-coord comme un sommet, si.
- Serait de l'ordre des sommets de la matière pour ce test?
- oui; le code ci-dessus, le polygone est formée par la jonction de sommet 0 au sommet 1 au sommet 2... au sommet de 0.
- Désolé - je veux dire serait la dissolution de la commande de la matière?
- J'ai peur de ne pas suivre; qu'entendez-vous par "l'enroulement de commande"?
- Si le polygone verts sont ordonnés dans le sens horaire ou dans le sens anti horaire v0 -> v1 -> v3 et v3 -> v1 -> v0?
- Ah, je vois. Il... ne devriez pas le faire. Je n'ai pas vérifié l'algorithme en profondeur pour s'en assurer, mais chaque étape ne se soucie d'un bord, à quel point dans le sens horaire/anti-horaire n'a pas de sens.
InformationsquelleAutor Chowlett
19

Chowlett est correct dans tous les cas, la forme, et la forme.
L'algorithme suppose que si ton point est sur la ligne du polygone, alors que c'est à l'extérieur - pour certains cas, c'est faux. Changer les deux "> "opérateurs" >=', et un changement de '<' de '<=' fixera.
```
bool PointInPolygon(Point point, Polygon polygon) {
  vector<Point> points = polygon.getPoints();
  int i, j, nvert = points.size();
  bool c = false;

  for(i = 0, j = nvert - 1; i < nvert; j = i++) {
    if( ( (points[i].y >= point.y ) != (points[j].y >= point.y) ) &&
        (point.x <= (points[j].x - points[i].x) * (point.y - points[i].y) / (points[j].y - points[i].y) + points[i].x)
      )
      c = !c;
  }

  return c;
}
```
- Est-il un moyen plus efficace de faire le Point au Polygone? MySQL extension spatiale prend environ 50ms pour interroger une table de 100 polygones.. cette fonction en PHP qui prend environ 100ms.
- MySQL utilise probablement natif (compilé) du code, alors que le PHP est interprété, et n'est pas connu pour sa vitesse...
- En fait (sans qu'il recherche beaucoup), je dirais qu'une simple optimisation est d'abord la vérification de la boîte englobante (si il est hors de la boîte englobante pas besoin de faire le chèque, c'est plus raffiné).
- merci pour la correction. Il n'y a qu'une petite accolade de problème dans la condition si, (points[i].y) >= point.y devrait être (points[i].y >= point.y)
- merci! Fixe.
- Vous répondez est source de confusion. Il y a seulement un '<' opérateur dans le code (en dehors de la boucle for). Vous avez également modifié les deux "> "opérateurs" >=' ainsi que l ' unique '<' de '<='. Je suis en train d'écrire des tests unitaires pour vérifier ce pour les points sur la ligne, et le test avec le point(100,100) et polygone 100,100 -> 200,100 -> 200,200 -> 100,200 échoue.
- Cette réponse n'est pas correcte, malgré le droit de vote. En ayant point.x <= ... signifie que vous considérez un point sur le bord, comme ayant un rayon qui traverse ce bord vers la droite. Cela permettra de compter les points situés sur la droite bords en "in" et des points situés sur les bords de la gauche "out". L'évidence de correction serait explicitement test pour l'égalité et la sortie de la boucle.
- l'ordre des points dans les points de vecteur de la matière à l'issue de ce test?
- Maintenant, si vous êtes coïncide avec un sommet que vous compter deux fois le même sommet et sont à l'extérieur, tandis que dans le polygone. Et la fixation de la souvent bousiller les cas de test où, un interne vertex descend et touche la ligne qui coïncide avec ce que vous êtes en contrôle. Sans être sur le bord, juste dans la façon de raycasting, mais pas de vous mettre à l'extérieur du polygone. V_____
- est très correct. Il est préférable de vérifier pour voir si le point se trouve sur le bord du polygone dans la boucle et simplement retourner la valeur true dans ce cas.
- Comme @Equateur dit, ce n'est pas une réponse correcte. L'original pnpoly algorithme, et le point sur une arête cas, est décrite ici par son auteur. TL;DR, si le point est sur le bord entre deux polygones, la pnpoly algorithme constante classer le point à l'intérieur d'un polygone, et en dehors de l'autre polygone.
InformationsquelleAutor Josh

Cela peut être aussi détaillée qu'il pourrait faire pour expliquer le ray-tracing de l'algorithme dans le code réel. Il pourrait ne pas être optimisé mais qui doit toujours venir après une compréhension complète du système.

    //method to check if a Coordinate is located in a polygon
public boolean checkIsInPolygon(ArrayList<Coordinate> poly){
//this method uses the ray tracing algorithm to determine if the point is in the polygon
int nPoints=poly.size();
int j=-999;
int i=-999;
boolean locatedInPolygon=false;
for(i=0;i<(nPoints);i++){
//repeat loop for all sets of points
if(i==(nPoints-1)){
//if i is the last vertex, let j be the first vertex
j= 0;
}else{
//for all-else, let j=(i+1)th vertex
j=i+1;
}
float vertY_i= (float)poly.get(i).getY();
float vertX_i= (float)poly.get(i).getX();
float vertY_j= (float)poly.get(j).getY();
float vertX_j= (float)poly.get(j).getX();
float testX  = (float)this.getX();
float testY  = (float)this.getY();
//following statement checks if testPoint.Y is below Y-coord of i-th vertex
boolean belowLowY=vertY_i>testY;
//following statement checks if testPoint.Y is below Y-coord of i+1-th vertex
boolean belowHighY=vertY_j>testY;
/* following statement is true if testPoint.Y satisfies either (only one is possible) 
-->(i).Y < testPoint.Y < (i+1).Y        OR  
-->(i).Y > testPoint.Y > (i+1).Y
(Note)
Both of the conditions indicate that a point is located within the edges of the Y-th coordinate
of the (i)-th and the (i+1)- th vertices of the polygon. If neither of the above
conditions is satisfied, then it is assured that a semi-infinite horizontal line draw 
to the right from the testpoint will NOT cross the line that connects vertices i and i+1 
of the polygon
*/
boolean withinYsEdges= belowLowY != belowHighY;
if( withinYsEdges){
//this is the slope of the line that connects vertices i and i+1 of the polygon
float slopeOfLine   = ( vertX_j-vertX_i )/ (vertY_j-vertY_i) ;
//this looks up the x-coord of a point lying on the above line, given its y-coord
float pointOnLine   = ( slopeOfLine* (testY - vertY_i) )+vertX_i;
//checks to see if x-coord of testPoint is smaller than the point on the line with the same y-coord
boolean isLeftToLine= testX < pointOnLine;
if(isLeftToLine){
//this statement changes true to false (and vice-versa)
locatedInPolygon= !locatedInPolygon;
}//end if (isLeftToLine)
}//end if (withinYsEdges
}
return locatedInPolygon;
}

Juste un mot à propos de l'optimisation: Il n'est pas vrai que le plus court (et/ou le tersest) du code est la manière la plus rapide de mise en œuvre. C'est un processus plus rapide pour lire et stocker un élément d'un tableau et de l'utiliser (peut-être) de nombreuses fois dans l'exécution du bloc de code que pour accéder au tableau à chaque fois que cela est nécessaire. Ceci est particulièrement important si le tableau est très grand. À mon avis, par le stockage de chaque terme d'un tableau dans une variable nommée, il est également plus facile d'évaluer son but et sont donc beaucoup plus lisible le code. Juste mes deux cents...

InformationsquelleAutor apil.tamang

L'algorithme est dépouillé de la plupart des éléments nécessaires. Après qu'il a été développé et testé tous les trucs inutiles a été supprimé. Comme résultat, vous pouvez comprend pas facilement, mais il fait le travail et aussi dans de très bonnes performances.

J'ai pris la liberté de traduire à ActionScript-3:

//not optimized yet (nvert could be left out)
public static function pnpoly(nvert: int, vertx: Array, verty: Array, x: Number, y: Number): Boolean
{
var i: int, j: int;
var c: Boolean = false;
for (i = 0, j = nvert - 1; i < nvert; j = i++)
{
if (((verty[i] > y) != (verty[j] > y)) && (x < (vertx[j] - vertx[i]) * (y - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
c = !c;
}
return c;
}

InformationsquelleAutor Bitterblue

3

Cet algorithme fonctionne dans n'importe quel polygone fermé tant que le du polygone à côtés ne traversent pas. Triangle, pentagone, carré, même un très sinueuse par morceaux-linéaire de la bande de caoutchouc qui n'est pas de la croix lui-même.

1) Définir votre polygone en tant que dirigé le groupe de vecteurs. Par c'est à dire que chaque côté du polygone est décrit par un vecteur qui va du sommet à un sommet d'un+1. Les vecteurs sont donc réalisé de sorte que la tête de l'un touche la queue de l'autre jusqu'à la dernière vecteur touche la queue de la première.

2) Sélectionnez le point de test à l'intérieur ou à l'extérieur du polygone.

3) Pour chaque vecteur Vn le long du périmètre du polygone trouver le vecteur Dn qui commence sur le point d'essai et se termine à la queue de Vn. Calculer le vecteur Cn défini comme DnXVn/DN*VN (X) indique la croix du produit; * indique un produit scalaire). Appel de l'ampleur de la Cn par le nom de Mn.

4) Ajouter tous les Mn et appelons cette quantité K.

5) Si K est égal à zéro, le point est à l'extérieur du polygone.

6) Si K n'est pas zéro, le point est à l'intérieur du polygone.

Théoriquement, un point qui se trouve SUR le bord du polygone va produire un résultat indéfini.

Géométriques sens de K est le total de l'angle que la puce est assis sur notre point de test "vu" la fourmi de marche au bord du polygone à pied vers la gauche, moins l'angle se dirigea vers la droite. Dans un circuit fermé, la fourmi se termine là où elle a commencé.
À l'extérieur du polygone, indépendamment de l'emplacement, la réponse est zéro.

À l'intérieur du polygone, indépendamment de l'emplacement, la réponse est "un temps autour du point".

InformationsquelleAutor Mario

J'ai changé le code d'origine pour le rendre un peu plus lisible (également cette utilise Eigen). L'algorithme est identique.

//This uses the ray-casting algorithm to decide whether the point is inside
//the given polygon. See https://en.wikipedia.org/wiki/Point_in_polygon#Ray_casting_algorithm
bool pnpoly(const Eigen::MatrixX2d &poly, float x, float y)
{
//If we never cross any lines we're inside.
bool inside = false;
//Loop through all the edges.
for (int i = 0; i < poly.rows(); ++i)
{
//i is the index of the first vertex, j is the next one.
//The original code uses a too-clever trick for this.
int j = (i + 1) % poly.rows();
//The vertices of the edge we are checking.
double xp0 = poly(i, 0);
double yp0 = poly(i, 1);
double xp1 = poly(j, 0);
double yp1 = poly(j, 1);
//Check whether the edge intersects a line from (-inf,y) to (x,y).
//First check if the line crosses the horizontal line at y in either direction.
if ((yp0 <= y) && (yp1 > y) || (yp1 <= y) && (yp0 > y))
{
//If so, get the point where it crosses that line. This is a simple solution
//to a linear equation. Note that we can't get a division by zero here -
//if yp1 == yp0 then the above if be false.
double cross = (xp1 - xp0) * (y - yp0) / (yp1 - yp0) + xp0;
//Finally check if it crosses to the left of our test point. You could equally
//do right and it should give the same result.
if (cross < x)
inside = !inside;
}
}
return inside;
}

vous semblez être le seul à mentionner la division par zéro cas 😉

InformationsquelleAutor Timmmm

2

Cette méthode de vérifier si le rayon à partir du point (testx, hargneuse) à O (0,0) couper les côtés du polygone ou pas .

Il est bien connu conclusion ici: si un rayon de 1 point et coupez les côtés d'un polygone pour une drôle de temps, ce point appartient au polygone, sinon, ce point sera à l'extérieur du polygone.

InformationsquelleAutor Thinhbk
1

Je pense que l'idée de base est de calculer les vecteurs à partir de ce point, un à chaque arête du polygone. Si le vecteur traverse une arête, alors le point est à l'intérieur du polygone. Par polygones concaves si elle traverse un nombre impair d'arêtes, il est aussi bien à l'intérieur (avertissement: bien que vous ne savez pas si il fonctionne pour tous les polygones concaves).

InformationsquelleAutor Anders
1

Étendre sur @chowlette de réponse où la deuxième ligne vérifie si le point est à gauche de la ligne,
Pas de dérivation est donné, mais c'est ce que j'ai:
D'abord il permet d'imaginer de base 2 cas:
- le point est à gauche de la ligne . / ou
- le point est à droite de la ligne /.
Si notre point de tirer un rayon horizontalement, où serait-il grève le segment de ligne. Est notre point vers la gauche ou la droite? À l'intérieur ou à l'extérieur? Nous savons que sa coordonnée y parce que c'est par définition le même que le point. Quelle serait la coordonnée x de l'être?

Prendre votre ligne traditionnelle formule y = mx + b. m est la hausse au cours de l'exécution. Ici, au lieu de cela, nous essayons de trouver le coordonnée x du point sur ce segment de ligne qui a la même hauteur (y) en tant que notre point.

Nous avons donc à résoudre pour x: x = (y - b)/m. m est montée sur exécuter, de sorte que cela devient de courir sur la hausse ou la (yj - yi)/(xj - xi) devient (xj - xi)/(yj - yi). b est le décalage de l'origine. Si nous supposons yi comme la base de notre système de coordonnées, b devient yi. De notre point de testy est notre entrée, en soustrayant yi transforme la totalité de la formule dans un décalage de yi.

Nous avons maintenant (xj - xi)/(yj - yi) ou 1/m temps y ou (testy - yi): (xj - xi)(testy - yi)/(yj - yi) mais testx n'est pas fondée à yi nous avons donc le rajouter dans le but de comparer les deux ( ou zéro testx ainsi )

InformationsquelleAutor derduher

Voici une implémentation php de ce:

<?php
class Point2D {
public $x;
public $y;
function __construct($x, $y) {
$this->x = $x;
$this->y = $y;
}
function x() {
return $this->x;
}
function y() {
return $this->y;
}
}
class Point {
protected $vertices;
function __construct($vertices) {
$this->vertices = $vertices;
}
//Determines if the specified point is within the polygon. 
function pointInPolygon($point) {
/* @var $point Point2D */
$poly_vertices = $this->vertices;
$num_of_vertices = count($poly_vertices);
$edge_error = 1.192092896e-07;
$r = false;
for ($i = 0, $j = $num_of_vertices - 1; $i < $num_of_vertices; $j = $i++) {
/* @var $current_vertex_i Point2D */
/* @var $current_vertex_j Point2D */
$current_vertex_i = $poly_vertices[$i];
$current_vertex_j = $poly_vertices[$j];
if (abs($current_vertex_i->y - $current_vertex_j->y) <= $edge_error && abs($current_vertex_j->y - $point->y) <= $edge_error && ($current_vertex_i->x >= $point->x) != ($current_vertex_j->x >= $point->x)) {
return true;
}
if ($current_vertex_i->y > $point->y != $current_vertex_j->y > $point->y) {
$c = ($current_vertex_j->x - $current_vertex_i->x) * ($point->y - $current_vertex_i->y) / ($current_vertex_j->y - $current_vertex_i->y) + $current_vertex_i->x;
if (abs($point->x - $c) <= $edge_error) {
return true;
}
if ($point->x < $c) {
$r = !$r;
}
}
}
return $r;
}

Test:

        <?php
$vertices = array();
array_push($vertices, new Point2D(120, 40));
array_push($vertices, new Point2D(260, 40));
array_push($vertices, new Point2D(45, 170));
array_push($vertices, new Point2D(335, 170));
array_push($vertices, new Point2D(120, 300));
array_push($vertices, new Point2D(260, 300));
$Point = new Point($vertices);
$point_to_find = new Point2D(190, 170);
$isPointInPolygon = $Point->pointInPolygon($point_to_find);
echo $isPointInPolygon;
var_dump($isPointInPolygon);

InformationsquelleAutor Daniel

0

C'est l'algorithme que j'utilise, mais j'ai ajouté un peu de prétraitement, la ruse de l'accélérer. Mes polygones ont ~1000 bords et ils ne changent pas, mais j'ai besoin de regarder pour savoir si le curseur est à l'intérieur de l'un sur chaque déplacement de la souris.

En gros, j'ai divisé la hauteur du rectangle de délimitation de l'égalité de longueur des intervalles et pour chacun de ces intervalles que je compile la liste des bords qui se trouvent dans/intersection avec elle.

Quand j'ai besoin de regarder pour un point, je peux calculer en O(1) du temps - intervalle, il est, puis je l'ai seulement besoin de tester ces bords qui sont dans l'intervalle de la liste.

J'ai utilisé 256 intervalles et cela a réduit le nombre d'arêtes j'ai besoin de tester 2 à 10 au lieu de ~1000.

InformationsquelleAutor Sly1024

J'ai modifié le code pour vérifier si le point est dans un polygone, y compris le point est sur un bord.

bool point_in_polygon_check_edge(const vec<double, 2>& v, vec<double, 2> polygon[], int point_count, double edge_error = 1.192092896e-07f)
{
const static int x = 0;
const static int y = 1;
int i, j;
bool r = false;
for (i = 0, j = point_count - 1; i < point_count; j = i++)
{
const vec<double, 2>& pi = polygon[i);
const vec<double, 2>& pj = polygon[j];
if (fabs(pi[y] - pj[y]) <= edge_error && fabs(pj[y] - v[y]) <= edge_error && (pi[x] >= v[x]) != (pj[x] >= v[x]))
{
return true;
}
if ((pi[y] > v[y]) != (pj[y] > v[y]))
{
double c = (pj[x] - pi[x]) * (v[y] - pi[y]) / (pj[y] - pi[y]) + pi[x];
if (fabs(v[x] - c) <= edge_error)
{
return true;
}
if (v[x] < c)
{
r = !r;
}
}
}
return r;
}

Veuillez essayer d'expliquer à vos changements de code
Les modifications sont simples, Si le point est sur le bord, Vérifier que le point est dans le polygone. Si pi[y] == pj[y] == v[y] et v[x] est dans l'entre-pi[x] et pj[x], le point est sur le bord de la ligne horizontale du polygone. si c == v[x] et v[y] est dans l'entre-pi[y] et pj[y], le point est sur le bord de la ligne verticale du polygone.
votre algorithme est bizarre

InformationsquelleAutor rawdev

Vous devez vous connecter pour publier un commentaire.