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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Daber
0 / 0 / 0
Регистрация: 15.03.2013
Сообщений: 43
#1

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

04.05.2013, 01:15. Просмотров 464. Ответов 5
Метки нет (Все метки)

написать функцию: даны координаты 20 точек ломаной, найти три круга, которые находятся дальше от нее и три ближайших окружности. есть координаты центров окружностей и их радиус, количество кругов неопределенная, но больше 7. ломаная задана объектами класса линия окружности являются объектами класса окружность
это все условие, поэтому алгоритм поиска не определен
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.05.2013, 01:15     расстояние от окружности к ломаной?
Посмотрите здесь:

Определить расстояние от данной точки до ломаной - C++
Есть задача. Вот ее краткий пересказ. На плосткости дана точка с координатами x и у. Дано n. На плоскости дано n точек, попарно...

Определить функцию, возвращающую расстояние между центром окружности и началом координат - C++
Разработать класс Point для задания координаты точки на плоскости. Выбирая этот класс в качестве базового, разработать производный класс...

По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения окружности с осями координат. - C++
По заданным координатам центра окружности и ее радиусу определить координаты точек пересечения окружности с осями координат.

Длина Ломаной - C++
Помогите пожалуйста написать программку, вот задание : ломаная задана координатами своих вершин.Найти ее длину.Использовать функцию для...

Класс ломаной линии - C++
Разработать класс ломанной линии CZigzagLine.В классе CZigzagLine линия должнабыть описана совокупностью координат точек на...

Задача нахождения длины ломаной - C++
Условие: Ввод из: Стандартный ввод Время выполнения на одном тесте: 1 с Вывод в: Стандартный вывод Ограничение памяти программы на...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
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
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
06.05.2013, 00:44     расстояние от окружности к ломаной? #5
Цитата Сообщение от Daber Посмотреть сообщение
Плохо знаю потоки
Цитата Сообщение от В.Высоцкий
И оборвали крик мой,
И обожгли мне щеки
Холодной острой бритвой
Восходящие потоки.
Какие еще потоки!? У меня все в одном потоке.

Цитата Сообщение от Daber Посмотреть сообщение
можно ли реализовать как-то по-другому?
Разумеется, меняйте реализацию по вашему усмотрению. Я совершенно не против, для вас и писал.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.05.2013, 03:45     расстояние от окружности к ломаной?
Еще ссылки по теме:

Найти длину кратчайшей ломаной - C++
Даны координаты N точек на плоскости. Найти длину кратчайшей ломаной, соединяющей эти точки. совсем нет идей как это сделать, приходит...

Определить длину ломаной по координатам - C++
Здравствуйте. Проблема с решением задачи &quot;Ловушки&quot;. Алгоритм ясен, ломаная образует многоугольник, начальная и конечная вершина...

Создать класс и вычислить длину ломаной линии - C++
Создать класс linXY - ломаная линия, принадлежащая первому квадранту плоскости. Функция-член класса: вычисление длины ломаной линии....

Класс "Окружность" с данными центр и радиус окружности. Вычислить длину и площадь окружности. - C++
Объявить класс и определить для него конструктор по умолчанию, конструктор инициализации. Определить функции-члены класса для ввода и...

Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если автомобили пе - C++
Скорость первого автомобиля V1 км/ч, второго — V2 км/ч, расстояние между ними S км. Определить расстояние между ними через T часов, если...

Массив: Соединить точки замкнутой самонепересекающейся ломаной так, чтобы периметр полученного многоугольника был минимальным - C++
Здравствуйте!! Такая проблема, не могу придумать алгоритм для решения следующей задачи, прощу подскажите, у кого есть какие идеи: В...


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

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

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