Форум программистов, компьютерный форум CyberForum.ru

расстояние от окружности к ломаной? - C++

Восстановить пароль Регистрация
 
Daber
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 43
04.05.2013, 01:15     расстояние от окружности к ломаной? #1
написать функцию: даны координаты 20 точек ломаной, найти три круга, которые находятся дальше от нее и три ближайших окружности. есть координаты центров окружностей и их радиус, количество кругов неопределенная, но больше 7. ломаная задана объектами класса линия окружности являются объектами класса окружность
это все условие, поэтому алгоритм поиска не определен
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
IrineK
Заблокирован
04.05.2013, 10:01     расстояние от окружности к ломаной? #2
Необходимо искать расстояния от окружностей до отрезков и сравнивать.

Расстояние от окружности до отрезка:
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
//distance from circle to section
 
#include <iostream>
#include <cmath>
using namespace std;
 
double length   (double X1, double Y1, double X2, double Y2)
{   return sqrt((X2-X1)*(X2-X1) + (Y2-Y1)*(Y2-Y1));
}
 
double distance (   double X1, double Y1, double X2, double Y2,
                    double XC, double YC, double R)
{   double vX = X2-X1;
    double vY = Y2-Y1;
    double wX = XC-X1;
    double wY = YC-Y1;
 
    double c1 = wX*vX + wY*vY;
    double c2 = vX*vX + vY*vY;
 
    if(c1<=0)
        return length(XC,YC,X1,Y1) - R;
    if(c2 <= c1)
        return length(XC,YC,X2,Y2) - R;
 
    double b = c1/c2;
    double Xb = X1+b*vX;
    double Yb = Y1+b*vY;
    return length(XC,YC,Xb,Yb) - R;
}
 
 
int main()
{   double X1,Y1,X2,Y2,XC,YC,R;
    cout<<"X1 Y1 X2 Y2:\t";
    cin>>X1>>Y1>>X2>>Y2;
    cout<<"XC YC R: \t";
    cin>>XC>>YC>>R;
 
    cout<<distance( X1,Y1,X2,Y2,XC,YC,R)<<"\n";
    
    cin.sync(); cin.get();
    return 0;
}
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
04.05.2013, 12:33     расстояние от окружности к ломаной? #3
Цитата Сообщение от IrineK Посмотреть сообщение
double distance ( * double X1, double Y1, double X2, double Y2,
* * * * * * * * * * double XC, double YC, double R)
{ * double vX = X2-X1;
* * double vY = Y2-Y1;
* * double wX = XC-X1;
* * double wY = YC-Y1;
double c1 = wX*vX + wY*vY;
* * double c2 = vX*vX + vY*vY;
if(c1<=0)
* * * * return length(XC,YC,X1,Y1) - R;
* * if(c2 <= c1)
* * * * return length(XC,YC,X2,Y2) - R;
double b = c1/c2;
* * double Xb = X1+b*vX;
* * double Yb = Y1+b*vY;
* * return length(XC,YC,Xb,Yb) - R;
}
Что-то я не понимаю алгоритма. Поясните, если вас не затруднит?
Конкретно интересует геометрический смысл производимых вычислений.


Лень мне делать все, но основные моменты я набросал. Расстояние от точки до отрезка считается более примитивным способом.
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <iomanip>
 
class Point {
 public:
  Point() : x(0), y(0), z(0) {}
  Point(double x, double y, double z) : x(x), y(y), z(z) {}
  Point(double x, double y) : x(x), y(y), z(0) {}
  double getX() const { return x; }
  double getY() const { return y; }
  double getZ() const { return z; }
 private:
  double x, y, z;
};
 
class Segment {
 public:
  Segment() : a(), b() {}
  Segment(const Point &a, const Point &b) : a(a), b(b) {}
  const Point &getA() const { return a; }
  const Point &getB() const { return b; }
 private:
  Point a, b;
};
 
class Circle {
 public:
  Circle() : center(), radius(0) {}
  Circle(const Point &center, double radius) : center(center), radius(radius) {}
  double getRadius() const { return radius; }
  const Point &getCenter() const { return center; }
 private:
  Point center;
  double radius;
};
 
std::ostream &operator<<(std::ostream &stream, const Point &p) {
  return stream << "Point{" << 
    std::fixed << std::setprecision(2) <<
    "x=" << p.getX() << "," <<
    "y=" << p.getY() << "," <<
    "z=" << p.getZ() << "}";
}
 
std::ostream &operator<<(std::ostream &stream, const Segment &s) {
  return stream << "Segment{" << 
    "a=" << s.getA() << "," <<
    "b=" << s.getB() << "}";
}
 
