Какой наиболее оптимальный алгоритм попадания точки внутрь многоугольника? Всем доброго дня!
Появилась задача определения попадания точки внутрь многоугольника. При этом желательно определять фактически 4 состояния:
1. Точка внутри многоугольника;
2. Точка на ребре многоугольника;
3. Точка совпадает с вершиной многоугольника;
4. Точка снаружи многоугольника.
Пункты 2 и 3 конечно могут быть объединены. Но сама задача требует определения таких состояний.
И дополнительное условие (на сколько я понимаю достаточно важное): координаты вершин и проверяемой точки задаются в виде double. На сколько я понимаю это заставляет вводить в алгоритм некую заданную точность или допуск (хотя вот тут могу быть и не прав). Почему такое уточняю: в свое время пока не нашел General Polygon Clipper натыкался на алгоритмы логических операций над многоугольниками, которые имели строгое ограничение: координаты вершин должны были быть целочисленными.
Готовый алгоритм для C++ был найден на Хабре.Найденный алгоритм был переписан на C#:public bool IsPoint3dInside1(Point3d p, double Tolerance)
{
if (VerticesCount = 0) ++w; break;
case 2: if (!((pred_pt.X * cur_pt.Y).CompareTo(pred_pt.Y * cur_pt.X) >= 0)) --w; break;
}
pred_pt = cur_pt;
pred_q = q;
}
return w != 0;
}
Как видно отличия от исходного алгоритма небольшие, но есть:
1. Сравнение с 0 заменено на сравнение с переменной Tolerance;
2. Вместо прямого сравнения результатов умножения внутри switch я использую CompareTo.В итоге у меня вопросы такие:
1. На сколько сам алгоритм оптимален и быстр в сравнении с аналогами? Быстродействие достаточно важно, т.к. конечная программа должна прогонять через него миллионы точек и тысячи многоугольников, состоящих из сотен и тысяч вершин.
2. Прав ли я заменяя сравнение с 0 на сравнение с Tolerance? Если нет, то как тогда учитывать допуски?
3. Прав ли я в том, что заменил прямое сравнение >= на CompareTo?
Буду благодарен за любую помощь. Заранее всем откликнувшимся большое спасибо!
Какой наиболее оптимальный алгоритм попадания точки внутрь многоугольника? Всем доброго дня!
Появилась задача определения попадания точки внутрь многоугольника. При этом желательно определять фактически 4 состояния:
1. Точка внутри многоугольника;
2. Точка на ребре многоугольника;
3. Точка совпадает с вершиной многоугольника;
4. Точка снаружи многоугольника.
Пункты 2 и 3 конечно могут быть объединены. Но сама задача требует определения таких состояний.
И дополнительное условие (на сколько я понимаю достаточно важное): координаты вершин и проверяемой точки задаются в виде double. На сколько я понимаю это заставляет вводить в алгоритм некую заданную точность или допуск (хотя вот тут могу быть и не прав). Почему такое уточняю: в свое время пока не нашел General Polygon Clipper натыкался на алгоритмы логических операций над многоугольниками, которые имели строгое ограничение: координаты вершин должны были быть целочисленными.
Готовый алгоритм для C++ был найден на Хабре.Найденный алгоритм был переписан на C#:public bool IsPoint3dInside1(Point3d p, double Tolerance)
{
if (VerticesCount = 0) ++w; break;
case 2: if (!((pred_pt.X * cur_pt.Y).CompareTo(pred_pt.Y * cur_pt.X) >= 0)) --w; break;
}
pred_pt = cur_pt;
pred_q = q;
}
return w != 0;
}
Как видно отличия от исходного алгоритма небольшие, но есть:
1. Сравнение с 0 заменено на сравнение с переменной Tolerance;
2. Вместо прямого сравнения результатов умножения внутри switch я использую CompareTo.В итоге у меня вопросы такие:
1. На сколько сам алгоритм оптимален и быстр в сравнении с аналогами? Быстродействие достаточно важно, т.к. конечная программа должна прогонять через него миллионы точек и тысячи многоугольников, состоящих из сотен и тысяч вершин.
2. Прав ли я заменяя сравнение с 0 на сравнение с Tolerance? Если нет, то как тогда учитывать допуски?
3. Прав ли я в том, что заменил прямое сравнение >= на CompareTo?
Буду благодарен за любую помощь. Заранее всем откликнувшимся большое спасибо!
Появилась задача определения попадания точки внутрь многоугольника. При этом желательно определять фактически 4 состояния:
1. Точка внутри многоугольника;
2. Точка на ребре многоугольника;
3. Точка совпадает с вершиной многоугольника;
4. Точка снаружи многоугольника.
Пункты 2 и 3 конечно могут быть объединены. Но сама задача требует определения таких состояний.
И дополнительное условие (на сколько я понимаю достаточно важное): координаты вершин и проверяемой точки задаются в виде double. На сколько я понимаю это заставляет вводить в алгоритм некую заданную точность или допуск (хотя вот тут могу быть и не прав). Почему такое уточняю: в свое время пока не нашел General Polygon Clipper натыкался на алгоритмы логических операций над многоугольниками, которые имели строгое ограничение: координаты вершин должны были быть целочисленными.
Готовый алгоритм для C++ был найден на Хабре.Найденный алгоритм был переписан на C#:public bool IsPoint3dInside1(Point3d p, double Tolerance)
{
if (VerticesCount = 0) ++w; break;
case 2: if (!((pred_pt.X * cur_pt.Y).CompareTo(pred_pt.Y * cur_pt.X) >= 0)) --w; break;
}
pred_pt = cur_pt;
pred_q = q;
}
return w != 0;
}
Как видно отличия от исходного алгоритма небольшие, но есть:
1. Сравнение с 0 заменено на сравнение с переменной Tolerance;
2. Вместо прямого сравнения результатов умножения внутри switch я использую CompareTo.В итоге у меня вопросы такие:
1. На сколько сам алгоритм оптимален и быстр в сравнении с аналогами? Быстродействие достаточно важно, т.к. конечная программа должна прогонять через него миллионы точек и тысячи многоугольников, состоящих из сотен и тысяч вершин.
2. Прав ли я заменяя сравнение с 0 на сравнение с Tolerance? Если нет, то как тогда учитывать допуски?
3. Прав ли я в том, что заменил прямое сравнение >= на CompareTo?
Буду благодарен за любую помощь. Заранее всем откликнувшимся большое спасибо!
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Интересные статьи из справочника
Поможем написать учебную работу
Отвечай на вопросы, зарабатывай баллы и трать их на призы.
Подробнее
Подробнее
Переписанный алгоритм выглядит довольно оптимальным для задачи определения попадания точки внутрь многоугольника. Он имеет линейную сложность относительно числа вершин многоугольника. Однако скорость выполнения может зависеть от конкретной реализации и оптимизации компилятора.
Замена сравнения с 0 на сравнение с переменной Tolerance может быть оправдана, если необходимо учитывать некоторую погрешность или точность при сравнении координат точек. Однако стоит учитывать, что выбор значения Tolerance может влиять на точность определения попадания точки. Необходимо провести тесты с разными значениями Tolerance для определения оптимального.
Замена прямого сравнения >= на CompareTo может быть оправдана, если необходимо учесть точность вычислений с плавающей запятой. Однако в данном случае можно также использовать прямое сравнение с >=, если нет необходимости в точном сравнении значений с учетом их допуска.
В целом, предложенный алгоритм выглядит разумным для задачи определения попадания точки внутрь многоугольника. Рекомендуется провести тестирование и оптимизацию для достижения наилучшей производительности.