Всем доброго дня!
Появилась задача определения попадания точки внутрь многоугольника. При этом желательно определять фактически 4 состояния:
1. Точка внутри многоугольника;
2. Точка на ребре многоугольника;
3. Точка совпадает с вершиной многоугольника;
4. Точка снаружи многоугольника.
Пункты 2 и 3 конечно могут быть объединены. Но сама задача требует определения таких состояний.
И дополнительное условие (на сколько я понимаю достаточно важное): координаты вершин и проверяемой точки задаются в виде
double. На сколько я понимаю это заставляет вводить в алгоритм некую заданную точность или допуск (хотя вот тут могу быть и не прав). Почему такое уточняю: в свое время пока не нашел General Polygon Clipper натыкался на алгоритмы логических операций над многоугольниками, которые имели строгое ограничение: координаты вершин должны были быть целочисленными.
Готовый алгоритм для C++ был найден на
Хабре.
Найденный алгоритм был переписан на C#:public bool IsPoint3dInside1(Point3d p, double Tolerance)
{
if (VerticesCount < 3) return false;
int[,] q_patt = new int[2, 2] { {0,1}, {3,2} };
Point3d pred_pt = Vertices[VerticesCount - 1];
pred_pt.X -= test.X;
pred_pt.Y -= test.Y;
int pred_q = q_patt[Convert.ToInt32(pred_pt.Y < Tolerance), Convert.ToInt32(pred_pt.X < Tolerance)];
int w = 0;
for (int i = 0; i < VerticesCount; i++)
{
Point3d cur_pt = Vertices[i];
cur_pt.X -= test.X;
cur_pt.Y -= test.Y;
int q = q_patt[Convert.ToInt32(cur_pt.Y < Tolerance), Convert.ToInt32(cur_pt.X < Tolerance)];
switch (q - pred_q)
{
case -3: ++w; break;
case 3: --w; break;
case -2: if ((pred_pt.X * cur_pt.Y).CompareTo(pred_pt.Y * cur_pt.X) >= 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?
Буду благодарен за любую помощь. Заранее всем откликнувшимся большое спасибо!
