Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Delphi: Звук, графика и видео > Как найти точку перегиба полилинии


Автор: zvyagaaa 8.5.2009, 19:18
Здравствуйте уважаемые.
Разбираюсь с рисованием и вычислением пути от точки до точки с препятствиями
user posted image В принципе получается, но есть одно но - массив точек получившейся линии имеет вид 
Код

127;72
116;72
105;72
105;61
105;50
116;50
127;50
138;50
149;50
160;50
160;61
160;72
160;83
160;94
149;94
138;94

т.е. идет рисование по клеточкам. Все бы ничего, но надо в точках, где линия меняет направление с горизонтального на вертикальный и наоборот , например, точки с координатами 105;72, 160;50 установить метки. Вот подкоркой понимаю, что надо просто массив координат отсортировать - но как реализовать не пойму.
Выручайте, пожалуйста.

Автор: Mechanic 8.5.2009, 23:12
А не нужно ничего сортировать. smile
Просто нужно исследовать массив последовательно в направлении рисования линии, анализируя напрвление движения.
Например

Код

type
  TPointArray = array of TPoint;
  TDirection = (dNone, dVertical, dHorizontal, dDiagonal);

var

  Path: TPointArray;
  LastDir: TDirection;
  LastDot: TPoint;

function WasDirectionChanged(const aDot: TPoint): boolean;
var CurDir: TDirection;
begin
  //get direction from last dot
  if (aDot.x = LastDot.x) and (aDot.y = LastDot.y) then
    CurDir := dNone
  else
  if (aDot.x = LastDot.x) and (aDot.y <> LastDot.y) then
     CurDir := dVertical
  else
    if (aDot.x <> LastDot.x) and (aDot.y = LastDot.y) then
      CurDir := dHorizontal
    else
      CurDir := dDiagonal;
   //check change
   Result := LastDir <> CurDir;
  //store for next use
  LastDir := CurDir;
  LastDot := aDot;
end;

var
  n: integer;

//if Length(Path) > 0

//first one. Init
LastDot := Path[Low(Path)]; LastDir := dNone;
//scan
for n := Low(Path) to High(Path) do
  if WasDirectionChanged(Path[n]) then
    //mark this dot as corner one


Это не самый оптимальный код, зато наглядный. smile

А что касается "вычислением пути от точки до точки с препятствиями", то тут не совсем ясно, ищется ли маршрут, или измеряется длина уже готового пути.
Если ищется маршрут, то можно использовать алгоритм A*, или подобный. А если мерять длину, то принцип тот же - последовательно складывать длины отрезков.

Автор: AntonN 9.5.2009, 00:50
следить за сменой направления движения, банальное if(x_old<>x_new) наверное подойдет smile

Автор: zvyagaaa 9.5.2009, 06:16
Mechanic, 
огромное спасибо за код, это именно то, что мне нужно.
А ищу путь методом Ли (волновой алгоритм), измерять пройденный путь не требуется пока. Хотя тут алгоритм для меня прозрачный

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)