Правильный ли цикл для точек в области?

Question

[Voldemar_pauk]

x:=StrToFloat(Edit1.Text);

y:=StrToFloat(Edit2.Text);
  if  ((x=0) and (y=-1)) or ((x=1) and (y=-1))
  then
  Label1.Caption:=' точка лежит в заштрихованной области'
  else if ((x=-1) or (y=-2)) or ((x=2) or (y=-2)) or ((x-y)=0) or ((x+y)=4)
  or ((x=2) and (y=-1))
   then
  Label1.Caption:=' точка лежит на границе заштрихованной области '
  else Label1.Caption:=' точка за пределами заштрихованной области '

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

Answer 1

[Hemul GM]

Проверь сначала вхождение точки в треугольник. Потом в прямоугольник.
Или можешь попробовать использовать функции Windows

function PointInPolygon(Point: TPoint; const Polygon: array of TPoint): Boolean;
var
  rgn: HRGN;
begin
  rgn := CreatePolygonRgn(Polygon[0], Length(Polygon), WINDING);
  Result := PtInRegion(rgn, Point.X, Point.Y);
  DeleteObject(rgn);
end;

Использование
var Points: array of TPoint;
Points := [TPoint.Create(-1, 0), TPoint.Create(0, 0), ...];
if PointInPolygon(TPoint.Create(0, 0), Points) then <точка входит в область>

Или отдельно реализацию
https://wiki.freepascal.org/Geometry_in_Pascal

Comments

[OCTAGRAM]

1. Видно, что пытаются проверить знания аналитической геометрии, а не API
   
2. rgn нужно уничтожать в try-finally или использовать RAII-обёртку
   

[Hemul GM]

OCTAGRAM, код в сети нашёл. Претензии не ко мне)

Answer 2

[OCTAGRAM]

С точки зрения математика подобный цикл делается так: берём массив точек и идём по нему циклом, перебирая все рёбра. Аккумулятор угла инициализируем нулём. В каждой итерации цикла добавляем в аккумулятор арксинус угла между лучами из выбранной точки в вершины рёбер, знак которого зависит от направления поворота. По окончании цикла, если выяснилось, что в аккумуляторе ±2π, значит, точка внутри фигуры. Также, если одна из вершин точно совпала с точкой или если во время аккумуляции был скачок ±π (арксинус минус единицы), это значит, что точка на границе. Если точка снаружи, то аккумулятор как накопится, так и разрядится поворотами в противоположную сторону, и минус с плюсом уравновесятся.

С точки зрения программиста такую математику воплощать как есть рискованно. Вместо натурального логарифма программист по возможности возьмёт двоичный логарифм. И вместо проблемного арксинуса хочется взять что-то такое же по смыслу, но с меньшим накоплением ошибок. Я бы назвал это квадратный арксинус. Замеряет прогресс не по единичной окружности вокруг точки, а по единичному квадрату. На вход получает две пары координат, на выходе даёт число, которое в случае полного оборота накапливается не в ±2π, а в ±8.

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

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

if ((? = ?) and // строгое равенство для проверки принадлежности линии
    (? <= ?) and (? >= ?)) or // два неравенства, чтоб линию обрезать с двух сторон и превратить в отрезок

   // второй отрезок
   ((? = ?) and // строгое равенство для проверки принадлежности  линии
    (? <= ?) and (? >= ?)) or // два неравенства, чтоб линию обрезать с двух сторон и превратить в отрезок

   // третий отрезок
   // …
then
begin
  // сообщить о том, что на границе
  // …
  Exit;  
end; // if

Удобно сначала проверить принадлежность границе и выйти по Exit, а только потом проверять принадлежность толще.

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

Принадлежность точки выпуклому многоугольнику определяется конъюнкцией неравенств для каждого ребра. Для выпуклого четырёхугольника:

(? <= ?) and (? <= ?) and (? <= ?) and (? <= ?)

Для треугольника:

(? <= ?) and (? <= ?) and (? <= ?)

Соединяем то и другое через or и получаем результат. Можно пойти и в другом направлении, не объединять множества точек, а вычитать. Глядя на рисунок, можно разглядеть объемлющий прямоугольник, из которого вычтена внутренность угла 135°. Внутренность угла можно задать двумя неравенствами

(? <= ?) and (? <= ?)

И объединить через and not:

(… внутри прямоугольника …) and not (… внутри угла …)

Answer 3

[kalapanga]

Во-первых, здесь нет никакого цикла.
Во-вторых, проверка нахождения точки внутри области реализована неправильно. Даже из общих соображений понятно, что проверка попадания точки в область не может выполнятся проверкой на равенство координат точки чему-либо. Там должна быть проверка на больше-меньше.
Длинное условие проверки попадания на границу не проверял, лень. Но что-то в нём подозрительно мало логических И (and). Скорее всего оно неверное.