Нужно отсечь все пересекающиеся окружности. Тривиальнейшая задача, но при реализации возникают непонятки.

Question

[VasG]

Скорее всего это связано с неполным пониманием (мной) специфики языка JAVA.
В общем: имеется двумерный массив array[][], где каждой координате соответствует либо ноль, либо не ноль. Не ноль — значит в этой точке центр окружности, а радиус задан извне и он на протяжении цикла постоянен. Значение элемента массива означает приблизительную вероятность того, что в этой точке действительно должен находиться центр окружности. Существует некий параметр (kriteria), который отсекает все маловероятные варианты.
Есть много окружностей, у которых центры находятся очень близко друг к другу, а также есть пересекающиеся окружности. Это вредно, т.к. данные массива используются для последующей статистической обработки.
Собственно, как я это делаю:

1. // Анализ исходного массива.
2.      for (int x1 = 0; x1 < width; x1++) {
3.          for (int y1 = 0; y1 < height; y1++) {
4.              // Если счётчик меньше критерия, то обнуляем его к чёрту.
5.              if (array[x1][y1] < kriteria) {
6.                  array[x1][y1] = 0;
7.              } else { // Если нет- продолжаем сравнение.
8.                  for (int x2 = x1 + 1; x2 < width; x2++) {
9.                      for (int y2 = y1 + 1; y2 < height; y2++) {
10.                          // Если счётчик меньше критерия, то обнуляем его к чёрту.
11.                          if (array[x2][y2] < kriteria) {
12.                              array[x2][y2] = 0;
13.                          } else { // Если нет - продолжаем сравнение.
14.                              // Самое время вычислить расстояние между окружностями.
15.                              long rasst = Math.round(Math.sqrt(Math.pow(y2 - y1, 2) + Math.pow(x2 - x1, 2)));
16.                              if (rasst < rasstKriteria) {
17.                                  array[x2][y2] = array[x1][y1] + array[x2][y2];
18.                                  array[x1][y1] = 0;
19.                              }
20.                          }
21.                      }
22.                  }
23.              }
24.          }
25.      }

При этом огромная часть (массив 3000х2000) ненужных точек отсекается, но часть всё равно остаётся! ЧЯДНТ? Я ошибся в коде? Подскажите пожалуйста, у кого есть немного времени!

Answer 1

[xappymah]

Мне кажется, что проблема может быть из-за того, что внутренний цикл (c x2 и y2) проходит по слишком ограниченной области — по прямоугольнику от (x1, y1) до (width, height), хотя должен пройтись по всем элементам прямоугольника (x1 + 1, 0) — (width, height) и по элементам (x1, y1 +1) — (x1, height).

В вашем же случае никогда не произойдет сравнения таких точек, например, как (x1, y1) и (x1 + 1, y1 -1), т.к. вторая не входит во внутренний цикл.

Comments

[VasG]

Действительно! Вот я слепой! Спасибо большое!

Answer 2

[ENargit]

У меня появилась еще идея для Вас.
А зачем вы используете такой огромный вложенный второй цикл? Ведь для точки (0,0) второй цикл пробежит по сути весь массив (сколько он у Вас там — 3000х2000 ?). Можно было бы пробегать лишь [x1,x1+rasstKriteria],[y1,y1+rasstKriteria]. Думаю, это эффективнее.

Comments

[ENargit]

Точее, с учетом очень верного замечания xappymah, лучше что-то вроде [x1-rasstKriteria,x1+rasstKriteria],[y1-rasstKriteria,y1+rasstKriteria]. Разумеется, с проверкой на выход за границы массива.

[VasG]

И в таком случае их вообще не нужно сравнивать! Можно просто обнулить всю область интереса, раз уж мы всё равно только её рассматриваем. Вот спасибо!!! Скорость выполнения обработки массива увеличилась почти на 35%!

[VasG]

И тогда «верхний» (по вложенности) цикл можно будет попросить шагать не по каждому элементу, а шагами по rasstKriteria, но тут надо как-то хитро придумать, чтобы, как говорится, не налажать :) Тогда скорость ещё поднимется! Это просто замечательно!

Answer 3

[Анатолий]

Извините что не по делу, но я просто не мог пройти молча мимо переменной rasst и rasstKriteria >.<
почему Вы не назвали переменные width и height соответственно shirin и visot?

Comments

[Александр]

английский у автора, по видимому, ещё не так хорош, я раньше тоже так писал часто

[Анатолий]

У меня тоже не так хорош английский, отчасти по этому у меня всегда открыта вкладка с гугл транслейтом.

[VasG]

Потому что переменные width и height уже заняты. Ну да, замесил русский с английским (ещё и неправильным), но обычно я быстро учусь и быстро в будущем исправлюсь, обещаю :)

Answer 4

[ENargit]

Мне не каежтся, что здесь вопрос действительно лишь в непонимании специфики Java. Мне бросаются в глаза несколько моментов:
— обнуление «к черту» я бы проводил в одном месте полным двойным циклом вначале (меньше побочных эффектов надо отслеживать).
— смущает округление Math.round. Это точно Вам нужно? Просто, в принципе, это может быть причиной потери нескольких вариантов.
— ну и проверьте, не забыли ли Вы учесть удвоение радиуса в rasstKriteria.

А вообще, действительно, сложно строить предположения не видя хотя бы какого-нибудь примера.

Answer 5

[Александр]

ну дык возьмите точку, которая не отрезается и посмотрите, что с ней происходит. Кэп как бы намекает.