Илья Николаевский, я попытался частично реализовать вашу библиотеку, а именно функционал нахождения касательных. В принципе, у JavaScript и C++ много общего в синтаксисе.
Отличия моей реализации от вашей в следующем:
1) Т.к. переопределение операторов не поддерживается в JavaScript я реализовал эти операторы через методы классов:
Point - Point -> Point.minus(Point)
Point == Point -> Point.equal(Point)
Point * Point -> Point.multi(Point)
Point ^ Point -> Point.p_multi(Point)
2) В JavaScript как такого оператора ^ нет, поэтому я реализовал его в функции XOR:
function XOR(a,b) {
return ( a || b ) && !( a && b );
}
this.IsInside = function(a) {
var vs = this.points;
var x = a.x, y = a.y;
var inside = false;
for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
var xi = vs[i].x, yi = vs[i].x;
var xj = vs[j].x, yj = vs[j].x;
var intersect = ((yi > y) != (yj > y)) && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
if (intersect) inside = !inside;
}
return inside;
}
6) В массиве касательных я обращаюсь к первому/второму элементу не через .first/.second а по индексу
7) У меня динамическая типизация
Остальное я точно реализовал по вашей библиотеке, однако почему ты выдаются вовсе не всегда касательные, но и секущие
Например вот так:
На каком этапе могла возникнуть ошибка?
(Я предполагал, что в методе GetTangentIds(), однако я несколько раз сверялся, различий не обнаружил. Может у меня проблема в порядке вершин полигона?)
Николай Чуприк, а для случая когда в подстроке есть повторяющиеся буквы в Pw(x) будут одинаковые множители? т.е. грубо говоря если подстрока из 4 символов: АБАВ, то Pw(x) = p1 * p2 * p1 * p3?
Фокс Йовович, понял, я имел в виду прямую, включающую отрезок. По поводу касательных. Я имел в виду: построить по 2 касательных на каждый из всех полигонов. Но т.к. Вам не нравится слово касательные, то тогда:
построить по 2 таких отрезка к каждому из полигонов, что если взять прямую, которая включает этот отрезок, она будет иметь с полигоном ровно 1 общую точку. При этом эти отрезки не должны иметь с каким-либо полигоном более 1 общей точки
wataru, Я разобрался как раздувать полигоны. Но... Я реализовал шаг, где мы должны от каждой точки каждого полигона сгенерировать касательные на все остальные полигоны. Но скорость получается слишком низкая. Для всего 20 полигонов генерируется аж 1800+ касательных, и это почти за 4 секунды. Но сколько будет генерировать 100 полигонов? 1000? Может я как-то неправильно понял идею?
wataru, Можете пожалуйста поподробнее рассказать про раздутие полигона?
Я правильно понимаю, что я должен найти нормали к каждой стороне, т.е. координаты вектора (пару чисел), перпендикулярного к стороне и направленного от стороны наружу т.е. не в полигон, а от него.
Далее я должен к каждой вершине применить следующее преобразование:
1) Находим 2 стороны, которые включают эту вершину и берём от них нормали пусть vec_1 и vec_2
2) num=1/(cos(a/2)*sqrt(2+2cos(a))), где a - угол между нормалями.
3) к x вершины прибавляю (vec_1.x + vec_2.x) * num
4) к y вершины прибавляю (vec_1.y + vec_2.y) * num
но результат какой-то не очень вышел (красный - внутренний, зеленый - внешний)
и из этого я делаю вывод, что я что-то неправильно понял
wataru, Ну тут надо подумать будет... А как реализовать 2 вариант? Если просто бежать в противоположном направлении от ближайшего преследователя то мы можем упереться в стенку. Тут надо найти ближайший путь, который направлен максимально от преследователя, да?
wataru, между ботами, чтобы боты могли преследовать убегающих ботов, а убегающие боты - убегать от преследующих. Т.е. я правильно понимаю, что для того, чтобы сделать убегающего бота мне не надо добавлять вершины/ребра в граф, а достаточно использовать существующий граф?
wataru, Ну такие цифры очень радуют) Я планировал использовать полигоны не более 10 вершин. И ещё меня интересует вопрос: если я захочу, чтобы например были боты, которые преследуют, а были те, кто убегают, то получается надо будет ещё и боты-вершины соединить в рёбра, если они не будет пересекать полигоны?
maaGames, У меня персонаж как бешеный убегает от шаров) И я боюсь, что персонаж успеет даже за 0.5 секунд продвинутся так, что путь шара придётся поменять
Отличия моей реализации от вашей в следующем:
1) Т.к. переопределение операторов не поддерживается в JavaScript я реализовал эти операторы через методы классов:
2) В JavaScript как такого оператора ^ нет, поэтому я реализовал его в функции XOR:
3) Вместо
.Size()я использовал.length4) Другой способ генерации выпуклого полигона
5) Другая реализация метода
Polygon.IsInside()6) В массиве касательных я обращаюсь к первому/второму элементу не через
.first/.secondа по индексу7) У меня динамическая типизация
Остальное я точно реализовал по вашей библиотеке, однако почему ты выдаются вовсе не всегда касательные, но и секущие
Например вот так:
На каком этапе могла возникнуть ошибка?
(Я предполагал, что в методе
GetTangentIds(), однако я несколько раз сверялся, различий не обнаружил. Может у меня проблема в порядке вершин полигона?)