Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2010.08.27;
Скачать: CL | DM;

Вниз

Попадает ли точка в замкнутый многоугольник   Найти похожие ветки 

 
kudatsky   (2010-04-22 11:54) [0]

На экране находится не выпуклый многоугольник, заданный координатами X1,Y1,X2,Y2,X3,Y3 и т.д. Задана точка X,Y. Как определить, находится ли точка внутри фигуры ? Нет ли для этого системной функции ?


 
oldman ©   (2010-04-22 12:11) [1]


> Нет ли для этого системной функции ?


Огорчу. Нет.


 
Дмитрий Белькевич   (2010-04-22 12:14) [2]


function IsPointInPolygon(X, Y: integer; TepmPolyLine: TDAPoint): boolean;
var
 i, n: integer;
begin
 i := 0;
 n := Length(TepmPolyLine) - 1;
 Result := False;
 repeat
  if not ((y > TepmPolyLine[i].Y) xor (y <= TepmPolyLine[i + 1].Y)) then
   if x - TepmPolyLine[i].X < (y - TepmPolyLine[i].Y) * (TepmPolyLine[i + 1].X - TepmPolyLine[i].X) /
    (TepmPolyLine[i + 1].Y - TepmPolyLine[i].Y) then
    Result := not Result;
  i := i + 1;
 until i >= n;
end;



TDAPoint        = array of TPoint;


Системной - не видел.


 
kudatsky   (2010-04-22 12:26) [3]

Дмитрий, спасибо !
Сейчас буду разбираться !


 
Leonid Troyanovsky ©   (2010-04-22 12:27) [4]


> Дмитрий Белькевич   (22.04.10 12:14) [2]

> Системной - не видел.

PtInRegion ?

--
Regards, LVT.


 
Омлет ©   (2010-04-22 13:53) [5]

> Дмитрий Белькевич   (22.04.10 12:14) [2]

Работает неверно.


 
Омлет ©   (2010-04-22 14:02) [6]

Пардон. Работает верно, но если последняя точка в массиве совпадает с первой.


 
Омлет ©   (2010-04-22 14:09) [7]

Если использовать PtInRegion, то можно не замыкать точки.

function IsPointInPolygon(X, Y: integer; Points: TDAPoint): boolean;
var
  Rgn : HRGN;
begin
  Result := False;
  Rgn := CreatePolygonRgn(Pointer(@Points[0])^, Length(Points), WINDING);
  if Rgn <> 0 then
  begin
    Result := PtInRegion(Rgn, X, Y);
    DeleteObject(Rgn);
  end;
end;


 
Sha ©   (2010-04-22 14:10) [8]

А ничего, что за границу массива выходит?


 
Sha ©   (2010-04-22 14:11) [9]

[8] относится к [2]


 
kudatsky   (2010-04-22 14:15) [10]

Всё прекрасно работает.
Всем спасибо ;-)))


 
Ins ©   (2010-04-22 14:39) [11]


> А ничего, что за границу массива выходит?


Не выходит:

> i := i + 1;  
>until i >= n;



> Омлет ©   (22.04.10 14:09) [7]
> Если использовать PtInRegion, то можно не замыкать точки.
>


Зато скорость выполнения в сотни раз может быть больше. Регион - это множество непересекающихся прямоугольников. Если их сотни, то и сотни раз проверить на вхождение (в каждый) нужно.


 
Ins ©   (2010-04-22 14:42) [12]


> Зато скорость выполнения

Время выполнения, оговорился...


 
Sha ©   (2010-04-22 14:53) [13]

> Ins ©   (22.04.10 14:39) [11]

Да, точно. По инерции считал, что n - количество точек.


 
Sha ©   (2010-04-22 15:59) [14]

Алгоритм [2] не работает, если точка лежит левее последнего отрезка  
и ее ордината лежит между ординатами последнего отрезка.

Например, для квадрата
 a[0].y:=0; a[0].x:=2;
 a[1].y:=0; a[1].x:=0;
 a[2].y:=2; a[2].x:=0;
 a[3].y:=2; a[3].x:=2;


