|
|
|
|
Канал Игры Мечты: «3D математика» |
|
|
|
DIMOSUS.X
 997 EGP
       
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
   |
|
Хм, на счет бага согласен.
Мне необходимо одновременно обрабатывать несколько сотен физически миров, в каждом из которых от несколько десятков до нескольких сотен физических объектов - придется чем то жертвовать...
добавлено спустя 3 минуты:
Попробую закодить и савнить производительность метода Мнска, если сопоставима, буду использовать его.
добавлено спустя 23 минуты:
Эээ, а какой самый быстрый способ найти площадь треугольника?
Полавина длины основания на высоту?
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом.
Последний раз редактировалось: DIMOSUS.X (16:13 13-01-2011), всего редактировалось 2 раз(а) |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
И еще, каким макаром площадь треугольника станет отрицательной?
добавлено спустя 3 минуты:
То есть как определить - отнимать или добавлять площадь текущего треугольника?
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом.
Последний раз редактировалось: DIMOSUS.X (17:54 13-01-2011), всего редактировалось 1 раз |
|
|
|
Minx
 1011 EGP
   
Рейтинг канала: 6(332)
Репутация: 139
Сообщения: 10548
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
Эээ, а какой самый быстрый способ найти площадь треугольника?
Полавина длины основания на высоту?
|
Смотря что известно.
Если известны координаты вершин в 2D, то тот же метод трапеций.
2S = | (Xa-Xb)*(Ya+Yb) + (Xb-Xc)*(Yb+Yc) + (Xc-Xa)*(Yc+Ya) |
Здесь 1 или 2 слогаемых отрицательные (вот почему получается макар, что площадь отрицательна) и знак вычисления зависит от того, прямой проход у нас или обратный и как расположены точки
|| - модуль.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Реализовал и сравнил производительность для четырехугольника:
Метод площадей: 4.3 кк проверок в секунду.
Метод луча: 4.7 кк проверок в секунду.
В общем спасибо за алгоритм 
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Shirson
1605 EGP
  
