Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Progrmmer69
0 / 0 / 1
Регистрация: 01.12.2016
Сообщений: 19
1

Найти точки пересечения луча и окружности

11.12.2017, 15:24. Просмотров 1076. Ответов 7

Given a sphere of radius sphereRadius, center point is sphereCenter and a ray with origin rayStart and direction vector rayDirection (in 3D space).
Please check the figure below for a graphical example.
Найти точки пересечения луча и окружности

Implement function:
C++
1
2
3
4
5
Intersection FindIntersection(
    const Vector3F& rayStart,
    const Vector3F& rayDirection,
    const Vector3F& sphere Center,
    float sphereRadius);
Function returns _all_ intersection points (if any) of a sphere (defined by sphereCenter and sphereRadius) and a ray (defined by rayStart and rayDirection).

Here Intersection is a simple struct:
C++
1
2
3
4
5
6
struct Intersection
{
    Vector3p0;
    Vector3p1;
unsigned char count;
};
Intersection.count identifies how many intersections found. There are three possible values for count:
0 – no intersections, p0 and p1 are not valid (should contain zero along to count equal zero);
1 – one intersection and p0 has intersection point position in 3D space, the second one (p1) is not valid (should contain zero along to count equal zero);
2 – two intersections, p0 and p1 are both valid and have intersection positions in 3D space.
Make sure your solution is aware of all edge cases and respects proposed interface for FindIntersecton(…).

Notes:
Minimum precision of the solution is 1e_(-4) (epsilon used for floating values comparison is equal 0.0001).
Intersections points order matters – if intersections result has two points, then p0 should be closer to the rayStart position.
If solutions can’t be found because of incorrect input parameters, then the result should be the same as no intersections found.





C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cmath>
 
using namespace std;
 
static const float Epsilon = 1e-4f;
 
struct Vector3F
{
public:
    float x;
    float y;
    float z;
};
 
struct Intersection
{
public:
    Vector3F p0;
    Vector3F p1;
 
    unsigned char count;
};
 
Intersection FindIntersection(
 
);
 
int main() {
    const Vector3F rayStart{ 0.0f, 0.0f, 4.0f };
    const Vector3F rayDirection{ 0.0f, 0.0f, -1.0f };
 
    const Vector3F sphereCenter{ 0.0f, 0.0f, 0.0f };
    const float sphereRadius = 1.0f;
 
    const Intersection result = FindIntersection(
        rayStart,
        rayDirection,
        sphereCenter,
        sphereRadius);
 
    cout << "Intersection test result: " << endl;
    cout << "P0 = (" << result.p0.x << ", " << result.p0.y << ", " << result.p0.z << ")" << endl;
    cout << "P1 = (" << result.p1.x << ", " << result.p1.y << ", " << result.p1.z << ")" << endl;
    cout << "Count= " << static_cast<unsigned int>(result.count) << endl;
 
    system("pause");
    return 0;
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2017, 15:24
Ответы с готовыми решениями:

Найти точки пересечения гиперболы и окружности
Нужно найти точки пересечения гиперболы и окружности. Если смотреть с...

Найти точки пересечения отрезка и окружности
Here i go again :) Нужен код готовой функции для поиска точек пересечения...

Точки пересечения окружности и прямой
Необходимо создать программу которая находит точки пересечения окружности и...

Определить точки пересечения прямой и окружности
Задана окружность с центром в точке О(x0,y0) и радиусом R0 и прямая y=ax+b....

Дайте готовый код нахождения точки пересечения окружности с прямой :-)
Нужен код нахождения точки пересечения окружности с прямой. Прямая задана...

