Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
~Nataly~
0 / 0 / 0
Регистрация: 12.08.2009
Сообщений: 16
#1

Найти близколежащие точки на плоскости - C++

17.09.2009, 16:52. Просмотров 974. Ответов 12
Метки нет (Все метки)

Уважаемые программисты, прошу помощи с такой задачей:
Имеется файл "test.search.txt". В нём разнообразные данные наблюдений, которые характеризуют объект. У каждого объекта свои координаты X и Y.
Чтобы было понятней: у первого объекта X=21.325405015, а Y=16.139773998.
Также и у остальных объектов на тех же позициях находятся их координаты.
Целью задания является вывести файл, в котором останутся только те объекты, у которых диапазон координат различается на 0.0001, как абцисах, так и ординатах. При этом объектов может быть либо несколько, либо ни одного.
Вот помогите с такой задачкой. Если что-то необходимо уточнить. то походу дела уточню.
0
Вложения
Тип файла: zip test.search.txt.zip (21.9 Кб, 17 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.09.2009, 16:52
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти близколежащие точки на плоскости (C++):

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

Дано множество точек на плоскости. Необходимо найти 4 точки (с максимальными и минимальными значениями x и y) - C++
Собственно, как я понял здесь нужна структура и динамический массив. но как это реализовать, я не знаю. Подскажите пожалуйста хотя бы как...

найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) - C++
Помогите, пожалуйста, написать программу на С++, используя структуру point для хранения координат точки: следует найти две наиболее...

Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри - C++
"Даны N точек на плоскости. Найти среди них точки являющиеся вершинами фигуры, содержащей максимальное число заданных точек. Фигура -...

точки на плоскости - C++
очень срочно нужно задачки для зачета(С#)... Задача1: Найти такую точку заданного на плоскости множества точек,сумма расстояний от...

Точки на плоскости - C++
Заданы две точки на плоскости. Определить лежат ли они одновременно на осях координат.

12
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
17.09.2009, 21:16 #2
останутся только те объекты, у которых диапазон координат различается на 0.0001, как абцисах, так и ординатах. При этом объектов может быть либо несколько, либо ни одного.
Условия непонятно описаны.
1)
Пусть есть всего две точки (x1,y1), (x2,y2).
Значит если fabs(x1-x2) == 0.0001 == fabs(y1-y2) тогда берем ?
А в остальных случаях не берем ?
Или нужно чтобы было <= ?

2)
Непонятно что делать когда точек больше двух.
Мы должны сравнивать все точки попарно и все пары должны удовлетворять условию ?
Или достаточно чтобы хотя бы одна пара попадала в условие ?
В этом случае может быть на плоскости несколько кластеров вокруг нескольких центров.
Или нужно чтобы такой центр был один - и все точки были близки от точек этого кластера ?
Или имеется в виду, что все точки должны быть близки от одной точки ?

