Для графики я бы предпочел не использовать целые числа. Многие системы используют целые числа для рисования пользовательского интерфейса (в конце концов, пиксели - это целые числа), но, например, macOS использует float для всего. macOS знает только точки, и точка может переводиться в один пиксель, но в зависимости от разрешения монитора она может переводиться во что-то другое. На экранах сетчатки половина точки (0,5 / 0,5) составляет пиксель. Тем не менее, я никогда не замечал, что пользовательские интерфейсы macOS значительно медленнее, чем другие пользовательские интерфейсы. Ведь 3D API (OpenGL или Direct3D) также работают с плавающими элементами, а современные графические библиотеки очень часто используют преимущества ускорения графического процессора.
Теперь вы сказали, что скорость - ваша главная задача, хорошо, давайте перейдем к скорости. Прежде чем запускать какой-либо сложный алгоритм, сначала выполните простой тест. Создайте ограничивающую рамку с выравниванием по оси вокруг многоугольника. Это очень легко, быстро и уже может обезопасить вас от многих вычислений. Как это работает? Выполните итерацию по всем точкам многоугольника и найдите минимальные / максимальные значения X и Y.
например. у вас есть баллы (9/1), (4/3), (2/7), (8/2), (3/6). Это означает, что Xmin = 2, Xmax = 9, Ymin = 1 и Ymax = 7. Точка за пределами прямоугольника с двумя ребрами (2/1) и (9/7) не может быть внутри многоугольника.
// p is your point, p.x is the x coord, p.y is the y coord
if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) {
// Definitely not within the polygon!
}
Это первый тест для любой точки. Как видите, этот тест очень быстрый, но он также очень грубый. Для обработки точек, которые находятся внутри ограничивающего прямоугольника, нам нужен более сложный алгоритм. Есть несколько способов, как это можно рассчитать. Какой метод работает, также зависит от того, может ли многоугольник иметь отверстия или всегда будет сплошным. Вот примеры твердых (одна выпуклая, одна вогнутая):
А вот с дыркой:
Зеленый имеет отверстие в середине!
Самый простой алгоритм, который может обрабатывать все три описанных выше случая и который все еще довольно быстр, называется приведение лучей . Идея алгоритма довольно проста: нарисуйте виртуальный луч из любой точки за пределами многоугольника к своей точке и посчитайте, как часто он попадает на сторону многоугольника. Если число совпадений четное, оно находится за пределами многоугольника, если оно нечетное, оно внутри.
Алгоритм с числом обмоток был бы альтернативой, он более точен для точек, находящихся очень близко к линии многоугольника, но он также намного медленнее. Приведение лучей может быть неудачным для точек, расположенных слишком близко к стороне многоугольника из-за ограниченной точности с плавающей точкой и проблем с округлением, но в действительности это вряд ли проблема, так как если точка находится близко к стороне, это часто визуально даже невозможно зритель распознает, находится ли он уже внутри или все еще снаружи.
У вас все еще есть ограничительная рамка выше, помните? Просто выберите точку за пределами ограничительной рамки и используйте ее в качестве отправной точки для вашего луча. Например. точка (Xmin - e/p.y) точно находится за пределами многоугольника.
Но что такое e? Ну, e (на самом деле epsilon) дает ограничивающей рамке padding . Как я уже сказал, трассировка лучей завершится неудачей, если мы начнем слишком близко к линии многоугольника. Поскольку ограничивающий прямоугольник может равняться многоугольнику (если многоугольник является выровненным по оси прямоугольником, ограничивающий прямоугольник равен самому многоугольнику!), Для обеспечения безопасности нам понадобятся некоторые отступы, вот и все. Насколько большой вы должны выбрать e? Не слишком большой Это зависит от масштаба системы координат, который вы используете для рисования. Если ширина шага вашего пикселя равна 1,0, просто выберите 1,0 (но 0,1 также сработало бы)
Теперь, когда у нас есть луч с его начальной и конечной координатами, проблема переходит от " - это точка внутри многоугольника " до ", как часто луч пересекает сторону многоугольника ». Поэтому мы не можем просто работать с точками многоугольника, как раньше, теперь нам нужны фактические стороны. Сторона всегда определяется двумя точками.
side 1: (X1/Y1)-(X2/Y2)
side 2: (X2/Y2)-(X3/Y3)
side 3: (X3/Y3)-(X4/Y4)
:
Вам нужно проверить луч со всех сторон. Считайте, что луч - вектор, а каждая сторона - вектор. Луч должен поразить каждую сторону ровно один раз или никогда. Он не может попасть в одну и ту же сторону дважды. Две линии в 2D-пространстве всегда будут пересекаться ровно один раз, если они не параллельны, и в этом случае они никогда не пересекаются. Однако, поскольку векторы имеют ограниченную длину, два вектора могут не быть параллельными и никогда не пересекаться, потому что они слишком короткие, чтобы когда-либо встречаться друг с другом.
// Test the ray against all sides
int intersections = 0;
for (side = 0; side < numberOfSides; side++) {
// Test if current side intersects with ray.
// If yes, intersections++;
}
if ((intersections & 1) == 1) {
// Inside of polygon
} else {
// Outside of polygon
}
Пока все хорошо, но как проверить, пересекаются ли два вектора? Вот некоторый C-код (не проверенный), который должен помочь:
#define NO 0
#define YES 1
#define COLLINEAR 2
int areIntersecting(
float v1x1, float v1y1, float v1x2, float v1y2,
float v2x1, float v2y1, float v2x2, float v2y2
) {
float d1, d2;
float a1, a2, b1, b2, c1, c2;
// Convert vector 1 to a line (line 1) of infinite length.
// We want the line in linear equation standard form: A*x + B*y + C = 0
// See: http://en.wikipedia.org/wiki/Linear_equation
a1 = v1y2 - v1y1;
b1 = v1x1 - v1x2;
c1 = (v1x2 * v1y1) - (v1x1 * v1y2);
// Every point (x,y), that solves the equation above, is on the line,
// every point that does not solve it, is not. The equation will have a
// positive result if it is on one side of the line and a negative one
// if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector
// 2 into the equation above.
d1 = (a1 * v2x1) + (b1 * v2y1) + c1;
d2 = (a1 * v2x2) + (b1 * v2y2) + c1;
// If d1 and d2 both have the same sign, they are both on the same side
// of our line 1 and in that case no intersection is possible. Careful,
// 0 is a special case, that's why we don't test ">=" and "<=",
// but "<" and ">".
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// The fact that vector 2 intersected the infinite line 1 above doesn't
// mean it also intersects the vector 1. Vector 1 is only a subset of that
// infinite line 1, so it may have intersected that line before the vector
// started or after it ended. To know for sure, we have to repeat the
// the same test the other way round. We start by calculating the
// infinite line 2 in linear equation standard form.
a2 = v2y2 - v2y1;
b2 = v2x1 - v2x2;
c2 = (v2x2 * v2y1) - (v2x1 * v2y2);
// Calculate d1 and d2 again, this time using points of vector 1.
d1 = (a2 * v1x1) + (b2 * v1y1) + c2;
d2 = (a2 * v1x2) + (b2 * v1y2) + c2;
// Again, if both have the same sign (and neither one is 0),
// no intersection is possible.
if (d1 > 0 && d2 > 0) return NO;
if (d1 < 0 && d2 < 0) return NO;
// If we get here, only two possibilities are left. Either the two
// vectors intersect in exactly one point or they are collinear, which
// means they intersect in any number of points from zero to infinite.
if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR;
// If they are not collinear, they must intersect in exactly one point.
return YES;
}
Входными значениями являются две конечные точки вектора 1 (v1x1/v1y1 и v1x2/v1y2) и вектора 2 (v2x1/v2y1 и v2x2/v2y2). Итак, у вас есть 2 вектора, 4 точки, 8 координат. YES и NO ясно. YES увеличивает пересечения, NO ничего не делает.
А как насчет Коллинеар? Это означает, что оба вектора лежат на одной бесконечной линии, в зависимости от положения и длины, они вообще не пересекаются или пересекаются в бесконечном количестве точек. Я не совсем уверен, как справиться с этим делом, я бы не посчитал это пересечением в любом случае. Ну, во всяком случае, этот случай довольно редок на практике из-за ошибок округления с плавающей запятой; лучший код, вероятно, не проверял бы для == 0.0f, но вместо этого для чего-то вроде < epsilon, где epsilon - довольно небольшое число.
Если вам нужно протестировать большее количество точек, вы, конечно, можете немного ускорить все это, сохранив в памяти стандартные формы сторон многоугольника в памяти, поэтому вам не придется каждый раз пересчитывать их. Это сэкономит вам два умножения с плавающей запятой и три вычитания с плавающей запятой при каждом тесте в обмен на сохранение в памяти трех значений с плавающей запятой на каждую сторону многоугольника. Это типичное соотношение между памятью и временем вычислений.
Последнее, но не менее важное: если вы можете использовать 3D-оборудование для решения проблемы, есть интересная альтернатива. Просто пусть GPU сделает всю работу за вас. Создайте поверхность для рисования вне экрана. Заполните его полностью черным цветом. Теперь позвольте OpenGL или Direct3D нарисовать ваш многоугольник (или даже все ваши многоугольники, если вы просто хотите проверить, находится ли точка в каком-либо из них, но вам не важно, какая из них), и заполните многоугольники другим цвет, например белый. Чтобы проверить, находится ли точка внутри многоугольника, получите цвет этой точки с поверхности рисования. Это всего лишь O (1) выборка из памяти.
Конечно, этот метод можно использовать, только если ваша поверхность для рисования не обязательно должна быть огромной. Если он не может поместиться в память графического процессора, этот метод медленнее, чем в ЦП. Если он должен быть огромным, и ваш графический процессор поддерживает современные шейдеры, вы все равно можете использовать графический процессор, реализовав приведенное выше приведение лучей в качестве графического шейдера, что абсолютно возможно. Для большого количества полигонов или большого количества точек для тестирования это окупится, учитывая, что некоторые графические процессоры смогут тестировать от 64 до 256 точек параллельно. Тем не менее, обратите внимание, что передача данных из CPU в GPU и обратно всегда обходится дорого, поэтому для простого тестирования пары точек на пару простых многоугольников, где либо точки, либо многоугольники являются динамическими и будут часто меняться, подход с использованием графического процессора редко платит выкл.