7
Kuzia domovenok
2436 / 2143 / 523
Регистрация: 25.03.2012
Сообщений: 7,720
Записей в блоге: 1
11.12.2017, 16:08 2
задай уравнения луча и сферы параметрически
луч это P=O+t*R где t>=0 P - любая точка на луче, O - начало луча R - вектор направления луча
сфера это (P-C)*(P-C)=r*r где r - скаляр радиуса сферы P любая точка на сферы C - центр сферы
Неизвестное - t
разкладываем луч в систему из трёх уравнений для x y z координат подставляем координаты в уравнение сферы
получаем обычное квадратное ур-е относительно t в итоге находим или 1 или 2 решения t либо не находим решений. Это и будут 1 или 2 или 0 точки пересечения соответственно
0
COKPOWEHEU
1052 / 733 / 173
Регистрация: 09.09.2017
Сообщений: 3,255
11.12.2017, 16:26 3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <math.h>
 
#define F_EPS 1e-4
 
class Vector3{
public:
  float x,y,z;
  Vector3(){}
  Vector3(float _x, float _y, float _z){x=_x; y=_y; z=_z;}
  float len2(){return x*x + y*y + z*z;}
  float len(){return sqrt(len2());}
  void normalize(){float l=sqrt(x*x+y*y+z*z); x/=l; y/=l; z/=l;}
  float operator * (Vector3 arg){return x*arg.x + y*arg.y + z*arg.z;}
  Vector3 operator = (Vector3 src){x=src.x; y=src.y; z=src.z; return *this;}
  Vector3 operator + (Vector3 arg){Vector3 tmp(x+arg.x, y+arg.y, z+arg.z); return tmp;}
  Vector3 operator - (Vector3 arg){Vector3 tmp(x-arg.x, y-arg.y, z-arg.z); return tmp;}
  Vector3 operator * (float l){Vector3 tmp(x*l, y*l, z*l); return tmp;} //scalar multiply
};
 
/*
 * ray_st, ray_dir - start point and direction of the ray
 * sp_cen, sp_rad - center point and radius of the sphere
 * res1, res2 - intersection points (if there is less than 2 intersections - no changes)
 * return value - number of intersections
 */
int find_intersection(Vector3 ray_st, Vector3 ray_dir, Vector3 sp_cen, float sp_rad, Vector3 &res1, Vector3 &res2){
  Vector3 middle; //middle point between intersections
  Vector3 dist; //vector from center of sphere to ray start
  Vector3 dpos; //vector from ray_st to sp_cen
  float len2; //square of distance from center of sphere to ray
  ray_dir.normalize();
  sp_rad *= sp_rad;
  
  dpos = sp_cen - ray_st;
  middle = ray_st + ray_dir*(ray_dir*dpos);
  len2 = (middle - sp_cen).len2();
  
  if(len2 > sp_rad)return 0;
  if(fabs( len2 - sp_rad )<F_EPS){
    res1 = middle;
    return 1;
  }
  len2 = sqrt(sp_rad - len2);
  //now len2 is distance, not its square
  res1 = middle - ray_dir*len2;
  res2 = middle + ray_dir*len2;
  return 2;
}
 