Рейтинг канала: 7(626)
Репутация: 219
Сообщения: 16511
Откуда: 79°W 44°N
Зарегистрирован: 29.01.2002
|
|
| DIMOSUS.X : |
|
Но если добавить второй луч, с углом поворота в 1 градус относительно первого и проверить пересечения и для него, то вероятность ошибки сократится до фантастически малой.
|
Есть подозрение, что нечто подобное было сказано в группе програмного обеспечения ракеты-носителя Ариан в процессе разработки софта 
|
one of the most infamous computer bugs in history (кликните здесь для просмотра)
|
_________________
У меня бисера не доxеpа. |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Кстати, у метода площадей есть какие-нибудь подводные грабли? В часности при обработке вогнутых фигур?
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
1011 EGP
Рейтинг канала: 6(332)
Репутация: 139
Сообщения: 10548
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| Shirson : |
|
Есть подозрение, что нечто подобное было сказано в группе програмного обеспечения ракеты-носителя Ариан в процессе разработки софта
|
Может было сказано, но природа и причина ошибки Ariane совершенно другие, отличные от того, что в топике.
В общем случае могут использоваться подобные подходы (когда имеется вероятность ошибки), но с четким доказательством её ограничения сверху вероятности возникновения для любых входных данных. Но ни в одной серьезной системе такого не встречал. Хотя вероятностные подходы и оценки отработаны во многом.
| DIMOSUS.X : |
|
Кстати, у метода площадей есть какие-нибудь подводные грабли? В часности при обработке вогнутых фигур?
|
Не работает для вырожденных случаев фигур с нулевой площадью. Также если точка находится на стороне фигуры, то нужно все проверять отдельно.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
И снова я
2D, есть отрезок и произвольная точка — как найти координаты точки отрезка, ближайшей к произвольной точке?
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
1011 EGP
Рейтинг канала: 6(332)
Репутация: 139
Сообщения: 10548
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
Этож вроде базовые вещи, по идее должны быть в геометрической библиотеке.
Если оптимизить по скорости, то..
Отрезок AB, точка O. Находим квадраты OA и OB. Если их разность меньше больше квадрата AB, то ответом является точка A или B, смотря что из OA и OB минимально.
Иначе точка находится на перпендикуляре. Создаем прямую, проходящую через точку O, перпендикулярную AB (стандартная операция) и ищем её пересечение с AB (тож стандарт).
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (18:32 15-01-2011), всего редактировалось 2 раз(а) |
|
|
|
Jurec
348 EGP
Рейтинг канала: 4(76)
Репутация: 102
Сообщения: 1441 Заблокирован
Откуда: Seattle
Зарегистрирован: 25.02.2006
|
|
Через высоту параллелограмма (сторона параллелограмма - отрезок, произвольная точка - другая вершина параллелограмма):
Прощадь параллелограмма, это высота * основание. (S1)
Высота - это в твоём случае расстояние от отрезка до точки. (x)
Площадь параллелограмма еще можно найти как длинну вектора, полученного от векторного произведения двух его сторон. (S2)
x = S2 / основание(длинна отрезка)
__
а, координаты. сорри, туплю
_________________
MOV topka, C++
Последний раз редактировалось: Jurec (18:32 15-01-2011), всего редактировалось 1 раз |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Реализовал, кому интересно
|
C# (кликните здесь для просмотра)
public static Vector2 NearPointSeg(Vector2 Point, Segment Seg)
{
Vector2 v = Seg.Point2 - Seg.Point1;
Vector2 w = Point - Seg.Point1;
float c1 = Vector2.Dot(w, v);
if (c1 <= 0) return Seg.Point1;
float c2 = Vector2.Dot(v, v);
if (c2 <= c1) return Seg.Point2;
float b = c1 / c2;
Vector2 Pb = Seg.Point1 + b * v;
return Pb;
}
|
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Есть луч и окружность, нужно найти ближайшую к началу луча точку пересечения.
Кто подскажет? 
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Мда, просто решить не получилось. В общем вот что у меня накодилось(к моему удивлению это работает):
| Код: |
public static bool PerOtrOkr(Segment Seg, Vector2 OkrPos, float Radius, out Vector2 Col)
{
float x0 = OkrPos.X;
float y0 = OkrPos.Y;
float x1 = Seg.Point1.X;
float y1 = Seg.Point1.Y;
float x2 = Seg.Point2.X;
float y2 = Seg.Point2.Y;
float x01 = x1 - x0;
float y01 = y1 - y0;
float x02 = x2 - x0;
float y02 = y2 - y0;
float dx = x02 - x01;
float dy = y02 - y01;
float a = dx * dx + dy * dy;
float b = 2.0f * (x01 * dx + y01 * dy);
float c = x01 * x01 + y01 * y01 - Radius * Radius;
float D = b * b - 4 * a * c;
Col = new Vector2(999999, 999999);
if (D == 0)
{
if (a != 0)
{
float i = -b / (2 * a);
Col.X = x1 + (x2 - x1) * i;
Col.Y = y1 + (y2 - y1) * i;
}
}
if (D > 0)
{
if (a != 0)
{
float i1 = (-b + (float)Math.Sqrt(D)) / (2 * a);
float i2 = (-b - (float)Math.Sqrt(D)) / (2 * a);
Vector2 Col1 = new Vector2(0, 0);
Vector2 Col2 = new Vector2(0, 0);
Col1.X = x1 + (x2 - x1) * i1;
Col1.Y = y1 + (y2 - y1) * i1;
Col2.X = x1 + (x2 - x1) * i2;
Col2.Y = y1 + (y2 - y1) * i2;
if (Vector2.Distance(Seg.Point1, Col1) < Vector2.Distance(Seg.Point1, Col2)) Col = Col1;
else Col = Col2;
}
}
if (-b < 0) return (c < 0);
if (-b < (2.0f * a)) return (4.0f * a * c - b * b < 0);
return (a + b + c < 0);
} |
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом.
Последний раз редактировалось: DIMOSUS.X (03:33 22-01-2011), всего редактировалось 1 раз |
|
|
|
Guest
2075 EGP
       
