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

@Progrmmer69 · Регистрация: 01.12.2016

Студворк — интернет-сервис помощи студентам

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;
}

@Kuzia domovenok · 11.12.2017, 16:08

задай уравнения луча и сферы параметрически
луч это 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 точки пересечения соответственно

@COKPOWEHEU · 11.12.2017, 16:26

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);
}

@Progrmmer69 · 11.12.2017, 16:33 **[ТС]**

COKPOWEHEU, в задание указано, что требуется сохранить структуру исходного кода.

@COKPOWEHEU · 11.12.2017, 16:43

Пусть луч задан началом 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. Теперь по теореме Пифагора найдем расстояние от нее до сферы $https://www.cyberforum.ru/cgi-bin/latex.cgi?X=\sqrt{R^2 - L^2}$ . У нас есть точка на луче T+P, направляющий вектор луча и расстояния от найденной точки до сферы. Получаем $https://www.cyberforum.ru/cgi-bin/latex.cgi?Y = (T+P)\pm (V\cdot X)$ .
Остаются чисто алгоритмические задачи вроде проверки пересекаются ли они вообще и не лежат ли они за пределами луча (этого я, кстати не делал - лень)

Добавлено через 30 секунд
Progrmmer69, ну так стилизуйте под себя, в чем проблема? Алгоритм я написал, код тоже

@Kuzia domovenok · 11.12.2017, 17:46

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;
    }
}

@COKPOWEHEU · 11.12.2017, 20:05

Сообщение от Kuzia domovenok

COKPOWEHEU, ты у кого-то код взял. Совсем не похоже на то что у автора. У него структуры - у тебя классы, да ещё и имена классов другие.

Неа, я его сам писал, как мне удобнее и привычнее.

Сообщение от Kuzia domovenok

Да, и при решении надо проверять, что t>=0

Это я описал словами. Надо же и ТСу оставить пищу для размышлений.

Сообщение от COKPOWEHEU

Остаются чисто алгоритмические задачи вроде проверки пересекаются ли они вообще и не лежат ли они за пределами луча (этого я, кстати не делал - лень)

@Kuzia domovenok · 11.12.2017, 21:04

Сообщение от COKPOWEHEU

Это я описал словами. Надо же и ТСу оставить пищу для размышлений.

это не тебе в упрёк, ты же видишь, что я в первый раз ошибся.

Новые блоги и статьи Все статьи Все блоги /
wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .

@Kuzia domovenok 4268 / 3327 / 926 Регистрация: 25.03.2012 Сообщений: 12,536 Записей в блоге: 1
	11.12.2017, 16:08
	задай уравнения луча и сферы параметрически луч это P=O+tR где 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

@Progrmmer69 3 / 3 / 1 Регистрация: 01.12.2016 Сообщений: 19
	11.12.2017, 16:33 [ТС]
	COKPOWEHEU, в задание указано, что требуется сохранить структуру исходного кода. 0

@COKPOWEHEU 4083 / 2681 / 432 Регистрация: 09.09.2017 Сообщений: 11,929
	11.12.2017, 16:43
	Пусть луч задан началом 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`. Теперь по теореме Пифагора найдем расстояние от нее до сферы $https://www.cyberforum.ru/cgi-bin/latex.cgi?X=\sqrt{R^2 - L^2}$ . У нас есть точка на луче `T+P`, направляющий вектор луча и расстояния от найденной точки до сферы. Получаем $https://www.cyberforum.ru/cgi-bin/latex.cgi?Y = (T+P)\pm (V\cdot X)$ . Остаются чисто алгоритмические задачи вроде проверки пересекаются ли они вообще и не лежат ли они за пределами луча (этого я, кстати не делал - лень) Добавлено через 30 секунд Progrmmer69, ну так стилизуйте под себя, в чем проблема? Алгоритм я написал, код тоже 1

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

Решение