在Android中查找路径中包含的点

r55awzrz  于 2023-10-14  发布在  Android
关注(0)|答案(4)|浏览(184)

他们决定不在Android中添加contains方法(用于Path)的原因是什么?
我想知道我在路径中有哪些点,并希望它比这里看到的更容易:
How can I tell if a closed path contains a given point?
如果我创建一个ArrayList并将整数添加到数组中会更好吗?(我只在控制语句中检查一次点)即。if(myPath.contains(x,y)
到目前为止,我的选择是:

  • 使用区域
  • 使用ArrayList
  • 扩展类
  • 你的建议

我只是在寻找最有效的方法

laximzn5

laximzn51#

不久前,我遇到了同样的问题,经过一番搜索,我发现这是最好的解决方案。
Java有一个Polygon类,它有一个contains()方法,可以让事情变得非常简单。不幸的是,java.awt.Polygon类在Android中不受支持。但是,我能够找到一个写了一个等效类的人。
我不认为你可以从Android Path类中获取组成路径的各个点,所以你必须以不同的方式存储数据。
该类使用交叉数算法来确定点是否在给定的点列表中。

/**
 * 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;
    }  
}
rdrgkggo

rdrgkggo2#

我只想评论@theisenp的回答:该代码有整数数组,如果你看算法描述网页,它警告不要使用整数而不是浮点数。
我复制了你上面的代码,它似乎工作得很好,除了一些角落的情况下,当我做的线,没有连接到自己很好。
通过将所有内容都改为浮点,我摆脱了这个bug。

o2g1uqev

o2g1uqev3#

我尝试了另一个答案,但它给了我一个错误的结果。没有费心去寻找确切的原因,但我自己直接从算法翻译:http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
现在代码如下:

/**
 * 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;
    }  
}
cnjp1d6j

cnjp1d6j4#

为了完整起见,我想在这里做几点说明:
从API 19开始,路径有一个交集操作。你可以在你的测试点周围创建一个非常小的正方形路径,将它与Path相交,看看结果是否为空。
您可以将路径转换为区域并执行contains()操作。然而,区域在整数坐标下工作,我认为它们使用转换后的(像素)坐标,所以你必须使用它。我还怀疑转换过程是计算密集型的。
Hans发布的边交叉算法很好,速度也很快,但对于某些角点情况,例如光线直接穿过顶点或与水平边相交时,或者舍入误差是一个问题时,你必须非常小心。
缠绕数方法是相当愚蠢的证明,但涉及到大量的计算量和计算成本。
This paper by Dan Sunday给出了一种混合算法,它与缠绕数一样精确,但计算上与光线投射算法一样简单。它的优雅让我大吃一惊

我的代码

这是我最近用Java写的一些代码,它处理由线段和圆弧组成的路径。(也是圆,但它们本身就是完整的路径,所以这是一种退化的情况。

package org.efalk.util;

/**
 * Utility: determine if a point is inside a path.
 */
public class PathUtil {
    static final double RAD = (Math.PI/180.);
    static final double DEG = (180./Math.PI);

    protected static final int LINE = 0;
    protected static final int ARC = 1;
    protected static final int CIRCLE = 2;

    /**
     * Used to cache the contents of a path for pick testing.  For a
     * line segment, x0,y0,x1,y1 are the endpoints of the line.  For
     * a circle (ellipse, actually), x0,y0,x1,y1 are the bounding box
     * of the circle (this is how Android and X11 like to represent
     * circles).  For an arc, x0,y0,x1,y1 are the bounding box, a1 is
     * the start angle (degrees CCW from the +X direction) and a1 is
     * the sweep angle (degrees CCW).
     */
    public static class PathElement {
        public int type;
        public float x0,y0,x1,y1;   // Endpoints or bounding box
        public float a0,a1;         // Arcs and circles
    }

    /**
     * Determine if the given point is inside the given path.
     */
    public static boolean inside(float x, float y, PathElement[] path) {
        // Based on algorithm by Dan Sunday, but allows for arc segments too.         
        // https://web.archive.org/web/20130126163405/http://geomalgorithms.com/a03-_inclusion.html
        int wn = 0;
        // loop through all edges of the polygon
        // An upward crossing requires y0 <= y and y1 > y
        // A downward crossing requires y0 > y and y1 <= y
        for (PathElement pe : path) {
            switch (pe.type) {
              case LINE:
                if (pe.x0 < x && pe.x1 < x) // left
                    break;
                if (pe.y0 <= y) {           // start y <= P.y
                    if (pe.y1 > y) {        // an upward crossing
                        if (isLeft(pe, x, y) > 0) // P left of  edge
                            ++wn;                // have  a valid up intersect
                    }
                }
                else {                              // start y > P.y
                    if (pe.y1 <= y) {       // a downward crossing
                        if (isLeft(pe, x, y) < 0) // P right of  edge
                            --wn;                // have  a valid down intersect
                    }
                }
                break;
              case ARC:
                wn += arcCrossing(pe, x, y);
                break;
              case CIRCLE:
                // This should be the only element in the path, so test it
                // and get out.
                float rx = (pe.x1-pe.x0)/2;
                float ry = (pe.y1-pe.y0)/2;
                float xc = (pe.x1+pe.x0)/2;
                float yc = (pe.y1+pe.y0)/2;
                return (x-xc)*(x-xc)/rx*rx + (y-yc)*(y-yc)/ry*ry <= 1;
            }
        }
        return wn != 0;
    }

    /**
     * Return >0 if p is left of line p0-p1; <0 if to the right; 0 if
     * on the line.
     */
    private static float
    isLeft(float x0, float y0, float x1, float y1, float x, float y)
    {
        return (x1 - x0) * (y - y0) - (x - x0) * (y1 - y0);
    }

    private static float isLeft(PathElement pe, float x, float y) {
        return isLeft(pe.x0,pe.y0, pe.x1,pe.y1, x,y);
    }

    /**
     * Determine if an arc segment crosses the test ray up or down, or not
     * at all.
     * @return winding number increment:
     *      +1 upward crossing
     *       0 no crossing
     *      -1 downward crossing
     */
    private static int arcCrossing(PathElement pe, float x, float y) {
        // Look for trivial reject cases first.
        if (pe.x1 < x || pe.y1 < y || pe.y0 > y) return 0;

        // Find the intersection of the test ray with the arc. This consists
        // of finding the intersection(s) of the line with the ellipse that
        // contains the arc, then determining if the intersection(s)
        // are within the limits of the arc.
        // Since we're mostly concerned with whether or not there *is* an
        // intersection, we have several opportunities to punt.
        // An upward crossing requires y0 <= y and y1 > y
        // A downward crossing requires y0 > y and y1 <= y
        float rx = (pe.x1-pe.x0)/2;
        float ry = (pe.y1-pe.y0)/2;
        float xc = (pe.x1+pe.x0)/2;
        float yc = (pe.y1+pe.y0)/2;
        if (rx == 0 || ry == 0) return 0;
        if (rx < 0) rx = -rx;
        if (ry < 0) ry = -ry;
        // We start by transforming everything so the ellipse is the unit
        // circle; this simplifies the math.
        x -= xc;
        y -= yc;
        if (x > rx || y > ry || y < -ry) return 0;
        x /= rx;
        y /= ry;
        // Now find the points of intersection. This is simplified by the
        // fact that our line is horizontal. Also, by the time we get here,
        // we know there *is* an intersection.
        // The equation for the circle is x²+y² = 1. We have y, so solve
        // for x = ±sqrt(1 - y²)
        double x0 = 1 - y*y;
        if (x0 <= 0) return 0;
        x0 = Math.sqrt(x0);
        // We only care about intersections to the right of x, so
        // that's another opportunity to punt. For a CCW arc, The right
        // intersection is an upward crossing and the left intersection
        // is a downward crossing.  The reverse is true for a CW arc.
        if (x > x0) return 0;
        int wn = arcXing1(x0,y, pe.a0, pe.a1);
        if (x < -x0) wn -= arcXing1(-x0,y, pe.a0, pe.a1);
        return wn;
    }

    /**
     * Return the winding number of the point x,y on the unit circle
     * which passes through the arc segment defined by a0,a1.
     */
    private static int arcXing1(double x, float y, float a0, float a1) {
        double a = Math.atan2(y,x) * DEG;
        if (a < 0) a += 360;
        if (a1 > 0) {       // CCW
            if (a < a0) a += 360;
            return a0 + a1 > a ? 1 : 0;
        } else {            // CW
            if (a0 < a) a0 += 360;
            return a0 + a1 <= a ? -1 : 0;
        }
    }
}

编辑:根据请求,添加一些使用此功能的示例代码。

import PathUtil;
import PathUtil.PathElement;

/**
 * This class represents a single geographic area defined by a
 * circle or a list of line segments and arcs.
 */
public class Area {
    public float lat0, lon0, lat1, lon1;    // bounds
    Path path = null;
    PathElement[] pathList;

    /**
     * Return true if this point is inside the area bounds. This is
     * used to confirm touch events and may be computationally expensive.
     */
    public boolean pointInBounds(float lat, float lon) {
        if (lat < lat0 || lat > lat1 || lon < lon0 || lon > lon1)
            return false;
        return PathUtil.inside(lon, lat, pathList);
    }

    static void loadBounds() {
        int n = number_of_elements_in_input;
        path = new Path();
        pathList = new PathElement[n];
        for (Element element : elements_in_input) {
            PathElement pe = new PathElement();
            pathList[i] = pe;
            pe.type = element.type;
            switch (element.type) {
              case LINE:        // Line segment
                pe.x0 = element.x0;
                pe.y0 = element.y0;
                pe.x1 = element.x1;
                pe.y1 = element.y1;
                // Add to path, not shown here
                break;
              case ARC: // Arc segment
                pe.x0 = element.xmin;     // Bounds of arc ellipse
                pe.y0 = element.ymin;
                pe.x1 = element.xmax;
                pe.y1 = element.ymax;
                pe.a0 = a0; pe.a1 = a1;
                break;
              case CIRCLE: // Circle; hopefully the only entry here
                pe.x0 = element.xmin;    // Bounds of ellipse
                pe.y0 = element.ymin;
                pe.x1 = element.xmax;
                pe.y1 = element.ymax;
                // Add to path, not shown here
                break;
            }
        }
        path.close();
    }

相关问题