выпуклая оболочка

[Anton147]

Задача: разработать программу, которая из заданного массива точек определяет "внешние" точки и строит выпуклую оболочку исходного массива точек.

Прогмамму я написал но при большом количестве точек выходят ошибки! Может я что-то упустил. Ребята помогите плиз...

Исходники во вложениях.

[phomm]

Дельфи с включённой опцией Range Check Errors сказала что есть выход за диапазон массива в sliyanie2 указывая строку

  if ((mass2[i2].X) > (mass1[i1].X)) then

Перепроверяйте все индексы, включите опцию эту (Project-options-compiler) введите 3 точки и запускайте отладку пошагово - увидишь.

[Anton147]

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

Дельфи с включённой опцией Range Check Errors сказала что есть выход за диапазон массива в sliyanie2 указывая строку

  if ((mass2[i2].X) > (mass1[i1].X)) then

Перепроверяйте все индексы, включите опцию эту (Project-options-compiler) введите 3 точки и запускайте отладку пошагово - увидишь.

спасибо! проверил, нашел ошибку, исправил.

function sliyanie2(mass1,mass2:TPointsArray;const n,n1,n2:integer):TPointsArray;
  var  i,i1,i2:integer;
  begin
  i1:=0;
  i2:=0;
  SetLength(Result,n);
  for i:=0 to n-1 do
  begin
  if n2=0 then Continue;
  if (i1<n1) and (i2<n2) then
  begin
  if ((mass2[i2].X) > (mass1[i1].X)) then
         begin
         if (i1<n1) then begin Result[i]:=mass1[i1]; inc(i1); end
                  else begin
                       if (i2<n2) then begin Result[i]:=mass2[i2]; inc(i2); end;
                       end;
         end
         else
         begin
         if (i2<n2) then begin Result[i]:=mass2[i2]; inc(i2); end
                  else begin
                       if (i1<n1) then begin Result[i]:=mass1[i1]; inc(i1); end;
                       end;
         end;
  end
  else
  begin
  if (i2=n2) and (i1<n1) then begin Result[i]:=mass1[i1]; inc(i1); end;
  if (i1=n1) and (i2<n2) then begin Result[i]:=mass2[i2]; inc(i2); end;
  end;
  end;
  end;

Не взял в учет то что при окончании одного из массивов он будет проверять элемент который не определен. Теперь все нормально. Но есть еще проблема. Оболочка в некоторых случаях определяется не совсем точно

[phomm]

Чисто алгоритмически затрудняюсь что-то посоветовать. Могу посоветовать только увеличить декомпозицию кода, чтобы свести на нет возможные влияния человеческой ошибки.
Ну или локализуйте проблему и приведите код с поправленным проектом и указанием на область поисков, а самое главное, поясните, в чем математически заключается смысл слов "выпуклая оболочка", а то я, например, затрудняюсь искать то, не знаю что.

[Anton147]

Выпуклая оболочка множества заданных на плоскости точек – это наименьший(т.е. его площадь минимальная) выпуклый многоугольник, который содержит все точки этого множества. При этом все вершины многоугольника – это точки исходного множества точек.

[phomm]

Я так примерно и представлял.
Но помочь вряд ли смогу - погонял немного, редко попадается косяк, даже на большом наборе, плюс дебаг самой сути алгоритма в принципе сложен, задача то специфична. Вот прикрутили бы Вы загрузку точек с файла и намутили такой набор на котором гарантированно Ваш алгоритм даёт косяк, при чём чем меньше набор точек - тем лучше будет, тогда и дебажить сей косяк можно, а так только время уйдёт, иголка в стоге сена, при чём я даже не буду понимать , зачем она мне нужна