Подправить можно так:

function ShaIsPointInPolygon(X, Y: integer; TepmPolyLine: TDAPoint): boolean;
var
 i1, i2: integer;
begin
 Result:=false;
 i2:=0;
 i1:=Length(TepmPolyLine)-1;
 while i1>=0 do begin;
   if not ((TepmPolyLine[i1].x < x) xor (x <= TepmPolyLine[i2].x))
   then if y - TepmPolyLine[i1].y
        < (x - TepmPolyLine[i1].x)
        * (TepmPolyLine[i2].y - TepmPolyLine[i1].y)
        / (TepmPolyLine[i2].x - TepmPolyLine[i1].x)
       then Result:=not Result;
   i2:=i1;
   i1:=i1-1;
   end;
 end;

procedure TForm1.Button2Click(Sender: TObject);
var
 a: TDAPoint;
 x, y: integer;
begin;
 SetLength(a,4);
 a[0].y:=0; a[0].x:=2;
 a[1].y:=0; a[1].x:=0;
 a[2].y:=2; a[2].x:=0;
 a[3].y:=2; a[3].x:=2;  
 x:=1; y:=1;
 Memo1.Lines.Add(IntToStr(Ord(IsPointInPolygon(x, y, a))));
 Memo1.Lines.Add(IntToStr(Ord(ShaIsPointInPolygon(x, y, a))));
 end;


 
Омлет ©   (2010-04-22 16:41) [15]

> Sha ©   (22.04.10 15:59) [14]
> Алгоритм [2] не работает, если точка лежит левее последнего отрезка

Если замкнуть точки (т.е. чтобы последняя была равна первой), то работает.


 
Дмитрий Белькевич   (2010-04-22 16:45) [16]


> [8] относится к [2]


Алгоритм рабочий. N - количетво точек минус одну, да. Что бы лишних телодвижений не делать в цикле.

За [14] спасибо. Проверю.


 
Дмитрий Белькевич   (2010-04-22 16:49) [17]


> Если замкнуть точки (т.е. чтобы последняя была равна первой),
>  то работает.


+1. У меня замыкается.


 
Sha ©   (2010-04-22 16:57) [18]

> Омлет ©   (22.04.10 16:41) [15]
> Если замкнуть точки (т.е. чтобы последняя была равна первой), то работает.

Очень похоже на костыль.


 
Sha ©   (2010-04-22 16:59) [19]

> Дмитрий Белькевич   (22.04.10 16:45) [16]
> За [14] спасибо. Проверю.

Надо иметь в виду, что в нем массив не замыкается.


 
Sha ©   (2010-04-22 17:00) [20]

Еще у этого алгоритма есть одно слабое место:
он дает разные ответы, в случаях когда точка лежит на левом или правом отрезке.
Имеет смысл включить границы, заменив неравенство на нестрогое в последнем if


 
Sha ©   (2010-04-22 17:05) [21]

Sha ©   (22.04.10 17:00) [20]

Хотя нет, не подумал, это не поможет.


 
Дмитрий Белькевич   (2010-04-22 19:31) [22]


> Очень похоже на костыль.


Возможно. Попробую [14].


 
Sha ©   (2010-04-23 00:30) [23]

Кстати, можно в несколько раз повысить скорость вычислений алгоритма [14].
если изменить объявление параметров функции следующим образом:

function ShaIsPointInPolygon(X, Y: integer; var TepmPolyLine: TDAPoint): boolean;


Можно ускорить функцию еще примерно в полтора раза,
но уже ценой ухудшения читаемости кода:

function ShaIsPointInPolygon2(Pt: PPoint; Poly: PPoint; Count: integer): boolean;
type
 TPointArray  = array[0..$6ffffff] of TPoint;
 PPointArray = ^TPointArray;
var
 Last: PPoint;
 Cross, dxLine, dxPoint, xOld, yOld: integer;
 Internal: boolean;
begin;
 Last:=@PPointArray(Poly)[Count-1];
 with Last^ do begin;
   xOld:=x;
   yOld:=y;
   end;
 Cross:=0;
 Internal:=true;
 repeat;
   dxPoint:=Poly.x - Pt.x;
   xOld:=xOld - Pt.x;
   if dxPoint xor xOld<0 then begin;
     dxLine:=dxPoint - xOld;
     yOld:=(yOld - Poly.y) * dxPoint
         + (Poly.y - Pt.y) * dxLine;
     if yOld=0
     then Internal:=not Internal
     else Cross:=Cross xor yOld xor dxLine;
     end;
   xOld:=Poly.x;
   yOld:=Poly.y;
   inc(Poly);
   until dword(Poly)>dword(Last);
 Result:=boolean(Cross shr 31) and Internal;
 end;


В последнем варианте функции передаются три параметра:
указатель на проверяемую точку,
указатель на первую вершину многоугольника,
количество вершин многоугольника.

Для точек, лежащих на границе многоугольника, поведение этой функции
единообразно: граничные точки не считаются внутренними.
Это отличается от предыдущей функции, которая может возвращать произвольный результат.


 
Sha ©   (2010-04-23 01:09) [24]

Если требуется совместимость с алгоритмом [14]
(границы с меньшими абсциссами/ординатами включаются, с большими - исключаются),
то можно использовать такую модификацию алгоритма:

function ShaIsPointInPolygon3(Pt: PPoint; Poly: PPoint; Count: integer): boolean;
type
 TPointArray  = array[0..$6ffffff] of TPoint;
 PPointArray = ^TPointArray;
var
 Last: PPoint;
 Cross, dxLine, dxPoint, xOld, yOld: integer;
begin;
 Last:=@PPointArray(Poly)[Count-1];
 with Last^ do begin;
   xOld:=x;
   yOld:=y;
   end;
 Cross:=0;
 repeat;
   dxPoint:=Poly.x - Pt.x;
   xOld:=xOld - Pt.x;
   if dxPoint xor xOld<0 then begin;
     dxLine:=xOld - dxPoint;
     yOld:=(yOld - Poly.y) * dxPoint
         + (Pt.y - Poly.y) * dxLine;
     if yOld<>0 then Cross:=Cross xor yOld xor dxLine;
     end;
   xOld:=Poly.x;
   yOld:=Poly.y;
   inc(Poly);
   until dword(Poly)>dword(Last);
 Result:=boolean(Cross shr 31);
 end;


 
Дмитрий Белькевич   (2010-04-23 01:27) [25]

Неплохо. Оптимизацию по скорости почти не делал - так только - убрал очевидное. Тоже как-то замечал, что const/var в параметрах может ускорить обработку - убирается косвенный доступ к массивам.


 
Sha ©   (2010-04-23 14:32) [26]

Можно заметить, что в выражениях для соседних отрезков имеется общая часть.
Это можно использовать для дополнительного ускорения функции:

type
 TPointArray  = array[0..$0ffffffe] of TPoint;
 PPointArray = ^TPointArray;

function ShaIsPointInPolygon1(Pt: PPoint; Poly: PPoint; Count: integer): boolean;
var
 Last: PPoint;
 dx1, dx2, Delta, yOld, Res: integer;
begin;
 Res:=0;
 Last:=@PPointArray(Poly)[Count-1];
 with Last^ do begin;
   dx1:=x - Pt.x;
   yOld:=y;
   end;

 repeat;
   dx2:=Poly.x - Pt.x;
   if dx1 xor dx2 < 0 then begin;
     dx1 := dx1 - dx2;
     Delta := (Pt.y - Poly.y) * dx1
            + (yOld - Poly.y) * dx2;
     if Delta<>0 then Res:=Res xor dx1 xor Delta;
     end;
   yOld:=Poly.y;
   inc(Poly);
   if dword(Poly)>dword(Last) then break;

   dx1:=Poly.x - Pt.x;
   if dx2 xor dx1 < 0 then begin;
     dx2 := dx2 - dx1;
     Delta := (Pt.y - Poly.y) * dx2
            + (yOld - Poly.y) * dx1;
     if Delta<>0 then Res:=Res xor dx2 xor Delta;
     end;
   yOld:=Poly.y;
   inc(Poly);
   until dword(Poly)>dword(Last);

 Result:=boolean(Res shr 31);
 end;


 