Добавлено через 19 минут
Для начала написал парсер файла -
код

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
/* Thread 51290 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
/********************************************************************/
#define INPUT_NAME  "test.search.txt"
 
 
/********************************************************************/
int parse_x_y( const char *buf, int buf_size, double *px, double *py );
 
 
/********************************************************************/
int main( void ) {
 
double x,y;
 
int buf_size;
char buf[1024];
FILE *fin= NULL;
 
 
fin= fopen( INPUT_NAME, "r" );
if ( fin == NULL ) {
    fprintf( stderr, "Error opening file %s\n", INPUT_NAME );
    exit( 1 );
}
 
for ( ; ; ) {
    
    /* Read line */
    if ( fgets( buf, sizeof(buf), fin ) == NULL ) {
        if ( feof( fin ) ) { break; }
        fprintf( stderr, "Error reading file\n" );
        exit( 1 );
    }
    buf_size= strlen( buf );
    if ( buf_size>0 && buf[buf_size-1] == '\n' ) { buf[--buf_size]= '\0'; }
 
    /* Parse line */
    if ( parse_x_y( buf, buf_size, &x, &y ) ) {
        fprintf( stderr, "Invalid format in file\n" );
        exit( 1 );
    }
    
    /* Print */
    printf( "%.10f %.10f\n", x, y );
 
}
 
fclose( fin ); fin= NULL;
 
return 0;
 
} /* main() */
 
 
/********************************************************************/
int parse_x_y( const char *buf, int buf_size, double *px, double *py ) {
 
char *endptr;
 
 
/* Check line */    
if ( buf_size != 408 ) { return 1; }
 
*px= strtod( &buf[238], &endptr );
if ( *px == 0.0 ) {
    if ( &buf[238] == endptr ) { return 1; }
}
 
*py= strtod( &buf[252], &endptr );
if ( *py == 0.0 ) {
    if ( &buf[252] == endptr ) { return 1; }
}
 
return 0;
 
} /* parse_x_y() */
1
~Nataly~
0 / 0 / 0
Регистрация: 12.08.2009
Сообщений: 16
18.09.2009, 10:18  [ТС] #3
Да, Вы правильно заметили по-поводу первого условия, необходимо так Вы указали.
Что касается второго, то тут мы должны сравнить все точки попарно и все пары должны удовлетворять условию.
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
18.09.2009, 16:52 #4
Это вообще задача или реальное задание ?
Я что-то сильно сомневаюсь что все пары попарно должны удовлетворять условию (1).
Потому что тогда очевидно что это будет просто две точки, которые расположены строго по диагонали.
Если взять три точки A,B,C. при этом от A до B сдвиг по 0.0001
И от B до C тоже сдвиг по 0.0001.
Тогда у нас получится чтобы между A и C был тоже сдвиг по 0.0001 - у нас так не получится никогда.
Либо может быть вариант что С совпадает с A например.
Так что какое-то задание глупое и решать его не хочется
Я думаю просто условие неправильное или неправильно трактуется.

Добавлено через 2 минуты
Возможно тут надо найти не все точки, а только две точки, но перебирая их все попарно.
Например есть A1,A2,A3,A4,A5,A6.
A1 и A2 удовлетворяют условию (1).
A3 и A4 удовлетворяют условию (1).
Остальные пары Ai и Aj не удовлетворяют.
В результате работы программы мы должны вывести пары:
A1 A2
A3 A4

Тогда еще задача имеет какой-то смысл.
0
novi4ok
551 / 504 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
18.09.2009, 20:29 #5
"близколежащие" - это несколько не те, которые имеют различие в абсциссе и ординате не более чего-то (давайте возьмем для примера единицу. просто чтоб нули после запятой не подсчитывать).

если формулировать задачу так как вы это делаете, то пара точек с координатами (0,0) и (0.99, 0.99) окажется "близкой" парой, в то же время пара (0,0) и (0, 1.1) - нет. не смотря на то, что точки второй пары ближе к друг другу, чем точки первой.

может задача должна быть сформулирована так:

отобрать все объекты, которые имеют в радиусе R еще хотя бы один другой объект. (?)
0
~Nataly~
0 / 0 / 0
Регистрация: 12.08.2009
Сообщений: 16
22.09.2009, 16:08  [ТС] #6
Цитата Сообщение от odip Посмотреть сообщение
Возможно тут надо найти не все точки, а только две точки, но перебирая их все попарно.
Например есть A1,A2,A3,A4,A5,A6.
A1 и A2 удовлетворяют условию (1).
A3 и A4 удовлетворяют условию (1).
Остальные пары Ai и Aj не удовлетворяют.
В результате работы программы мы должны вывести пары:
A1 A2
A3 A4