int main(){
  Vector3 r1, r2;
  int num;
  num = find_intersection(Vector3(-1,0,0),Vector3(1,0,0), Vector3(0,0.5,0.5),1, r1, r2);
}
0
Progrmmer69
0 / 0 / 1
Регистрация: 01.12.2016
Сообщений: 19
11.12.2017, 16:33  [ТС] 4
COKPOWEHEU, в задание указано, что требуется сохранить структуру исходного кода.
0
COKPOWEHEU
1052 / 733 / 173
Регистрация: 09.09.2017
Сообщений: 3,255
11.12.2017, 16:43 5
Пусть луч задан началом P и направлением V. Сфера задана центром C и радиусом R. Вектор от начала луча до центра сферы обзовем D = C-P. Точка на прямой, наиболее близкая к центру сферы будет T, расстояние от нее до центра - L, расстояние от нее до точек пересечения X (они симметричны относительно нее). Предлагаю все это нарисовать чтобы было нагляднее.
Все обозначения есть, начинаем вычислять. Для начала допустим что вектор V единичный (или нормальзуем его). Далее вспомним что скалярное произведение векторов это произведение их длин на косинус угла между ними. Но длина вектора D на косинус угла между ним и V это длина его проекции: t = |D|*cos(a) = (D,V). Теперь переведем это в векторную форму, воспользовавшись единичностью вектора V: T=V*(D,V). Эта точка нам еще понадобится. Найдем расстояние от нее до центра сферы: L=T-D. Теперь по теореме Пифагора найдем расстояние от нее до сферы http://www.cyberforum.ru/cgi-bin/latex.cgi?X=\sqrt{R^2 - L^2}. У нас есть точка на луче T+P, направляющий вектор луча и расстояния от найденной точки до сферы. Получаем http://www.cyberforum.ru/cgi-bin/latex.cgi?Y = (T+P)\pm (V\cdot X).
Остаются чисто алгоритмические задачи вроде проверки пересекаются ли они вообще и не лежат ли они за пределами луча (этого я, кстати не делал - лень)

Добавлено через 30 секунд
Progrmmer69, ну так стилизуйте под себя, в чем проблема? Алгоритм я написал, код тоже
0
Kuzia domovenok
2436 / 2143 / 523
Регистрация: 25.03.2012
Сообщений: 7,720
Записей в блоге: 1
11.12.2017, 17:46 6
Лучший ответ Сообщение было отмечено Progrmmer69 как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cmath>
 
using namespace std;
 
static const float Epsilon = 1e-4f;
 
struct Vector3F
{
public:
    float x;
    float y;
    float z;
};
 
struct Intersection
{
public:
    Vector3F p0;
    Vector3F p1;
 
    unsigned char count;
};
inline float operator*(Vector3F p0, Vector3F p1)
{
    return p0.x*p1.x + p0.y*p1.y + p0.z*p1.z;
}
inline Vector3F operator*(Vector3F p0, float t)
{
    p0.x *= t;
    p0.y *= t;
    p0.z *= t;
    return p0;
}
inline Vector3F operator-(Vector3F p0, Vector3F p1)
{
    p0.x -= p1.x;
    p0.y -= p1.y;
    p0.z -= p1.z;
    return p0;
}
 
Intersection  FindIntersection(
    Vector3F rayStart,
    Vector3F rayDirection,
    Vector3F sphereCenter,
    float sphereRadius)
{
    Vector3F delta;
    delta = sphereCenter - rayStart;
 
    float a = rayDirection*rayDirection;
    float half_b = rayDirection*delta*(-1.0f);
    float c = delta*delta - sphereRadius*sphereRadius;
 
    Intersection otvet;
    //assert(fabs(a) > Epsilon);//lineynoye uravneniye //luch raven nulyu ne mozhet
    float Discr = half_b*half_b - a*c;
    if (Discr < -Epsilon) 
    {// 0 korney
        otvet.count = 0;
        return otvet;
    }
    if (Discr > Epsilon)
    {// 2 korney
        otvet.count = 2;
        float minus_t0 = (half_b + sqrt(Discr) )/a;
        float minus_t1 = (half_b - sqrt(Discr) ) / a;
        otvet.p0 = rayStart - rayDirection*minus_t0;
        otvet.p1 = rayStart - rayDirection*minus_t1;
        return otvet;
    }
    {// 1 korney
        otvet.count = 1;
        float minus_t0 = half_b/ a;
        otvet.p0 = rayStart - rayDirection*minus_t0;
        return otvet;
    }
}
 