Игорь Шевченко ©   (2010-04-23 18:24) [27]


>    dx2:=Poly.x - Pt.x;
>    if dx1 xor dx2 < 0 then begin;


можно для бестолковых этот участок кода перевести ?


 
MBo ©   (2010-04-23 18:50) [28]

>можно для бестолковых этот участок кода перевести ?
Это сравнение знаков dx1 и dx2  - вопрос об этом?


 
Sha ©   (2010-04-23 19:10) [29]

>> if dx1 xor dx2 < 0 then begin;
>   можно для бестолковых этот участок кода перевести

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

Сравнением dx1 xor dx2 < 0 мы проверяем выполние одного условий
Poly.x < Pt.x <= Old.x
Old.x  < Pt.x <= Poly.x
где Poly и Оld - координаты концов отрезка, Pt - наша точка.

Т.о. блок begin будет выполнен, если точка лежит под/над отрезком.


 
Игорь Шевченко ©   (2010-04-23 21:06) [30]

Sha ©   (23.04.10 19:10) [29]
MBo ©   (23.04.10 18:50) [28]

Круто. Но нифига не понятно с первого взгляда. Хоть бы скобки поставлены были...


 
antonn ©   (2010-04-23 22:14) [31]

Спасибо :)


 
Вася   (2010-04-24 05:24) [32]

по тестам вроде создать регион и проверить попадание в него на winapi быстрее будет...=\


 
Sha ©   (2010-04-24 10:17) [33]

> Вася   (24.04.10 05:24) [32]
> по тестам вроде создать регион и проверить попадание в него на winapi быстрее будет...=\

Хотелось бы увидеть


 
Leonid Troyanovsky ©   (2010-04-24 10:39) [34]


> Вася   (24.04.10 05:24) [32]

> на winapi быстрее будет...=\

http://support.microsoft.com/kb/121960

--
Regards, LVT.


 
Sha ©   (2010-04-24 14:45) [35]

Все ранее приведенные функции на границах региона дают результат, отличающийся от PtInRegion.
Для совместимости с API пришлось пускать луч вдоль оси X и поменять порядок анализа концов отрезков.
На моих тестах следующая функция выдает результат, совпадающий с API-шной PtInRegion,
но работает в разы быстрее (без учета времени на создание/удаление региона).
Разумеется, полная совместимость не гарантируется.

function ShaIsPointInPolygon4(Pt: PPoint; Poly: PPoint; Count: integer): boolean;
var
 Last: PPoint;
 dy1, dy2, Delta, xOld, Res: integer;
begin;
 Res:=0;
 Last:=@PPointArray(Poly)[Count-1];
 with Last^ do begin;
   dy1:=Pt.y - y;
   xOld:=x;
   end;

 repeat;
   dy2:=Pt.y - Poly.y;
   if dy1 xor dy2 < 0 then begin;
     dy1 := dy1 - dy2;
     Delta := (Pt.x - Poly.x) * dy1
            + (xOld - Poly.x) * dy2;
     if Delta<>0 then Res:=Res xor dy1 xor Delta;
     end;
   xOld:=Poly.x;
   inc(Poly);
   if dword(Poly)>dword(Last) then break;

   dy1:=Pt.y - Poly.y;
   if dy2 xor dy1 < 0 then begin;
     dy2 := dy2 - dy1;
     Delta := (Pt.x - Poly.x) * dy2
            + (xOld - Poly.x) * dy1;
     if Delta<>0 then Res:=Res xor dy2 xor Delta;
     end;
   xOld:=Poly.x;
   inc(Poly);
   until dword(Poly)>dword(Last);

 Result:=boolean(Res shr 31);
 end;


 
Ins ©   (2010-04-24 23:22) [36]


> Все ранее приведенные функции на границах региона дают результат,
>  отличающийся от PtInRegion.


А кто сказал, что именно PtInRegion дает на границах правильный результат? Регион, полученный вызовом CreatePolygonRgn, это не многоугольник, а его грубое пиксельное приближение со всеми вытекающими... Да и кому нужна эта строгая точность на границах, учитывая что функция наверняка нужна для HitTest-а


 
Игорь Шевченко ©   (2010-04-24 23:35) [37]


> А кто сказал, что именно PtInRegion дает на границах правильный
> результат?


Например я :)

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

http://support.microsoft.com/kb/121960


 
Ins ©   (2010-04-24 23:56) [38]


> Например я :)


Дан многоугольник (треугольник), координаты вершин:
(0; 0)
(6; 0)
(3; 10)
Берем точку (0;1). Очевидно, чисто геометрически она не входит в многоугольник, но PtInRegion вам скажет иначе


 
Sha ©   (2010-04-25 00:08) [39]

> Игорь Шевченко ©   (24.04.10 23:35) [37]
> А для хит-теста народ рекомендует вот такой более быстрый способ.
> http://support.microsoft.com/kb/121960

Вовсе он и не быстрый.

> Ins ©   (24.04.10 23:56) [38]
> Очевидно, чисто геометрически она не входит в многоугольник, но PtInRegion вам скажет иначе

Не скажет.


 
Дмитрий Белькевич   (2010-04-25 00:18) [40]

Мне, например, не для хиттеста нужна. Забираю алгоритмом выделенный массив точек (векторный редактор). Если несколько потеряется по краям - то не критично, даже и не знал, что проблема существует.


 
Sha ©   (2010-04-25 00:27) [41]

> Дмитрий Белькевич   (25.04.10 00:18) [40]
> даже и не знал, что проблема существует.

Существует. PtInRegion теряет точки на правой и нижней границе.

Это не проблема, если регионы прямоугольные и имеют общие границы, параллельные осям.

Но в общем случае это может привести к выпадению точек между регионами,
даже если у них общая граница.


 
Ins ©   (2010-04-25 00:43) [42]


> Не скажет.


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


 
Игорь Шевченко ©   (2010-04-25 00:51) [43]

Ins ©   (25.04.10 00:43) [42]

В компьютере все дискретно...


 
Ins ©   (2010-04-25 00:56) [44]


> В компьютере все дискретно...


Это понятно, вопрос только насколько эта дискретность грубая. Так есть ли повод утверждать, что именно PtInRegion на границе считает правильно, и равнять под него алгоритм с меньшей степенью грубости?


 
Sha ©   (2010-04-25 01:18) [45]

Нормально, вроде, он считает.
Более того, никак не удается построить пример выпадения точек у регионов с общими границами.
Похоже, в [41] я заблуждался насчет выпадения.


 
Игорь Шевченко ©   (2010-04-25 01:33) [46]

Ins ©   (25.04.10 00:56) [44]


> Это понятно, вопрос только насколько эта дискретность грубая.
>  Так есть ли повод утверждать, что именно PtInRegion на
> границе считает правильно, и равнять под него алгоритм с
> меньшей степенью грубости?


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


 
Sha ©   (2010-04-25 02:10) [47]

Допустим, на плоскости заданы 4 точки с целочисленными координатами,
являющиеся вершинами горизонтально расположенного прямоугольника.

Добавим к этому множеству точек произвольное количество новых точек,
лежащих внутри или на границах прямоугольника и также имеющих
целочисленные координаты.
> Игорь Шевченко ©   (25.04.10 01:33) [46]

Затем создадим множество непересекающихся многоугольников произвольной формы, используя в качестве их вершин наше множество точек.

Нам хотелось бы, чтобы функция, определяющая принадлежность точек
многоугольникам, относила каждую внутреннюю точку исходного прямоугольника,
а также точки, лежащие на его верхней и левой сторонах,
в точности к одному многоугольнику
и считала, что точки, лежащие на правой и нижней сторонах,
не входят ни в один многоугольник.

Вопрос в том, является ли PtInRegion такой функцией?
Все говорит за то, что является.


 
Sha ©   (2010-04-25 02:14) [48]