Тогда еще задача имеет какой-то смысл.
Пару дней меня небыло, инет пропал(( прошу прощения.
В общем уточнила я по-поводу этого задания, вот как Вы тут описали, примерно так и надо. Только точек может быть кпримеру не только 2, а и более.
Например А1,А2,А7,А8 удовлетворяют условию
А3,А4,А5 удовлетворяют
А5 и А6 удовлетворяют.
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
22.09.2009, 16:58 #7
Все равно ничего не понятно.
Что значит точки A1,A2,A7,A8 удовлетворяют условию (1) ?
Условие (1) относится к ровно двум точкам !
Вопрос был - что значит условие выполняется для 3,4,...,N точек ?
А еще лучше - привести пример из нескольких конкретных координат точек и написать какой будет ответ, чтобы совсем было точно !
Вообщем задача решается быстрее, чем удается узнать условие
0
~Nataly~
0 / 0 / 0
Регистрация: 12.08.2009
Сообщений: 16
03.10.2009, 15:47  [ТС] #8
Ну вот приведу такой пример:
значит есть к примеру точки с координатами
A (5.262737 ; 9.356948)
B (5.847205 ; 8.047849)
C (5.262772 ; 9.356861)
D (4.918046 ; 9.168293)
E (5.828826 ; 9.153901)
F (5.828873 ; 9.153989)
Вот исходя из этого видно , что у А и С координаты Х и Y имеют необходимый диапазон различия в 0.0001, также это же неблаюдаем у точек E и F , т.е. они, точки A, B, E, F должны остаться в выводном файле,а остальные отфильтроваться. Таких точек, как А и C, может быть не только 2, а и болеек примеру 3,4,5 и тп.
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
03.10.2009, 16:30 #9
А теперь внимательно смотрим на A и C.
5.262772-5.262737=0.000035
9.356948-9.356861=0.000087

Разница между ними не равна 0.0001
Почему мы взяли эти точки ?

Добавлено через 1 минуту
2~Nataly~: Если нет времени объяснить условие, то может вообще закроем эту тему ?
0
~Nataly~
0 / 0 / 0
Регистрация: 12.08.2009
Сообщений: 16
03.10.2009, 17:16  [ТС] #10
Разница не равна, а вот диапазон различия идет не более 0.0001, т.е. удовлетворяет условию, нам так и надо. Если диапазон был бы больше, то уже б не подходило.
Обе координаты у точек удовлетворяют условию диапазона не боле 0.0001, следовательно подходят.
Дело в том, что в том документе, что я выкладывала в 1ом посте точки передвигаются, и вот необходимо мне уловить этот диапазон.
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
03.10.2009, 17:39 #11
Ну вот теперь стало ясно условие задачи.
Задача простая.
Нужно загрузить файл в память по-строчно.
Сравнить все точки между собой, это будет O(N*N).
Пары точек пометить.
Потом вывести только те строки, которые были помечены.
0
~Nataly~
0 / 0 / 0
Регистрация: 12.08.2009
Сообщений: 16
03.10.2009, 18:36  [ТС] #12
Могу попросить о примерном наброске когда у Вас будет время?
0
odip
Эксперт С++
7159 / 3221 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
11.10.2009, 16:15 #13
Программа

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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
/* Thread 51290 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
 
 
/********************************************************************/
#define MAX_LINE_SIZE       1024
#define LINES_DEF_SIZE      256
#define MAX_DIFF            0.0001
 
 
/********************************************************************/
typedef struct {
    double x, y;
    int flag;
} point_flag_t;
 
typedef struct {
    int size, max_size;
    char **lines;
} objects_t;
 
#define objects_size(arg_pobj)          ((arg_pobj)->size)
#define objects_line(arg_pobj,arg_i)    ((arg_pobj)->lines[(arg_i)])
 
 
/********************************************************************/
void do_process( const char *in_name, const char *out_name );
 
int read_objects_file( objects_t *pobj, const char *name );
void free_objects( objects_t *pobj );
 
int parse_x_y( const char *buf, double *px, double *py );
 
 
/********************************************************************/
int main( int argc, char *argv[] ) {
 
argc--; argv++;
 
if ( argc != 2 ) {
    fprintf( stderr, "Usage: search in.txt out.txt" );
    exit( 2 ) ;
}
 
do_process( argv[0], argv[1] );
return 0;
 
} /* main() */
 
 
/********************************************************************/
void do_process( const char *in_name, const char *out_name ) {
 
int i, j;
int errcode;
 
int line_size;
char *line;
 
int obj_size;
objects_t obj;
 
double x, y;
point_flag_t *ppoint= NULL;
FILE *fout= NULL;
 
 
/* Read */
if ( read_objects_file( &obj, in_name ) ) { goto err_read; }
 
/* Check */
obj_size= objects_size( &obj );
if ( obj_size == 0 ) { goto err_no_obj; }
 
/* Allocate points */
ppoint= (point_flag_t*)malloc( obj_size*sizeof(point_flag_t) );
if ( ppoint == NULL ) { goto err_nomem; }
 
/* Parse x,y and setup point */
for ( i= 0; i<obj_size; i++ ) {
    if ( parse_x_y( objects_line( &obj, i ), &x, &y ) ) { goto err_format; }
    ppoint[i].x= x; ppoint[i].y= y;
    ppoint[i].flag= 0;
}
 
/* Compare loop */
for ( i= 0; i<obj_size; i++ ) {
    for ( j= i+1; j<obj_size; j++ ) {
        if ( fabs( ppoint[i].x-ppoint[j].x )<=MAX_DIFF &&
            fabs( ppoint[i].y-ppoint[j].y )<=MAX_DIFF ) {
            ppoint[i].flag= ppoint[j].flag= 1;
            /* printf( "near %d %d\n", i, j ); */
            break;
        }
    }
}
 
/* Create out */
fout= fopen( out_name, "wb" );
if ( fout == NULL ) { goto err_create; }
 
/* Write out loop */
for ( i= 0; i<obj_size; i++ ) {
    if ( !ppoint[i].flag ) { continue; }
 
    line= objects_line( &obj, i );
    line_size= strlen( line );
    errcode= fprintf( fout, "%s\n", line );
    if ( line_size+1 != errcode ) { goto err_write; }
 
}
 
/* Close out */
if ( fclose( fout ) ) { goto err_close; }
fout= NULL;
 
/* Free ppoint */
free( ppoint ); ppoint= NULL;
 
return;
 
 
/* Processing errors */
err_read:
fprintf( stderr, "Error reading file\n" );
goto err_all;
 
err_no_obj:
fprintf( stderr, "No objects\n" );
goto err_all;
 
err_nomem:
fprintf( stderr, "No memory\n" );
goto err_all;
 
err_format:
fprintf( stderr, "Invalid format\n" );
goto err_all;
 
err_create:
fprintf( stderr, "Error creating file\n" );
goto err_all;
 
err_write:
fprintf( stderr, "Error writing file\n" );
goto err_all;
 
err_close:
fprintf( stderr, "Error closing file\n" );
goto err_all;
 
err_all:
exit( 1 );
 
} /* do_process() */
 
 
/********************************************************************/
int read_objects_file( objects_t *pobj, const char *name ) {
 
int buf_size, max_size;
char buf[MAX_LINE_SIZE], *line, **lines;
FILE *fin= NULL;
 
 
/* Init */
pobj->size= 0; pobj->max_size= 0;
pobj->lines= NULL;
 
/* Open */
fin= fopen( name, "r" );
if ( fin == NULL ) { goto err_read; }
 
/* Loop */
for ( ; ; ) {
    
    /* Read line */
    if ( fgets( buf, sizeof(buf), fin ) == NULL ) {
        if ( feof( fin ) ) { break; }
        goto err_read;
    }
    buf_size= strlen( buf );
    if ( buf_size>0 && buf[buf_size-1] == '\n' ) { buf[--buf_size]= '\0'; }
 
    /* Check space and realloc */
    if ( pobj->size >= pobj->max_size ) {
 
        max_size= (pobj->max_size!=0) ? 2*pobj->max_size : LINES_DEF_SIZE;
        lines= (char**)realloc( pobj->lines, max_size*sizeof(char*) );
        if ( lines == NULL ) { goto err_nomem; }
            
        pobj->max_size= max_size; pobj->lines= lines;
 
    }
    
    /* Store */
    line= malloc( buf_size+1 );
    if ( line == NULL ) { goto err_nomem; }
    memcpy( line, buf, buf_size+1 );
    pobj->lines[pobj->size]= line; pobj->size++;
 
}
 
/* Close */
if ( fclose( fin ) ) { goto err_close; }
fin= NULL;
 
/* Return */
return 0;
 
 
/* Processing errors */
err_read:
err_close:
err_nomem:
return 1;
 
} /* read_objects_file() */
 
 
/********************************************************************/
void free_objects( objects_t *pobj ) {
 
int i;
 
 
for ( i= 0; i<pobj->size; i++ ) {
    if ( pobj->lines[i] != NULL ) { free( pobj->lines[i] ); }
}
free( pobj->lines );
 
pobj->size= pobj->max_size= 0;
pobj->lines= NULL;
    
} /* free_objects() */
 
 
/********************************************************************/
int parse_x_y( const char *buf, double *px, double *py ) {
 
int buf_size;
char *endptr;
 
 
/* Check line */    
buf_size= strlen( buf );
if ( buf_size != 408 ) { return 1; }
 
*px= strtod( &buf[238], &endptr );
if ( *px == 0.0 ) {
    if ( &buf[238] == endptr ) { return 1; }
}
 
*py= strtod( &buf[252], &endptr );
if ( *py == 0.0 ) {
    if ( &buf[252] == endptr ) { return 1; }
}
 
return 0;
 
} /* parse_x_y() */


Результат работы на приведенном файле
Код
 1398.85  294.67 1.155     71.11    263.93 20.494 20.177 99.999 21.735 21.418 99.999 99.999 99.999  0.619  0.940 99.999 99.999 99.999  99.999  99.999  99.999  99.999  0.009  0.007  0.181  0.164  0.109  0.099   36   32 99.999 99.999   99  21.326773432  16.125337796  9  1 22.21 2008  7 31 2454678.87595153   130  g.MP9401              /home/Obs/cfht/1013384p_10.fits           2006 SX368            2112  4644
 1397.33  296.11 1.857    137.01    195.64 20.494 20.177 99.999 21.022 20.706 99.999 99.999 99.999  0.619  0.940 99.999 99.999 99.999  99.999  99.999  99.999  99.999  0.027  0.031  0.181  0.164  0.109  0.099   36   32 99.999 99.999   99  21.326768067  16.125264613  9  1 22.21 2008  7 31 2454678.87595153   130  g.MP9401              /home/Obs/cfht/1013384p_10.fits           2006 SX368            2112  4644
  250.06 1732.64 1.096     68.64    315.09 20.494 20.177 99.999 21.773 21.456 99.999 99.999 99.999  0.619  0.940 99.999 99.999 99.999  99.999  99.999  99.999  99.999  0.004  0.004  0.074  0.067  0.109  0.099   36   32 99.999 99.999   99  21.322697056  16.051438964  9  1 22.21 2008  7 31 2454678.87595153   130  g.MP9401              /home/Obs/cfht/1013384p_10.fits           2006 SX368            2112  4644
  261.39 1731.96 1.999    371.65     16.25 20.494 20.177 99.999 19.939 19.622 99.999 99.999 99.999  0.619  0.940 99.999 99.999 99.999  99.999  99.999  99.999  99.999  0.035  0.045  0.071  0.064  0.109  0.099   36   32 99.999 99.999   99  21.322737559  16.051472168  9  1 22.21 2008  7 31 2454678.87595153   130  g.MP9401              /home/Obs/cfht/1013384p_10.fits           2006 SX368            2112  4644
1
11.10.2009, 16:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.10.2009, 16:15
Привет! Вот еще темы с ответами:

Точки на плоскости. - C++
Заданы три точки на плоскости: M с координатами (x1,y1), L с координатами (x2,y2) и H с координатами (x3,y3). Определите, лежат ли они на...

Точки на плоскости - C++
Здравствуйте, как зная координаты четырех точек определить расположены они на одной плоскости или нет?

Координаты точки на плоскости - C++
Помогите пожалуйста с задачей Даны целочисленные координаты точки на плоскости. Если точка совпадает с началом координат, то вывести 0....

структура точки в плоскости - C++
создать структуру для работы с точками на плоскости. необходимо определить следующее 1)создать точку по координатам 2)вывод точки в...


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

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

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