Конференция "Игры" » Попадает ли точка в многоугольник? [Delphi, Windows]
 
  • Опять я (08.09.12 09:56) [0]
    Требуется максимально быстрый вариант.
    Видел, много решений, стандартных, но некоторые умные люди предложили
    свой более быстрый вариант, а я их (варианты) забыл.
  • MBo © (08.09.12 14:21) [1]
  • Опять я (14.09.12 11:39) [2]
    Оъясните как перевести этот цикл:

     
    for (i = 0, j = nvert-1; i < nvert; j = i++)





    type
     TPoints = array of TPoint;

    function pnpoly(nvert: integer; const verts: TPoints; const Test: TPoint): Integer;
    var
     i, j, c: Integer;
    begin
     For i:= 0 to nvert - 1 do
       If ((verts[i].Y > Test.Y) <> (verts[i].Y > Test.Y)) and
            Test.X <
    end;


  • MBo © (14.09.12 13:37) [3]
    на первом шаге (i=0) j равно номеру последней точки, потом - на единицу отстаёт  от i
    j := nvert - 1;
    for i:= 0 to nvert - 1 do begin
     ...вычисления
     j := i;
    end;

  • Опять я (14.09.12 14:11) [4]
    Пишет все время 0 в заголовке формы, что не так? Порядок операторов?



    function pnpoly(nvert: integer; const verts: array of TPoint; const Test: TPoint): Integer;
    var
    i, j, c: Integer;
    begin
    c:= 0;
    j:= nvert - 1;
    For i:= 0 to nvert - 1 do
    begin
      If ((verts[i].Y > Test.Y) <> (verts[i].Y > Test.Y)) and
          (Test.X < (verts[j].X - verts[i].X) * (Test.Y -  verts[i].Y) / (verts[j].Y - verts[i].Y) +  verts[i].X)
           then c:= not c;
      j:= i;
    end;

    Result:= c;
    end;

    const
     DUMMY_POLYGON: array [0..5] of TPoint = ((X: 10; Y: 10),
                                              (X: 60; Y: 80),
                                              (X: 50; Y: 90),
                                              (X: 20; Y: 620),
                                              (X: 190; Y: 150),
                                              (X: 180; Y: 100));

    procedure TForm1.FormPaint(Sender: TObject);
    begin
     Canvas.FillRect(Canvas.ClipRect);
     Canvas.Polygon(DUMMY_POLYGON);
    end;

    procedure TForm1.FormMouseMove(Sender: TObject; Shift: TShiftState; X,
     Y: Integer);
    begin
     Caption:= IntToStr(pnpoly(Length(DUMMY_POLYGON), DUMMY_POLYGON, Point(X, Y)));

    end;


  • MBo © (14.09.12 14:46) [5]
    Во второй скобке ошибка.
    Кроме того, стоит отлавливать деление на ноль (что для целых чисел будет часто). И можно переделать для целых чисел вообще без деления (только знаки учитывать)
    function pnpoly(const verts: array of TPoint; const Test: TPoint): Boolean;
    var
     i, j: Integer;
    begin
     Result := False;
     j := High(verts);
     for i := 0 to High(verts) do begin
       if ((verts[i].Y > Test.Y) <> (verts[j].Y > Test.Y)) and
         (Test.X < (verts[j].X - verts[i].X) * (Test.Y - verts[i].Y) /
         (verts[j].Y - verts[i].Y) + verts[i].X) then
         Result := not Result;
       j := i;
     end;
    end;

  • MBo © (14.09.12 15:00) [6]
    P.S. Насчет деления на ноль - оно может случиться , если отключена быстрая оценка логическуих выражений.
  • Опять я (15.09.12 17:28) [7]
    Что-то я не нашел ошибку в скобках, проверил сейчас.

    А если (verts[j].Y - verts[i].Y) + verts[i].X = 0, что тогда делать?
  • Опять я (15.09.12 17:30) [8]
    Перелал с учетом 0, перестало работать!


    function pnpoly2( const verts: array of TPoint; const Test: TPoint): Boolean;
    var
    i, j, Tmp: Integer;
    begin
    Result := False;
    j := High(verts);

    for i := 0 to High(verts) do
    begin
      if ((verts[i].Y > Test.Y) <> (verts[j].Y > Test.Y)) then
      begin
        Tmp:= (verts[j].Y - verts[i].Y) + verts[i].X;
        If (Tmp <> 0) then
        begin
          If (Test.X < (verts[j].X - verts[i].X) * (Test.Y - verts[i].Y) / Tmp)
          then Result := not Result;

        end;
      end;

      j := i;
    end;
    end;


  • MBo © (15.09.12 19:02) [9]
    в [4] в обеих скобках одно и то же (i)
    if ((verts[i].Y > Test.Y) <> (verts[i].Y > Test.Y))

    C учётом нуля можно не переделывать, только на всякий случай директивой принудительно обрамить (short boolean evaluation)
    А перестало работать, потому что +verts[i].X там лишнее
  • Опять я (15.09.12 19:51) [10]
    Т.е. если выражение будет полностью проверено, то компилятор сам выкинет случай с делением на 0?
  • MBo © (15.09.12 20:03) [11]
    По умолчанию стоит директива быстрой оценки - т.е. если не выполняется первая часть if, то код во второй части не исполняется. В данном случае деление на ноль может быть при равенстве Y-координат соседних точек, а это дает False в первой части.
  • Опять я (15.09.12 20:28) [12]
    *А как обратно установить директиву по умолчанию $B?
    Вдруг мы её включили?


    function pnpoly(const verts: array of TPoint; const Test: TPoint): Boolean;
    var
    i, j: Integer;
    begin
    Result := False;
    j := High(verts);
    for i := 0 to High(verts) do begin
    {$B-} // Отключаем.
      if ((verts[i].Y > Test.Y) <> (verts[j].Y > Test.Y)) and
        (Test.X < (verts[j].X - verts[i].X) * (Test.Y - verts[i].Y) /
        (verts[j].Y - verts[i].Y) + verts[i].X) then
        Result := not Result;
     
      // *

      j := i;
    end;
    end;


  • MBo © (15.09.12 20:46) [13]
    по умолчанию выключена полная оценка. Состояние запоминать через IFDEF
  • Опять я (15.09.12 22:12) [14]
    Понятно. Спасибо.
 
Конференция "Игры" » Попадает ли точка в многоугольник? [Delphi, Windows]
Есть новые Нет новых   [118232   +26][b:0][p:0.003]