Окошко для редактирования текста маловато.
В результате так фигово пост [47] оформлен, но смысл должен быть понятен.


 
Германн ©   (2010-04-25 02:19) [49]


> В результате так фигово пост [47] оформлен

А в чём собственно "фиговость"? Читается нормально.


 
Sha ©   (2010-04-25 02:21) [50]

В [47] подразумевается, что общая площадь многоугольников равна площади исходного прямоугольника, т.е. он разрезан на многоугольники.


 
Sha ©   (2010-04-25 02:31) [51]

> Германн ©   (25.04.10 02:19) [49]
> А в чём собственно "фиговость"?

Лесенка строк режет глаз. От цитаты остался заголовок, который затесался в середину текста.

> Ins ©   (25.04.10 00:43) [42]
> он лишнего не включает, насколько я вижу, скорее теряет

Это псевдо-потеря. Граничная точка, как и любая другая, должна входить только в один регион. Вот она и входит в соседний регион, даже если он воображаемый.


 
Германн ©   (2010-04-25 02:34) [52]


> Sha ©   (25.04.10 02:21) [50]
>
> В [47] подразумевается, что общая площадь многоугольников
> равна площади исходного прямоугольника, т.е. он разрезан
> на многоугольники.

Так ты про суть или про оформление?


 
Sha ©   (2010-04-25 02:42) [53]

> Германн ©   (25.04.10 02:34) [52]
> Так ты про суть или про оформление?

В [47] коряво оформлено корявое изложение совершенно очевидной вещи :)

Если мы при помощи PtInRegion возьмемся красить точки каждого многоугольника в свой цвет,
то у нас не останется неокрашенных и не придется перекрашивать.


 
Германн ©   (2010-04-25 03:18) [54]

Лучше я уж промолчу.


 
Ins ©   (2010-04-25 11:45) [55]


> Sha ©   (25.04.10 02:31) [51]


Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется


 
Ins ©   (2010-04-25 11:51) [56]


> Не совсем понимаю, в чем проблема - внутренняя структура
> региона тайны не представляет, определить, принадлежит ли
> точка всем прямоугольникам из этой структуры задача вполне
> однозначно осуществимая.


Брр... Нисколько в этом не сомневаюсь, я и не о том вообще... Тут выше была попытка адаптировать алгоритм с другой логикой так, чтобы он работал именно как PtInRegion. А зачем? Если этот алгоритм работает вполне правильно (я считаю, что точнее), то какая разница как работает PtInRegion, у которого свои причуды? Или эти причуды во что бы то ни стало должны быть одинаковыми?


> Граничная точка, как и любая другая, должна входить только
> в один регион.

Кому это она должна? :) Это смотря в какой задаче


 
Игорь Шевченко ©   (2010-04-25 12:45) [57]

Ins ©   (25.04.10 11:51) [56]


> А зачем? Если этот алгоритм работает вполне правильно (я
> считаю, что точнее), то какая разница как работает PtInRegion,
>  у которого свои причуды? Или эти причуды во что бы то ни
> стало должны быть одинаковыми?


Я сильно извиняюсь, а какие причуды у PtInRegion ?


 
Sha ©   (2010-04-25 13:01) [58]

> Ins ©   (25.04.10 11:45) [55]
> Да, это фишка Windows при работе с прямоугольниками - на пиксель меньше, даже при рисовании проявляется

Если работать только с прямоугольными регионами, то можно подумать, что Windows исключает правую и нижнюю границу по одной и той же причине.
На самом деле это не так.
Обычно лучевой алгоритм проверки вхождения точки в регион проверяет, что точка находится строго левее линии. Поэтому вся левая граница не принадлежит региону. Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет правая граница.
С нижней границей дело обстоит иначе. Очевидно, алгоритм не должен считать дважды перечение луча с границей многоугольника в случае когда луч проходит точно через его вершину. Поэтому алгоритм не учитывает концы отрезков, имеющих бОльшую ординату. Это выглядит как срезание локальных выступов снизу региона, а не как полное исключение нижней границы.
Поэтому, например, невозможно создать такой регион, в который входили бы точки, помеченные буквой "о" на рисунке