int main() {
    const Vector3F rayStart{ 0.0f, 0.0f, 4.0f };
    const Vector3F rayDirection{ 0.0f, 0.0f, -1.0f };
 
    const Vector3F sphereCenter{ 0.0f, 0.0f, 0.0f };
    const float sphereRadius = 1.0f;
 
    const Intersection result = FindIntersection(
        rayStart,
        rayDirection,
        sphereCenter,
        sphereRadius);
 
    cout << "Intersection test result: " << endl;
    cout << "P0 = (" << result.p0.x << ", " << result.p0.y << ", " << result.p0.z << ")" << endl;
    cout << "P1 = (" << result.p1.x << ", " << result.p1.y << ", " << result.p1.z << ")" << endl;
    cout << "Count= " << static_cast<unsigned int>(result.count) << endl;
 
    system("pause");
    return 0;
}
Добавлено через 1 минуту
COKPOWEHEU, ты у кого-то код взял. Совсем не похоже на то что у автора. У него структуры - у тебя классы, да ещё и имена классов другие.

Добавлено через 54 минуты
Да, и при решении надо проверять, что t>=0
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
Intersection  FindIntersection(
    Vector3F rayStart,
    Vector3F rayDirection,
    Vector3F sphereCenter,
    float sphereRadius)
{
    Vector3F delta;
    delta = sphereCenter - rayStart;
 
    float a = rayDirection*rayDirection;
    float half_b = rayDirection*delta*(-1.0f);
    float c = delta*delta - sphereRadius*sphereRadius;
 
    Intersection otvet;
    //assert(fabs(a) > Epsilon);//lineynoye uravneniye //luch raven nulyu ne mozhet
    float Discr = half_b*half_b - a*c;
 
    otvet.count = 0;
    if (Discr < -Epsilon) 
    {// 0 korney
        return otvet;
    }
    if (Discr > Epsilon)
    {// 2 korney
        float minus_t = (half_b + sqrt(Discr)) / a;
        if (minus_t < Epsilon){
            ++otvet.count;
            otvet.p0 = rayStart - rayDirection*minus_t;
        }
        minus_t = (half_b - sqrt(Discr) ) / a;
        if (minus_t < Epsilon) {
            ++otvet.count;
            otvet.p1 = rayStart - rayDirection*minus_t;
        }
        return otvet;
    }
    {// 1 korney
        float minus_t = half_b / a;
        if (minus_t < Epsilon) {
            ++otvet.count;
            otvet.p0 = rayStart - rayDirection*minus_t;
        }
        return otvet;
    }
}
1
COKPOWEHEU
1052 / 733 / 173
Регистрация: 09.09.2017
Сообщений: 3,255
11.12.2017, 20:05 7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
COKPOWEHEU, ты у кого-то код взял. Совсем не похоже на то что у автора. У него структуры - у тебя классы, да ещё и имена классов другие.
Неа, я его сам писал, как мне удобнее и привычнее.
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Да, и при решении надо проверять, что t>=0
Это я описал словами. Надо же и ТСу оставить пищу для размышлений.
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Остаются чисто алгоритмические задачи вроде проверки пересекаются ли они вообще и не лежат ли они за пределами луча (этого я, кстати не делал - лень)
0
Kuzia domovenok
2436 / 2143 / 523
Регистрация: 25.03.2012
Сообщений: 7,720
Записей в блоге: 1
11.12.2017, 21:04 8
Цитата Сообщение от COKPOWEHEU Посмотреть сообщение
Это я описал словами. Надо же и ТСу оставить пищу для размышлений.
это не тебе в упрёк, ты же видишь, что я в первый раз ошибся.
0
11.12.2017, 21:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2017, 21:04

Вычислительная геометрия (Даны координаты центра, R окружности, координаты точки вне окруж-ти. Найти точку пересечения одной из касательных с окруж-ю)
Даны координаты центра (xc,yc) и радиус R окружности, координаты точки (x,y)...

Найти точки пересечения прямых проходящих через заданные точки
Всем привет! Прошу помощи в решении задачи: Дана система координат X:Y (по 25...

Найти координаты точек пересечения прямой y=kx+b и окружности
Найти координаты точек пересечения прямой y=kx+b и окружности радиуса R с...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru