Làm cách nào để biết liệu đường dẫn đã đóng có chứa một điểm nhất định không?

Question

Trong Android, tôi có một đối tượng Đường dẫn mà tôi tình cờ biết định nghĩa một đường dẫn khép kín và tôi cần tìm ra liệu một điểm đã cho có được chứa trong đường dẫn hay không. Những gì tôi đã hy vọng cho một cái gì đó dọc theo dòng của

path.contains (int x, int y)

nhưng điều đó dường như không tồn tại.

Lý do cụ thể tôi đang tìm kiếm điều này là do tôi có một bộ sưu tập hình dạng trên màn hình được định nghĩa là đường dẫn và tôi muốn tìm ra người dùng đã nhấp vào hình nào. Nếu có một cách tốt hơn để tiếp cận điều này như sử dụng các yếu tố giao diện người dùng khác nhau thay vì tự làm "theo cách khó khăn", tôi sẽ mở ra các đề xuất.

Tôi tự mở để viết một thuật toán nếu tôi phải làm, nhưng điều đó có nghĩa là nghiên cứu khác nhau mà tôi đoán.

Answer 1

Lớp android.graphics.Path không có phương thức như vậy. Lớp Canvas có một vùng cắt có thể được đặt thành một đường dẫn, không có cách nào để kiểm tra nó với một điểm. Bạn có thể thử Canvas.quickReject, thử nghiệm với một hình chữ nhật điểm đơn (hoặc 1x1 Rect). Tôi không biết nếu điều đó thực sự sẽ kiểm tra đối với con đường hoặc chỉ là hình chữ nhật kèm theo, mặc dù.

Lớp Vùng chỉ rõ ràng theo dõi hình chữ nhật chứa.

Bạn có thể xem xét vẽ từng khu vực của mình vào một lớp alpha 8 bit Bitmap với mỗi Path được điền vào giá trị 'màu' riêng của nó (đảm bảo chống răng cưa được tắt trong số Paint). Điều này tạo ra một loại mặt nạ cho mỗi đường dẫn được lấp đầy với một chỉ mục cho đường dẫn lấp đầy nó. Sau đó, bạn chỉ có thể sử dụng giá trị pixel làm chỉ mục vào danh sách đường dẫn của mình.

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); 
    } 

Sau đó nhìn lên điểm,

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

Hãy chắc chắn để kiểm tra 255 (không có đường dẫn) nếu có những điểm không hàn.

Answer 2

Đây là những gì tôi đã làm và nó dường như làm việc:

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)); 

Bây giờ bạn có thể sử dụng phương pháp region.contains(x,y).

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

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

** Cập nhật vào 6/7/2010 ** Phương pháp region.setPath sẽ gây ra ứng dụng của tôi sụp đổ (không có thông báo cảnh báo) nếu rectF là quá lớn. Đây là giải pháp của tôi:

// 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

WebKit của SkiaUtils có C++ công việc xung quanh cho lỗi Randy Findley của:

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

Tôi biết tôi là một chút muộn để đảng, nhưng tôi sẽ giải quyết vấn đề này bằng cách suy nghĩ về nó như xác định một điểm có nằm trong đa giác hay không.

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

Toán học tính toán chậm hơn khi bạn đang nhìn vào Bezier splines thay vì đoạn thẳng, nhưng vẽ một tia từ điểm vẫn hoạt động.

Answer 5

Để hoàn chỉnh, tôi muốn thực hiện một vài lưu ý ở đây:

Tính đến API 19, có một intersection operation cho Paths. Bạn có thể tạo một đường hình vuông rất nhỏ xung quanh điểm kiểm tra của bạn, cắt nó với Đường dẫn và xem kết quả có trống hay không.

Bạn có thể chuyển đổi Đường dẫn thành Khu vực và thực hiện thao tác contains(). Tuy nhiên Khu vực làm việc trong các tọa độ nguyên, và tôi nghĩ rằng họ sử dụng các tọa độ chuyển đổi (pixel), vì vậy bạn sẽ phải làm việc với điều đó. Tôi cũng nghi ngờ rằng quá trình chuyển đổi là tính toán chuyên sâu.

Thuật toán vượt qua mà Hans đăng là tốt và nhanh, nhưng bạn phải rất cẩn thận đối với một số trường hợp góc như khi tia truyền trực tiếp qua đỉnh hoặc cắt cạnh ngang hoặc khi vòng tròn lỗi là một vấn đề, mà nó luôn luôn là.

Phương pháp winding number là bằng chứng đánh lừa khá nhiều, nhưng liên quan đến rất nhiều trig và tốn kém tính toán.

This paper by Dan Sunday cung cấp một thuật toán lai chính xác như số cuộn dây nhưng đơn giản như thuật toán như thuật toán truyền tia. Nó thổi tôi đi như thế nào thanh lịch nó được.

Xem https://stackoverflow.com/a/33974251/338479 cho mã của tôi sẽ thực hiện tính toán điểm trong đường cho một đường bao gồm các đoạn đường, vòng cung và vòng tròn.