在Android中查找包含在path中的点

是否有一个原因,他们决定不在Android中添加包含方法(对于path)?

我想知道我在道路上有什么意见,并希望比这里更容易:

我怎么知道封闭path是否包含给定的点?

创build一个ArrayList并将整数添加到数组中会更好吗? (我只在控制语句中检查一次)也就是说。 if(myPath.contains(x,y)

到目前为止,我的select是:

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

我只是寻找最有效的方式,我应该去做这件事

Solutions Collecting From Web of "在Android中查找包含在path中的点"

前一段时间我遇到了同样的问题,经过一番search,我发现这是最好的解决scheme。

Java有一个带有contains()方法的Polygon类,它会使事情变得非常简单。 不幸的是,Android中不支持java.awt.Polygon类。 但是,我find了一个写同类课程的人 。

我不认为你可以从Android Path类获得构成path的单个点,所以你将不得不以不同的方式存储数据。

该类使用交叉数algorithm来确定点是否位于给定列表中。

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

我只想评论@theisenp答案:代码有整数数组,如果你看看algorithm描述网页,它会警告使用整数而不是浮点数。

我复制了上面的代码,除了一些angular落的情况下,我似乎没有任何连接到自己很好的线。

通过改变一切到浮点,我摆脱了这个错误。

试过了另一个答案,但是对我的情况却给了一个错误的结果。 没有打扰find确切的原因,但做了自己的直接翻译algorithm: 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; } } 

为了完整起见,我想在这里做一些注释:

从API 19开始,path有一个交叉操作 。 您可以在testing点周围创build一个非常小的方形path,将其与path相交,并查看结果是否为空。

您可以将path转换为区域并执行一个contains()操作。 然而,区域工作在整数坐标,我认为他们使用转换(像素)的坐标,所以你必须处理。 我也怀疑转换过程是计算密集型的。

汉斯公布的边缘交叉algorithm既好又快,但是对于某些边angular情况,例如当光线直接穿过顶点,或者与水平边缘相交时,或者当舍入误差是一个问题时,您必须非常小心,它永远是。

绕组编号方法是非常简单的,但涉及很多的触发,并且计算成本很高。

Dan Sunday的这篇论文给出了一种混合algorithm,它与绕组编号一样精确,但是与光线投射algorithm一样在计算上简单。 它吹走了我多么优雅。

我的代码

这是我最近在Java中编写的一些代码,它处理由线段弧段组成的path。 (也圈出来,但这些都是完整的path,所以这是一个退化的情况。)

 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 he given path. */ public static boolean inside(float x, float y, PathElement[] path) { // Based on algorithm by Dan Sunday, but allows for arc segments too. // 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 <= Py 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 > Py 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(); }