Vérifier si une longitude/latitude coordonner réside à l'intérieur d'un polygone complexe dans un dispositif intégré?

J'ai besoin de l'utilisateur d'être en mesure de dessiner un polygone complexe, sur une carte, et ensuite l'application de vérifier si une longitude/latitude réside à l'intérieur de ce polygone.

J'ai seulement été en mesure de trouver des algorithmes qui ont été à l'aide d'un simple x/y du système de coordonnées cartésiennes, qui n'a pas de compenser la courbure de la terre.

L'utilisateur dessine le polygone sur un PC, où les points sont transférés à la radio pour un périphérique intégré, qui doit ensuite vérifier si le polygone se trouve dans sa position actuelle (prise de GPS).

Que ce soit pour un intégré à l'appareil, je ne suis pas en mesure d'utiliser d'immenses bibliothèques, plutôt j'ai besoin de l'algorithme pour effectuer le contrôle de moi-même ou une très petite bibliothèque. Mais il me semble être incapable de trouver un tel algorithme.

Ce genre de distances cherchez-vous à? Je fais ce genre de travail beaucoup et si vous parlez des relativement petits polygones comme le disent < 1000 mètres celles des algorithmes simples fonctionnent bien par rapport à la précision d'un GPS classique. Courbure de la terre n'ont pas beaucoup d'effet sur les petites distances.
Notez que si vous travaillez avec un SIG, vous pouvez comme cela, AFIN sœur-site: gis.stackexchange.com
Je suis à la recherche d'utiliser cette fois sur une très large échelle (plusieurs centaines de kilomètres), mais nécessitent encore de très-près de précision, il sera également utilisé dans sectorielle des zones qui sont < 1 km
Assez juste, mais rappelez-vous, à moins que les segments sont un long chemin à part, il ne fera pas une différence. Par exemple, une 200KM d'autoroute avec une série de segments de quelques KILOMÈTRES en dehors de ne pas faire beaucoup de différence. C'est seulement si vous dites avoir un avantage sur un polygone de 100 km de long qu'il va vraiment faire une différence, ce qui est assez rare dans mon expérience. La plupart de la vie réelle des choses comme, disons, une ville de la frontière ne sont pas que de droite, dans la pratique, il est donc utile de réfléchir probablement des erreurs et si vous en avez vraiment besoin. À vitesse d'autoroute, vous aurez probablement aussi besoin d'un peu dead reckoning trop si vous avez vraiment besoin de cette précision.

OriginalL'auteur ChewToy | 2012-12-19

  1. 16

    Voici une application que j'ai écrit en C# pour un Polygone de la classe qui contient une liste de sommets. Il ne tient pas compte de la courbure de la Terre. Plutôt, vous pré-traiter le polygone en segments plus petits avant l'exécution de cette.

    Les performances de cet algorithme est de très bonne qualité. Même pour les polygones avec des milliers de bords de il termine dans environ un ou deux millisecondes sur mon bureau.

    Le code a été optimisé un peu et n'est donc pas lisible comme pseudo-code.

    public bool Contains(GeoLocation location)
{
if (!Bounds.Contains(location))
return false;
var lastPoint = _vertices[_vertices.Length - 1];
var isInside = false;
var x = location.Longitude;
foreach (var point in _vertices)
{
var x1 = lastPoint.Longitude;
var x2 = point.Longitude;
var dx = x2 - x1;
if (Math.Abs(dx) > 180.0)
{
//we have, most likely, just jumped the dateline (could do further validation to this effect if needed).  normalise the numbers.
if (x > 0)
{
while (x1 < 0)
x1 += 360;
while (x2 < 0)
x2 += 360;
}
else
{
while (x1 > 0)
x1 -= 360;
while (x2 > 0)
x2 -= 360;
}
dx = x2 - x1;
}
if ((x1 <= x && x2 > x) || (x1 >= x && x2 < x))
{
var grad = (point.Latitude - lastPoint.Latitude) / dx;
var intersectAtLat = lastPoint.Latitude + ((x - x1) * grad);
if (intersectAtLat > location.Latitude)
isInside = !isInside;
}
lastPoint = point;
}
return isInside;
}

    L'idée de base est de trouver toutes les arêtes du polygone qui s'étendent sur le " x " en position de le point vous êtes à l'essai contre. Alors vous le trouvez comment beaucoup d'entre eux se coupent la ligne verticale qui s'étend au-dessus de votre point de vue. Si un même numéro de croix au-dessus du point, alors vous êtes à l'extérieur du polygone. Si un nombre impair de la croix au-dessus, alors vous êtes à l'intérieur.

    Merci pour votre réponse! Ce genre de précision, avez-vous été en mesure de réaliser à l'aide de cet algorithme? Vu qu'il ne compense pas la courbure de la terre, il ne fait que travailler avec des semi-petites distances ou que ça va marcher décemment, même avec plus de polygones (disons 50 km)?
    la précision varie avec la distance. Si vous avez besoin de plus de précision qu'il vous donne, les trouver le point milieu des deux sommets adjacents sur la sphère, et insérez un nouveau sommet. Répéter cette opération jusqu'à ce que le polygone est à l'intérieur de votre tolérances requises. Sinon, vous pouvez modifier l'algorithme pour effectuer l'intersection de test d'une manière qui tient compte de la courbure de la terre.
    Merci beaucoup pour l'algorithme, quel est l'état de Limites.Contient(emplacement)?
    c'est une option d'optimisation. Si vous avez un cadre de sélection rectangulaire qui contient la mesure de tous les points du polygone, alors qu'il pourrait être plus rapide de faire un test rapide sur la boîte avant de la marche de tous les sommets. Si le point n'est pas dans les limites alors il ne peut pas être dans le polygone.
    Salut a Attiré, cet algorithme est vous dire si un hasard sommet est à l'intérieur d'un polygone. Je suis en train d'exclure le cas lorsque le hasard le sommet est en fait un sommet formant le polygone en supprimant toute >= et <= la comparaison et de la transformer en > et < tous les conseils sur ce point?

    OriginalL'auteur Drew Noakes

  2. 5

    De bonnes explications et simple du code C qui vous permet de convertir vos besoins

    http://alienryderflex.com/polygon/

    Combiner le polygone vérifier avec un RTree rapide de l'abattage de l'arbre de recherche si vous avez beaucoup de non chevauchement des polygones.

    OriginalL'auteur Niclas Lindgren