..o...
.ooo..
ooooo.
.ooo..
..o...

из-за среза правой границы получим

......
.oo...
oooo..
.oo...
......

а если сдублировать границу вот так

..oo..
.oooo.
oooooo
.oooo.
..oo..

то будет еще хуже

..o...
.ooo..
ooooo.
.ooo..
......


> Или эти причуды во что бы то ни стало должны быть одинаковыми?

Одинаковость причуд говорит о возможной одинаковости алгоритмов.

>> Граничная точка, как и любая другая, должна входить только в один регион.
> Кому это она должна? Это смотря в какой задаче.

Это да.

Если мы выводим на экран сформированное в многоугольниках изображение, нам будет приятно сознавать, что на экране не будет дыр и избражения не перекрываются. Тут подходит, например, алгоритм совместимый с PtInRegion.

А если мы показываем на однотонном фоне какой-нибудь геометрический объект, например, пирамиду, то имеет смысл отрисовать его четкие границы.
Приведенный алгоритм может быть легко модифицирован для этой задачи


 
Sha ©   (2010-04-25 13:09) [59]

> Sha ©   (25.04.10 13:01) [58]

Написано:

> Обычно лучевой алгоритм проверки вхождения точки в регион проверяет,
> что точка находится строго левее линии.
> Поэтому вся левая граница не принадлежит региону.
> Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет правая граница.

Читать так:

Обычно лучевой алгоритм проверки вхождения точки в регион проверяет,
что точка находится строго левее линии.
Поэтому вся правая граница не принадлежит региону.
Если заменить равенство на нестрогое, то лучше не станет - тогда пропадет левая граница.


 
Anatoly Podgoretsky ©   (2010-04-25 13:19) [60]

> Sha  (25.04.2010 13:09:59)  [59]

Насколько я знаю, правая координата не указывается, а то что кажется координатой, на самом деле является длиной.
Поеэтому прямоугольник на 0, 32 - это не прямоугольник на 33 пикселя. Это обсуждали в Борландовских конференциях лет 10 назад.


 
Sha ©   (2010-04-25 13:40) [61]

> Anatoly Podgoretsky ©   (25.04.10 13:19) [60]

Да, конечно.


 
Ins ©   (2010-04-25 19:17) [62]


> Одинаковость причуд говорит о возможной одинаковости алгоритмов.


Едва ли... Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных, в данном случае - о том, что это многоугольник с такими-то вершинами. Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников, которые являются приближением к этому полигону. А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.


 
Sha ©   (2010-04-25 22:28) [63]

> Ins ©   (25.04.10 19:17) [62]
>  Для этого необходимо чтобы регион Windows хранил информацию о своих исходных данных...

Нет, не необходимо.

> Насколько я знаю, такие данные он не хранит, он хранит массив прямоугольников...

Эти самые прямоугольники вполне могли быть построены по лучевому алгоритму.

> А выпадение правой и нижней границы объясняется особенностями работы с прямоугольниками.

Интересно, какими особенностями работы с прямоугольниками можно объяснить различия (о которых я писал) в выпадении правой и нижней границы?
Лучевой алгоритм их прекрасно объясняет.


 
Sha ©   (2010-04-26 00:25) [64]

Хотя, наверно, и другие алгоритмы могут приводить к тем же особенностям.
Ну, это только к лучшему.



Страницы: 1 2 вся ветка

Текущий архив: 2010.08.27;
Скачать: CL | DM;

Наверх




Память: 0.66 MB
Время: 0.054 c
6-1223299271
JohnKorsh
2008-10-06 17:21
2010.08.27
Работа программ с сетевыми компонентами в ОС Vista.


8-1203951832
NaRuTo
2008-02-25 18:03
2010.08.27
DirectX or OpenGl


15-1269281948
Нехочуха
2010-03-22 21:19
2010.08.27
Природа в цифрах


2-1274121378
man_of_sense
2010-05-17 22:36
2010.08.27
Компонент WebBrowser


15-1271655350
Валерий М.
2010-04-19 09:35
2010.08.27
Принтер и логи