Рейтинг канала: 5(167)
Репутация: 376
Сообщения: 27975
Откуда: Моск.
Зарегистрирован: 12.10.2004
|
|
| DIMOSUS.X : |
|
Col = new Vector2(999999, 999999);
|
ZOMG, WTF??? В смысле - почему такая зверская инициализация? Это же не предел ни разу.
добавлено спустя 4 минуты:
| DIMOSUS.X : |
|
Есть луч и окружность, нужно найти ближайшую к началу луча точку пересечения.
|
Можно ещё раз условие поточнее? Есть именно луч, т.е. точка+вектор неопределённой длины? Как задано?
А то больно сложное решение, есть мысль на попроще, но завтра, со свежего мозга...
_________________
Трещит земля как пустой орех
Как щепка трещит броня
Последний раз редактировалось: Guest (03:29 23-01-2011), всего редактировалось 1 раз |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
Col = new Vector2(999999, 999999);
Это я перестраховалсо , инициализировать можно любыми значениями — дальше по алгоритму идет перезапись этого вектора.
В качестве луча у меня отрезок Segment Seg — то бишь две точки.
Смысл моего алгоритма — решить квадратное уравнение полученное из пересечения прямой и отрезка.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
1011 EGP
Рейтинг канала: 6(332)
Репутация: 139
Сообщения: 10548
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
дальше по алгоритму идет перезапись этого вектора
|
Идет не всегда.
Например при a=0 получаем, что выход может быть как true, так и false, и, если правильно понимаю интерфейс функции, то внешний пользователь словит хардкодный (999999, 999999) и подумает, что это ответ.
Почему вместо этого
| Код: |
Vector2 Col1 = new Vector2(0, 0);
Vector2 Col2 = new Vector2(0, 0);
Col1.X = x1 + (x2 - x1) * i1;
Col1.Y = y1 + (y2 - y1) * i1;
Col2.X = x1 + (x2 - x1) * i2;
Col2.Y = y1 + (y2 - y1) * i2; |
не записать как
| Код: |
Vector2 Col1 = new Vector2(
x1 + (x2 - x1) * i1,
y1 + (y2 - y1) * i1);
Vector2 Col2 = new Vector2(
x1 + (x2 - x1) * i2,
y1 + (y2 - y1) * i2); |
?
тжс и с Col
_________________
μηδείς αγεωμέτρητος εισίτω
Последний раз редактировалось: Minx (07:35 23-01-2011), всего редактировалось 1 раз |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
| Minx : |
Идет не всегда.
Например при a=0 получаем, что выход может быть как true, так и false, и, если правильно понимаю интерфейс функции, то внешний пользователь словит хардкодный (999999, 999999) и подумает, что это ответ.
|
Есть такая вероятность — это я отдельно фильтрую.
Компилятор весьма умный и кроме уменьшения строк в коде это ни чего не даст.
Компилятор забракует — ему нужно что бы вектор out Vector2 Col был инициализирован при любом раскладе.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
1011 EGP
Рейтинг канала: 6(332)
Репутация: 139
Сообщения: 10548
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
Есть такая вероятность — это я отдельно фильтрую.
|
Т.е. при использовании функции пользователь будет каждый раз отдельно фильтровать, а сторонний пользователь (которым ты сам станешь через пару месяцев) получит грабли в самый подходящий момент.
| DIMOSUS.X : |
|
Компилятор весьма умный и кроме уменьшения строк в коде это ни чего не даст.
|
Не факт. При чем, я бы даже сказал, далеко не факт. Скорее всего дело обстоит с точностью до наобормот.
| DIMOSUS.X : |
|
Компилятор забракует — ему нужно что бы вектор out Vector2 Col был инициализирован при любом раскладе.
|
В любом случае есть null или явное указание в коде константы с названием вида DefaultVector, а не с магическими цифрами.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
DIMOSUS.X
997 EGP
Рейтинг канала: 4(67)
Репутация: 188
Сообщения: 3252
Откуда: Vilnius/Minsk
Зарегистрирован: 06.08.2008
|
|
| Minx : |
|
Т.е. при использовании функции пользователь будет каждый раз отдельно фильтровать, а сторонний пользователь (которым ты сам станешь через пару месяцев) получит грабли в самый подходящий момент.
|
Это будут исключительно грабли пользователя, так как а=0 получится только если начало и конец луча совпадают.
_________________
Даже ежики ежиков могут с трудом,
Иначе бы ежики были кругом. |
|
|
|
Minx
1011 EGP
Рейтинг канала: 6(332)
Репутация: 139
Сообщения: 10548
Откуда: Gomel, Belarus
Зарегистрирован: 19.11.2005
|
|
| DIMOSUS.X : |
|
Это будут исключительно грабли пользователя, так как а=0 получится только если начало и конец луча совпадают.
|
Квадрат float получит 0 не только в этом случае.
_________________
μηδείς αγεωμέτρητος εισίτω |
|
|
|
|
|
|
|
|
Канал Игры Мечты: «3D математика» |
|
|
