Trouver des points contenus dans un chemin d'Android

Je suis venu contre ce même problème il y a un peu de temps, et après une recherche, j'ai trouvé que ceci comme la meilleure solution.

Java a un Polygon code> classe avec un contient () code> méthode qui rendrait les choses vraiment simples. Malheureusement, la classe java.awt.polygon code> n'est pas prise en charge dans Android. Cependant, j'ai pu trouver quelqu'un qui a écrit un classe équivalente . p>

Je ne pense pas que vous puissiez obtenir les points individuels qui constituent le chemin de la trajectoire Android PATH CODE> , vous devrez donc stocker les données de manière différente. p>

La classe utilise un algorithme de numéro de passage pour déterminer si le point est à l'intérieur de la liste de points donnée. P>

/**
 * Minimum Polygon class for Android.
 */
public class Polygon
{
    // Polygon coodinates.
    private int[] polyY, polyX;

    // Number of sides in the polygon.
    private int polySides;

    /**
     * Default constructor.
     * @param px Polygon y coods.
     * @param py Polygon x coods.
     * @param ps Polygon sides count.
     */
    public Polygon( int[] px, int[] py, int ps )
    {
        polyX = px;
        polyY = py;
        polySides = ps;
    }

    /**
     * Checks if the Polygon contains a point.
     * @see "http://alienryderflex.com/polygon/"
     * @param x Point horizontal pos.
     * @param y Point vertical pos.
     * @return Point is in Poly flag.
     */
    public boolean contains( int x, int y )
    {
        boolean oddTransitions = false;
        for( int i = 0, j = polySides -1; i < polySides; j = i++ )
        {
            if( ( polyY[ i ] < y && polyY[ j ] >= y ) || ( polyY[ j ] < y && polyY[ i ] >= y ) )
            {
                if( polyX[ i ] + ( y - polyY[ i ] ) / ( polyY[ j ] - polyY[ i ] ) * ( polyX[ j ] - polyX[ i ] ) < x )
                {
                    oddTransitions = !oddTransitions;          
                }
            }
        }
        return oddTransitions;
    }  
}

essayé l'autre réponse, mais cela a donné un résultat erroné pour mon cas. Je n'ai pas pris la peine de trouver la cause exacte, mais a fait ma propre traduction directe de l'algorithme sur: http://www.ecse.ripi.edu/homepages/wrf/research/short_notes/pnpoly.html

Le code lit: P>

/**
 * Minimum Polygon class for Android.
 */
public class Polygon
{
    // Polygon coodinates.
    private int[] polyY, polyX;

    // Number of sides in the polygon.
    private int polySides;

    /**
     * Default constructor.
     * @param px Polygon y coods.
     * @param py Polygon x coods.
     * @param ps Polygon sides count.
     */
    public Polygon( int[] px, int[] py, int ps )
    {
        polyX = px;
        polyY = py;
        polySides = ps;
    }

    /**
     * Checks if the Polygon contains a point.
     * @see "http://alienryderflex.com/polygon/"
     * @param x Point horizontal pos.
     * @param y Point vertical pos.
     * @return Point is in Poly flag.
     */
    public boolean contains( int x, int y )
    {
        boolean c = false;
        int i, j = 0;
        for (i = 0, j = polySides - 1; i < polySides; j = i++) {
            if (((polyY[i] > y) != (polyY[j] > y))
                && (x < (polyX[j] - polyX[i]) * (y - polyY[i]) / (polyY[j] - polyY[i]) + polyX[i]))
            c = !c;
        }
        return c;
    }  
}

Je voudrais juste commenter sur @theisenp Réponse: le code comporte des tableaux entier et si vous regardez sur la page Web de la description d'algorithme, il met en garde contre l'utilisation d'entiers au lieu d'un point flottant.

J'ai copié votre code ci-dessus et cela semblait fonctionner correctement, à l'exception des cas d'angle lorsque je faisais des lignes qui ne se sont pas bien connues à elles-mêmes.

En changeant tout sur Point flottant, je me suis débarrassé de ce bogue.

En complétude, je veux faire quelques notes ici:

à partir de API 19, il y a un Opération d'intersection pour les chemins. Vous pouvez créer un très petit chemin carré autour de votre point de test, l'intersecter avec le chemin et voir si le résultat est vide ou non.

Vous pouvez convertir des chemins vers des régions et faire un Contient () Opération. Cependant, les régions fonctionnent dans des coordonnées entière et je pense qu'ils utilisent des coordonnées transformées (pixels), vous devrez donc travailler avec cela. Je soupçonne également que le processus de conversion est informellement intensif de calcul.

L'algorithme de croisement de bord que Hans posté est bon et rapide, mais vous devez faire très attention à certains cas de coin comme lorsque le rayon passe directement à travers Un sommet ou coupe un bord horizontal, ou lorsque l'erreur arrondi est un problème, ce qu'elle est toujours.

le Numéro d'enroulement est une preuve très imbuleuse, mais implique beaucoup de trigle et est calculé en calcul.

Ce document par Dan Dimanche donne un algorithme hybride aussi précis que le numéro d'enroulement, mais aussi simple que l'algorithme de coulée de rayons. Ça m'a explosé à quel point c'était élégant.

Mon code

Ceci est un code que j'ai écrit récemment en Java, qui gère un chemin à partir de deux segments de ligne et arcs. (Également cercles, mais ce sont des chemins complets seuls, il est donc en quelque sorte un cas dégénéré.) xxx

---

modifier: par demande, ajoutant un exemple de code utilise ceci. xxx