Комментарии 13
Rect.contains(int x, int y)/RectF.contains(int x, int y) как вариант для прямоугольников и всего остального, что Вы готовы считать прямоугольником, чтобы избежать вычислений).
Вы правы, это хороший способ для уменьшения числа вычислений, именно поэтому в своей программе я проверяю точку на принадлежность прямоугольнику, в который вписан объект, перед тем, как выпускать «тяжёлую артиллерию».
Если интересно как это реализовать проще всего: habrahabr.ru/post/161237/
Для похожей задачи использовал примерно следующее:
Path path; //многоугольник
RectF clipRect; //границы многоугольника (bounds)
Region clip = new Region(clipRect);
Region pathRegion = new Region();
pathRegion.setPath(path, clip);
//...
if (pathRegion.contains(x, y))
{
//...
}
Я попробовал ваш вариант и должен отметить, что он работает замечательно.
Но с другой стороны он мне не подходит по ряду причин:
— почти всегда я получаю вещественные значения координат точки, т.к. конвертирую координаты точки касания в другую единицу измерения. Поэтому int сразу отпадает — каст к нему ведёт к большим погрешностям в работе приложения.
— краткое тестирование времени выполнения методов:
для многоугольника с N примерно равным 10 — 15 возвращает одинаковое время работы двух методов — 0...1 мс. Ни в коем случае не утверждаю, что какой-то из способов хуже или лучше, но для моих задач такой производительности вполне хватает.
Думаю, что если найду время, то попробую протестировать нативный и самописный методы на производительность более тщательно.
Но с другой стороны он мне не подходит по ряду причин:
— почти всегда я получаю вещественные значения координат точки, т.к. конвертирую координаты точки касания в другую единицу измерения. Поэтому int сразу отпадает — каст к нему ведёт к большим погрешностям в работе приложения.
— краткое тестирование времени выполнения методов:
long time = System.currentTimeMillis();
// Do something...
Log.i("Time:", String.valueOf(System.currentTimeMillis() - time));для многоугольника с N примерно равным 10 — 15 возвращает одинаковое время работы двух методов — 0...1 мс. Ни в коем случае не утверждаю, что какой-то из способов хуже или лучше, но для моих задач такой производительности вполне хватает.
Думаю, что если найду время, то попробую протестировать нативный и самописный методы на производительность более тщательно.
Данная задача широко известна в вычислительной геометрии, однако в русскоязычной литературе практически не описана.
Я в 1997 году покупал книгу Майкла Ласло «Вычислительная геометрия и компьютерная графика» на русском языке. Там были и алгоритмы определения принадлежности точки многоугольнику, и триангуляция Делоне, и диаграммы Вороного…
Данная задача широко известна в вычислительной геометрии, однако в русскоязычной литературе практически не описана.
Да ну ладно вам! Миллион раз описана, разжевана и в рот положена. И столько есть мест, где подсмотреть решение можно
Не кидайтесь словами, кидайтесь ссылками.
Ну, например я, как дурак изобретал метод «интеграла по контуру» в дискретном варианте «количество оборотов». «А на утро через год узнал, что эти слова уже написаны другим поэтом».
Хотя это было эдак в 1993, тогда нельзя было «вот тако вот так взять и гуглануть». И литературы по комп-графике было маловато.
Тем не менее по теме: в эти годы на хабре вопрос посчёта оборотов освещался не раз.
Хотя это было эдак в 1993, тогда нельзя было «вот тако вот так взять и гуглануть». И литературы по комп-графике было маловато.
Тем не менее по теме: в эти годы на хабре вопрос посчёта оборотов освещался не раз.
Прошёл по ссылке, просмотрел первые три страницы результатов. Про метод учёта числа пересечений написано почти на каждой странице. Про метод учёта числа оборотов написано не больше, чем есть на википедии.
Пожалуй я останусь при мнении, что фраза
Пожалуй я останусь при мнении, что фраза
… разжевана и в рот положена...больше подходит для данного топика.
Давайте будет считать, что я не совсем точно выразился. В русскоязычной литературе из двух вышеназванных методов я встречал только метод учёта числа пересечений, либо оба со скудным описанием.
Я буду только рад, если в комментариях будут появляться ссылки на различные источники. Думаю, что это будет многим интересно.
А пока подредактирую пост для устранения своей неточности. Всем спасибо за комментарии.
Я буду только рад, если в комментариях будут появляться ссылки на различные источники. Думаю, что это будет многим интересно.
А пока подредактирую пост для устранения своей неточности. Всем спасибо за комментарии.
Для выпуклых многоугольников есть простой способ: если точка лежит правее каждого отрезка многоугольника, то точка находится внутри многоугольника, иначе — снаружи. Отрезки должны идти по часовой стрелке.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача об определении принадлежности точки многоугольнику