Перекресток многоугольника javascript

Question

Я использовал этот код: http://www.amphibian.com/blogstuff/collision.html. в тестовом файле HTML я изменил первый треугольник

triangle1.addPoint({"x":-20, "y":-20}); 
triangle1.addPoint({"x":-20, "y":20}); 
triangle1.addPoint({"x":20, "y":20}); 
triangle1.addPoint({"x":20, "y":10}); 
triangle1.addPoint({"x":10, "y":10}); 
triangle1.addPoint({"x":10, "y":-20}); 

теперь, когда я двигаю другой треугольник с внутри этой формы до пересечения дает мне Неправильно пересечение. Любая идея, где может быть проблема?

Answer 1

Хорошо, я настроил fiddle для тех, кто хочет поиграть с этим. Вот результаты:

Скрипт использует разделяющей оси теоремы или (как Википедия называет его) Hyperplane separation theorem, как описано в источнике polygon.js:

/* 
* To detect intersection with another Polygon object, this 
* function uses the Separating Axis Theorem. It returns false 
* if there is no intersection, or an object if there is. The object 
* contains 2 fields, overlap and axis. Moving the polygon by overlap 
* on axis will get the polygons out of intersection. 
*/ 
Polygon.prototype.intersectsWith = function(other) { 

Эта теорема применим только к выпуклым многоугольникам. Ваша форма не выпуклая, поскольку в ней есть «вмятина». Вот почему сценарий неправильно сообщает, что фигуры пересекаются. Если вам нужно заставить его работать с вогнутыми фигурами, вам придется сначала разбить вогнутую форму на отдельные выпуклые части, а затем применить теорему ко всем отдельным частям. Очевидно, это делает скрипт более сложным, так как вам нужно перебирать поперечное произведение вогнутых частей двух фигур.

Answer 2

Вот моя не слишком сложная реализация поиска многоугольника пересечения двух полигонов.

Он работает для выпуклых и вогнутых многоугольников, но не для сложных (самопересекающихся) полигонов. Алгоритм довольно похож на алгоритм, представленный в Margalit & Knott.

Его сложность составляет около 4 * n1 * n2, где n1 и n2 - числа вершин в многоугольниках, пересечение которых вычисляется.

Это отдельный автономный .js-файл. «Многоугольник» рассматривается как любой массив javascript двумерных точек. «Точка» - это любой объект javascript с числовыми свойствами x и y.

Внедрение функциональности Союза поверх существующего не должно быть проблемой, и я сделаю это, возможно, в ближайшее время.

Intersection of 2D polygons