¿Cómo puedo saber si una ruta cerrada contiene un punto dado?

Question

En Android, tengo un objeto Path que sé que define una ruta cerrada, y necesito averiguar si un punto dado está contenido dentro de la ruta. Lo que esperaba era algo a lo largo de las líneas de

path.contains (int x, int y)

pero que no parece existir.

La razón específica por la que estoy buscando esto es porque tengo una colección de formas en la pantalla definidas como rutas, y quiero averiguar en cuál hizo clic el usuario. Si hay una mejor manera de acercarse a esto, como usar diferentes elementos de la interfaz de usuario en lugar de hacerlo "por las malas", estoy abierto a sugerencias.

Estoy dispuesto a escribir un algoritmo si tengo que hacerlo, pero eso significa una investigación diferente, supongo.

Answer 1

La clase android.graphics.Path no tiene este método. La clase Canvas tiene una región de recorte que se puede establecer en una ruta, no hay forma de probarla contra un punto. Puede probar Canvas.quickReject, probando con un rectángulo de un solo punto (o un 1x1 Rect). Sin embargo, no sé si eso realmente verificaría contra el camino o el rectángulo circundante.

La clase Región claramente solo realiza un seguimiento del rectángulo que contiene.

Es posible que se planteen la elaboración de cada uno de sus regiones de mapa de bits en una capa alfa de 8 bits con cada Path lleno en su propio valor 'color' (asegúrese de que el anti-aliasing se apaga en su Paint). Esto crea una especie de máscara para cada ruta llena de un índice de la ruta que lo llena. Entonces podrías usar el valor de píxel como un índice en tu lista de rutas.

Bitmap lookup = Bitmap.createBitmap(width, height, Bitmap.Config.ALPHA_8); 
//do this so that regions outside any path have a default 
//path index of 255 
lookup.eraseColor(0xFF000000); 

Canvas canvas = new Canvas(lookup); 
Paint paint = new Paint(); 

//these are defaults, you only need them if reusing a Paint 
paint.setAntiAlias(false); 
paint.setStyle(Paint.Style.FILL); 

for(int i=0;i<paths.size();i++) 
    { 
    paint.setColor(i<<24); // use only alpha value for color 0xXX000000 
    canvas.drawPath(paths.get(i), paint); 
    } 

A continuación, busque puntos,

int pathIndex = lookup.getPixel(x, y); 
pathIndex >>>= 24; 

asegúrese de comprobar si hay 255 (sin ruta) si hay puntos sin cubrir.

Answer 2

Esto es lo que hice y parece que funciona:

RectF rectF = new RectF(); 
path.computeBounds(rectF, true); 
region = new Region(); 
region.setPath(path, new Region((int) rectF.left, (int) rectF.top, (int) rectF.right, (int) rectF.bottom)); 

Ahora se puede utilizar el método region.contains(x,y).

Point point = new Point(); 
mapView.getProjection().toPixels(geoPoint, point); 

if (region.contains(point.x, point.y)) { 
    // Within the path. 
} 

** ** Actualización sobre 6/7/2010 El método region.setPath hará que mi aplicación se bloquee (ningún mensaje de advertencia) si el rectF es demasiado grande. Aquí está mi solución:

// Get the screen rect. If this intersects with the path's rect 
// then lets display this zone. The rectF will become the 
// intersection of the two rects. This will decrease the size therefor no more crashes. 
Rect drawableRect = new Rect(); 
mapView.getDrawingRect(drawableRect); 

if (rectF.intersects(drawableRect.left, drawableRect.top, drawableRect.right, drawableRect.bottom)) { 
    // ... Display Zone. 
} 

Answer 3

de SkiaUtils WebKit tiene un C++ solución alternativa para el bug de Randy Findley:

bool SkPathContainsPoint(SkPath* originalPath, const FloatPoint& point, SkPath::FillType ft) 
{ 
    SkRegion rgn; 
    SkRegion clip; 

    SkPath::FillType originalFillType = originalPath->getFillType(); 

    const SkPath* path = originalPath; 
    SkPath scaledPath; 
    int scale = 1; 

    SkRect bounds = originalPath->getBounds(); 

    // We can immediately return false if the point is outside the bounding rect 
    if (!bounds.contains(SkFloatToScalar(point.x()), SkFloatToScalar(point.y()))) 
     return false; 

    originalPath->setFillType(ft); 

    // Skia has trouble with coordinates close to the max signed 16-bit values 
    // If we have those, we need to scale. 
    // 
    // TODO: remove this code once Skia is patched to work properly with large 
    // values 
    const SkScalar kMaxCoordinate = SkIntToScalar(1<<15); 
    SkScalar biggestCoord = std::max(std::max(std::max(bounds.fRight, bounds.fBottom), -bounds.fLeft), -bounds.fTop); 

    if (biggestCoord > kMaxCoordinate) { 
     scale = SkScalarCeil(SkScalarDiv(biggestCoord, kMaxCoordinate)); 

     SkMatrix m; 
     m.setScale(SkScalarInvert(SkIntToScalar(scale)), SkScalarInvert(SkIntToScalar(scale))); 
     originalPath->transform(m, &scaledPath); 
     path = &scaledPath; 
    } 

    int x = static_cast<int>(floorf(point.x()/scale)); 
    int y = static_cast<int>(floorf(point.y()/scale)); 
    clip.setRect(x, y, x + 1, y + 1); 

    bool contains = rgn.setPath(*path, clip); 

    originalPath->setFillType(originalFillType); 
    return contains; 
} 

Answer 4

Sé que soy un poco tarde a la fiesta, pero me gustaría resolver este problema al pensar en ello, como determinar si un punto está o no en un polígono.

http://en.wikipedia.org/wiki/Point_in_polygon

La matemática calcula más lentamente cuando se está buscando en curvas de Bezier en lugar de segmentos de línea, pero dibujando un rayo desde el punto todavía funciona.

Answer 5

Para completar, quiero hacer un par de notas aquí:

En fecha 19 API, hay un intersection operation de Caminos. Puede crear una ruta cuadrada muy pequeña alrededor de su punto de prueba, cortarla con la ruta y ver si el resultado está vacío o no.

Puede convertir Rutas a regiones y realizar una operación contains(). Sin embargo, las regiones funcionan en coordenadas enteras, y creo que usan coordenadas transformadas (píxeles), por lo que tendrás que trabajar con eso. También sospecho que el proceso de conversión es computacionalmente intensivo.

El algoritmo de cruce de bordes que Hans publicó es bueno y rápido, pero debe tener mucho cuidado para ciertos casos de esquina, como cuando el rayo pasa directamente a través de un vértice o interseca un borde horizontal o cuando redondea el error es un problema, que siempre es.

El método winding number es bastante infalible, pero implica una gran cantidad de trigonometría y es computacionalmente costoso.

This paper by Dan Sunday proporciona un algoritmo híbrido que es tan preciso como el número de cuerda pero tan simple como el algoritmo de fundición de rayos. Me impresionó lo elegante que era.

Consulte https://stackoverflow.com/a/33974251/338479 para obtener mi código que hará el cálculo de punto en ruta para una ruta que consta de segmentos de línea, arcos y círculos.