std::ostream &operator<<(std::ostream &stream, const Circle &c) {
  return stream << "Circle{" <<
    "center=" << c.getCenter() << "," <<
    std::fixed << std::setprecision(2) <<
    "radius=" << c.getRadius() << "}";
}
 
double getDistanceSquare(const Point &a, const Point &b) {
  return pow(a.getX() - b.getX(), 2.0) + pow(a.getY() - b.getY(), 2.0) +
    pow(a.getZ() - b.getZ(), 2.0);
}
 
// по формуле, площадь треугольника = основание * высота / 2
double getDistance(const Segment &segment, const Point &point) {
  double a = getDistanceSquare(segment.getA(), point);
  double b = getDistanceSquare(segment.getB(), point);
  double c = getDistanceSquare(segment.getA(), segment.getB());
 
  // по квадрату расстояний определяется, тупой ли угол
  // если тупой, то искомое расстояние есть меньшая сторона теугольника
  if (a >= b + c) return sqrt(b);
  if (b >= a + c) return sqrt(a);
 
  a = sqrt(a);
  b = sqrt(b);
  c = sqrt(c);
 
  // полупериметр
  double p = (a + b + c) / 2;
  double square = sqrt((p - a) * (p - b) * (p - c) * p);
  
  // высота
  return square * 2 / c;
};
 
double getDistance(const Segment &segment, const Circle &circle) {
  return getDistance(segment, circle.getCenter()) - circle.getRadius();
}
 
Point getRandomPoint() {
  return Point((rand() % 10000) / 100., (rand() % 10000) / 100., 0);
}
 
Circle getRandomCircle() {
  return Circle(getRandomPoint(), (rand() % 1000) / 100.);
}
 
// расстояние от ломаной до окружности
double getDistance(Point *first, Point *last, const Circle &circle) {
  double distance = getDistance(Segment(*first, *(first + 1)), circle);
  ++first;
  --last;
  while (first != last) {
    double thisDistance = getDistance(Segment(*first, *(first + 1)), circle);
    if (thisDistance < distance) {
      distance = thisDistance;
    }
    ++first;
  }
  return distance;
}
 
int main(int argc, char *argv[]) {
  srand(time(0));
 
  int numberOfPoints = 20;
  Point *polyline = new Point[numberOfPoints];
  
  // собирается ломаная и одновремено выводится на экран
  for (int i = 0; i < numberOfPoints; ++i) {
    std::cout << (polyline[i] = getRandomPoint());
    if (i < numberOfPoints - 1) {
      std::cout << ",";
    }
  }
  std::cout << std::endl;
 
  int numberOfCircles = 8 + rand() % 5;
  Circle *circles = new Circle[numberOfCircles];
 
  // создаются окружности и одновремено выводятся на экран
  for (int i = 0; i < numberOfCircles; ++i) {
    std::cout << (circles[i] = getRandomCircle());
    if (i < numberOfCircles - 1) {
      std::cout << ",";
    }
  }
  std::cout << std::endl;
 
  // расстояние от точки до ломаной
  std::cout << getDistance(polyline, polyline + numberOfPoints, circles[0]) << std::endl;
}
Осталось отсортировать список окружностей в соответствии с расстоянием до ломаной. Можно сделать доп. массив расстояний и рассортировать в соответствии с ним, можно напрямую, каждый раз вычисляя расстояния.
Daber
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 43
06.05.2013, 00:38  [ТС]     расстояние от окружности к ломаной? #4
Добавлено через 1 минуту
Цитата Сообщение от lemegeton Посмотреть сообщение
Лень мне делать все, но основные моменты я набросал. Расстояние от точки до отрезка считается более примитивным способом.
Плохо знаю потоки, можно ли реализовать как-то по-другому? Спасибо
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
06.05.2013, 00:44     расстояние от окружности к ломаной? #5
Цитата Сообщение от Daber Посмотреть сообщение
Плохо знаю потоки
Цитата Сообщение от В.Высоцкий
И оборвали крик мой,
И обожгли мне щеки
Холодной острой бритвой
Восходящие потоки.
Какие еще потоки!? У меня все в одном потоке.

Цитата Сообщение от Daber Посмотреть сообщение
можно ли реализовать как-то по-другому?
Разумеется, меняйте реализацию по вашему усмотрению. Я совершенно не против, для вас и писал.
Daber
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 43
06.05.2013, 03:45  [ТС]     расстояние от окружности к ломаной? #6
Цитата Сообщение от lemegeton Посмотреть сообщение
Разумеется, меняйте реализацию по вашему усмотрению. Я совершенно не против, для вас и писал.
Попробую сам разобраться, спасибо
Yandex
Объявления
06.05.2013, 03:45     расстояние от окружности к ломаной?
Ответ Создать тему
Опции темы

Текущее время: 10:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru