Как я могу определить, содержит ли замкнутый путь заданную точку?

Question

В Android у меня есть объект Path, который, как я знаю, определяет замкнутый путь, и мне нужно выяснить, содержится ли заданная точка в пути. То, на что я надеялся, было что-то вроде

path.contains (int x, int y)

но этого, похоже, не существует.

Конкретная причина, по которой я ищу это, заключается в том, что у меня есть набор фигур на экране, определенных как контуры, и я хочу выяснить, на какую из них нажал пользователь. Если есть лучший способ приблизиться к этому, например, использовать различные элементы пользовательского интерфейса, а не делать это «сложным путем» самостоятельно, я открыт для предложений.

Я открыт для написания алгоритма сам, если мне нужно, но это означает другое исследование, я думаю.

Answer 1

Вот что я сделал и, похоже, работает:

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

Теперь вы можете использовать метод region.contains(x,y).

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

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

** Обновление 6/7 /2010 ** Метод region.setPath вызовет сбой моего приложения (без предупреждающего сообщения), если rectF слишком велик.Вот мое решение:

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

Класс android.graphics.Path не имеет такого метода.У класса Canvas есть область отсечения, которая может быть установлена ​​на путь, нет способа проверить его по точке.Вы можете попробовать Canvas.quickReject, проверяя один прямоугольник (или 1x1 Rect).Я не знаю, проверяет ли это на самом деле путь или только вмещающий прямоугольник.

Класс Region явно отслеживает только содержащий прямоугольник.

Возможно, вы захотите нарисовать каждую из ваших областей в 8-битном альфа-слое растрового изображения с каждым Path, заполненным собственным значением цвета (убедитесь, что сглаживание отключено в вашем Paint),Это создает своего рода маску для каждого пути, заполненного индексом пути, по которому он был заполнен.Тогда вы можете просто использовать значение пикселя в качестве индекса в вашем списке путей.

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

Затем найдите точки,

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

Обязательно проверьте на 255 (без пути)если есть незаполненные баллы.

Answer 3

WebKit SkiaUtils имеет обходной путь C ++ для ошибки Рэнди Финдли:

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

Для полноты я хочу сделать пару замечаний здесь:

Начиная с API 19, существует операция пересечения для путей. Вы можете создать очень маленький квадратный путь вокруг вашей контрольной точки, пересечь его с путем и посмотреть, является ли результат пустым или нет.

Вы можете преобразовать пути в регионы и выполнить операцию contains () . Однако регионы работают в целочисленных координатах, и я думаю, что они используют преобразованные (пиксельные) координаты, поэтому вам придется работать с этим. Я также подозреваю, что процесс преобразования требует больших вычислительных ресурсов.

Алгоритм пересечения ребер, который опубликовал Ганс, хорош и быстр, но вы должны быть очень осторожны в определенных угловых случаях, например, когда луч проходит непосредственно через вершину или пересекает горизонтальное ребро, или когда ошибка округления это проблема, которая всегда есть.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * '*' * '' '' '' '' '' '' '' '' '' '' в значительной степени ''] не требует больших усилий;

Эта статья Дэна Сандея дает гибридный алгоритм, который так же точен, как число обмоток, но так же прост в вычислительном отношении, как и алгоритм приведения лучей. Это поразило меня, как это было элегантно.

См. https://stackoverflow.com/a/33974251/338479 моего кода, который будет выполнять вычисление точки на пути для пути, состоящего из отрезков, дуг и окружностей.

Answer 5

Я знаю, что немного опоздал на вечеринку, но я решил бы эту проблему, подумав об этом, как об определении, находится ли точка в многоугольнике.

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

Математика вычисляется медленнее, когда вы смотрите на сплайны Безье, а не на отрезки, но рисование луча из точки по-прежнему работает.