Содержание этой статьи очень простые, в основном для начинающих, таких как я, поэтому, пожалуйста, попросите всех императоров алгоритма взглянуть
Цитировать
Известно, что сегмент линии 1 (a, b) и линейный сегмент 2 (c, d), где ABCD является конечной точкой, найдите точку пересечения P сегмента линии. (параллельные или коллинеарные считаются непересекающимися)
Алгоритм 1: Найдите точку пересечения прямой линии, где расположены два сегмента линии, а затем определите, находится ли точка пересечения на двух сегментах линии.
При поиске точки пересечения прямой линии мы можем найти ее через общее уравнение AX+By+C = 0 прямой линии (ABC в уравнении является коэффициентом, а не конечной точкой, упомянутой выше. Кроме того, точечные косое уравнения и уравнения наклонного перехвата также могут использоваться, а не здесь).
Затем, основываясь на позиционной взаимосвязи между точкой пересечения и конечной точкой сегмента линии, мы можем судить, находится ли точка пересечения в сегменте линии.
Формула заключается в следующем:
<code> function segmentsintr (a, b, c, d) { /** 1 Решите систему линейных уравнений и найдите пересечение сегментов линейных сегментов. **/ // Если знаменатель равен 0, он параллельный или коллинеарный, и не пересекает знаменатель var = (by - ay)*(dx - cx) - (ax - bx)*(cy - dy); if (знаменатель == 0) {вернуть false; } // Координата пересечения прямой линии, где расположен сегмент линии (x, y) var x = ((bx - ax) * (dx - cx) * (cy - ay) + (by - ay) * (dx - cx) * ax - (dy - cy) * (bx - ax) * cx) / деноминатор; var y = - ((by - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (by - ay) * cy) / grainator; /** 2 Определите, находится ли пересечение в двух сегментах **/if (// пересечение в сегменте 1 (x - ax) * (x - bx) <= 0 && (y - ay) * (y - by) <= 0 // и пересечение также в сегменте линии 2 && (x - cx) * (x - dx) <= 0 && (y-) (y) (y) (y) (y) (y) <=/(y) * (x) * Вернитесь на перекресток p return {x: x, y: y}} // в противном случае, не соответствует возврату false} </code>Алгоритм сначала имеет четкую и простую для понимания идею, но его производительность не высока. Потому что он вычисляет пересечение до того, как неясно, является ли пересечение действительным (в онлайн -сегменте), которое занимает много времени.
Если точка пересечения, наконец, обнаружена недействительной, то предыдущий расчет будет напрасным. Более того, весь процесс расчета также очень сложный.
Итак, есть ли способ сказать, есть ли сначала эффективная точка пересечения, а затем рассчитать ее?
Очевидно, ответ - да. Так что некоторые алгоритмы найдены.
Алгоритм 2: Определите, являются ли две конечные точки каждого сегмента линии на обеих сторонах другого сегмента линии. Затем найдите пересечение прямой линии, где расположены две сегменты линии, в противном случае они не пересекаются.
Первый шаг - определить, являются ли две точки с обеих сторон определенного сегмента линии. Обычно можно использовать метод проекции:
Найдите нормальный вектор сегмента линии, затем проецируйте точку на нормальную линию и, наконец, оцените взаимосвязь между точкой и сегментом линии на основе прогнозируемой позиции.
Смотрите изображение ниже
Проекция на нормальном сегменте линии CD точки A и точки B показана на рисунке. В настоящее время нам также необходимо проецировать компакт -диск сегмента линии на нашей обычной линии (просто выберите одну из точек C или точки D).
В основном используется для справки.
На рисунке проекция точки A и точки B проецируется на обеих сторонах проекции точки C, что указывает на обе стороны линейного сегмента CD сегмента линии AB.
Точно так же просто судите, является ли CD с обеих сторон сегмента линии AB.
Поиск норм, проекций и других вещей звучит очень сложно, но на самом деле это действительно довольно сложно для меня. Я мало что знал о знаниях о геометрии несколько месяцев назад (я забыл все знания о геометрии, когда изучал: '()'
К счастью, обучение и реализация не являются сложными, и есть формулы, за которыми следует следовать.
Найдите нормальный сегмент линии AB:
var nx = by - ay, ny = ax - bx; var normalline = {x: nx, y: ny}; Примечание. Где геометрические значения normalLine.x и normalLine.y представляют направление нормальной линии, а не координаты.
Найдите позицию проекции точки C на нормальной линии:
var dist = normalline.x*cx + normalline.y*cy;
ПРИМЕЧАНИЕ. «Положение проекции» здесь представляет собой скаляр, который представляет расстояние до происхождения нормального, а не координаты точки проекции.
Обычно этого достаточно, чтобы узнать это расстояние.
После того, как мы рассчитываем проекцию точек A (DISTA), точки B (DILSB) и точки C (DISTC) на рисунке, мы можем легко оценить относительное положение на основе их соответствующих размеров.
Когда DILE == DILEB == DISTC, два сегмента коллинеарны
Когда дистать == distb! = Distc, два сегмента линии параллельны
Когда Dista и Distb находятся на одной стороне Distc, два сегмента линии не пересекаются.
Когда Dista и Distb находятся на противоположной стороне DISTC, необходимо ли снова оценить два сегмента линии.
Предыдущие шаги только реализуют «пересекаются сегменты линий». Когда результат верен, нам нужно дополнительно найти точку пересечения.
Давайте поговорим о процессе поиска точки пересечения позже. Давайте сначала посмотрим на полную реализацию этого алгоритма:
Функция сегментов intr (a, b, c, d) {// нормальный n1 var nx1 = (by - ay), ny1 = (ax - bx); // нормальный n2 var nx2 = (dy - cy), ny2 = (cx - dx); // два нормала умножаются, если результат равен 0, это означает, что сегмент линии AB и сегмент CD параллельны или коллинеарно, и не пересекают var DENMINATOR = NX1*NY2 - NY1*NX2; if (знаменатель == 0) {вернуть false; } // Проекция на нормальном n2 var distc_n2 = nx2 * cx + ny2 * cy; var dista_n2 = nx2 * ax + ny2 * ay-distc_n2; var distb_n2 = nx2 * bx + ny2 * by-distc_n2; // Проекция точки A и точки B находится на одной и той же стороне проекции точки C (для случая в сегменте линии этот пример рассматривается как непересекающийся); if (dista_n2*distb_n2> = 0) {return false; } // // Судить о взаимосвязи между точкой C точкой D и сегментом линии AB, принцип такой же, как и выше, // // Проекция на нормальном n1 var dista_n1 = nx1 * ax + ny1 * ay; var distc_n1 = nx1 * cx + ny1 * cy-dista_n1; var distd_n1 = nx1 * dx + ny1 * dy-dista_n1; if (distc_n1*distd_n1> = 0) {return false; } // Рассчитайте координаты интерсекции var fraction = dista_n2 / знаменатель; var dx = фракция * ny1, dy = -fraction * nx1; return {x: ax + dx, y: ay + dy}; }Метод, используемый для поиска координат точки пересечения в конце, выглядит немного странно, и кажется, что он незаметный.
Фактически, это похоже на алгоритм в алгоритме 1, за исключением того, что многие из терминов расчета в нем были рассчитаны заранее.
Другими словами, часть алгоритма, чтобы найти координаты точки пересечения в двух милях, фактически сделана из линейных уравнений прямой линии.
Теперь давайте сравним алгоритм один и алгоритм два простым и грубым и ненаучным способом:
1. В лучшем случае сложность двух алгоритмов одинакова
2. В худшем случае расчет количества алгоритма 1 и алгоритма 2 почти одинаково
3. Однако алгоритм 2 обеспечивает больше «условий раннего конца», поэтому в среднем алгоритм 2 должен быть лучше.
После фактического тестирования фактическая ситуация действительно имеет место.
Два предыдущих алгоритма в основном распространены и могут справляться с большинством ситуаций. Но на самом деле, есть лучший алгоритм.
Это то, что я только что узнал недавно (я узнал это сейчас и продал сейчас, не обращайте внимания на это ...)
Алгоритм 3: Определите, являются ли две конечные точки каждого сегмента линии на обеих сторонах другого сегмента линии. Если вы найдете пересечение прямой линии, где расположены две сегменты линии, в противном случае они не будут пересекаться.
(Да? Почему это кажется таким же, как алгоритм 2? Не сомневайтесь, что это действительно то же самое ...)
Так называемый алгоритм 3 на самом деле является просто улучшением алгоритма. 2. Основные улучшения:
Позиционная связь между точками и сегментами линий оценивается не по нормальной проекции, а по площади треугольников, состоящих из точек и сегментов линий.
Давайте сначала рассмотрим формулу треугольника области: известно, что три точки A (x, y) b (x, y) c (x, y) в области треугольника:
<code> var triarea = ((ax - cx) * (by - cy) - (ay - cy) * (bx - cx)) /2; </code>
Поскольку площадь параллелограмма (два вектора являются соседними сторонами), состоящая из двух векторов, разбитых == два вектора, вышеуказанная формула не сложно понять.
Более того, поскольку у векторов есть указания, область также имеет указания. Обычно мы используем против часовой стрелки как положительные и по часовой стрелке отрицательными.
Ключевыми моментами улучшенного алгоритма являются:
Если положительные и отрицательные признаки зоны треугольника, образованного «сегментом линии AB и точки C», отличаются от области треугольника, образованной «сегментом линии AB и точкой D»,
Затем точка C и точка D расположены с обеих сторон линейного сегмента AB.
Как показано на рисунке ниже:
Треугольник, показанный пунктирной линией на рисунке, имеет различные направления обмотки (порядок определения трех сторон), поэтому положительные и отрицательные символы области различны.
Сначала посмотрим на код:
Поскольку нам нужно только судить о символе, нам не нужно разделять следующее на 2 в предыдущей формуле области треугольника.
Функция сегментов intr (a, b, c, d) {// 2 раза превышает площадь треугольника abc var aea_abc = (ax - cx) * (by - cy) - (ay - cy) * (bx - cx); // 2 раза превышают площадь треугольника abd var area_abd = (ax - dx) * (by - dy) - (ay - dy) * (bx - dx); // Если символы площади одинаковы, две точки не пересекаются с той же стороны (в случае точки в сегменте линии, этот пример рассматривается как непересекающийся); if (reable_abc*reaue_abd> = 0) {return false; } // 2 раза превышает область треугольника cda var gree_cda = (cx - ax) * (dy - ay) - (cy - ay) * (dx - ax); // 2 раза превышают площадь треугольника CDB // Примечание. Здесь есть небольшая оптимизация. Нет необходимости рассчитать область с формулой, но она получена путем добавления и вычитания трех известных областей. var geable_cdb = gree_cda + reair_abc - reair_abd; if (reable_cda * reaue_cdb> = 0) {return false; } // Рассчитайте координаты интерсекции var t = area_cda / (area_abd- area_abc); var dx = t*(bx - ax), dy = t*(by - ay); return {x: ax + dx, y: ay + dy}; }Наконец, часть, которая вычисляет координаты пересечения, такая же, как и алгоритм.
Основываясь на алгоритме 2, алгоритм 3 значительно упрощает шаги расчета, и код более оптимизирован. Можно сказать, что это лучшее среди трех алгоритмов. То же самое верно для фактических результатов теста.
Конечно, мы должны быть честными в JavaScript, временная сложность трех алгоритмов на самом деле одинакова для обычных расчетов (особенно по двигателю V8).
В моем тестовом примере я также провел аномальные перекрестные тесты на линии на миллион линий, чтобы расширить разрыв между тремя алгоритмами.
Суммировать
Тем не менее, с отношением к стремлению к совершенству и обучению, преследование лучшего алгоритма всегда имеет положительное значение. Выше приведено несколько алгоритмов, которые используют JS для достижения точек пересечения линейных сегментов. Контент не очень глубокий. Я надеюсь, что всем будет полезно изучать JS.