Функция проверки вхождения точки в многоугольник

← →
delphin1986 © (2015-07-17 16:37) [0]

Доброго времени суток! Помогите пожалуйста исправить функцию проверки вхождения точки в многоугольник:
Есть вершины многоугольника [43.210180617618484,76.85760498046875],[43.18965832646819,76.80404663085937],[43 .07440531650471,76.85554504394531],[43.14258116631987,77.1295166015625],[43.2366 9920384741,76.97433471679687]

и собственно точка
43.21243264381804,76.3374710083008

Если отобразить многоугольник и точку на карте то визуально видно что она не входит в многоугольник, но FireBird функция проверки говорит об обратном

create or alter procedure INPOLYGON ( POLYGON_VALUES varchar(30000), LNG_E double precision, LNG_N double precision) returns ( RESULT smallint) as declare variable BOOL2 smallint; declare variable BOOL1 smallint; declare variable Y double precision; declare variable X double precision; declare variable VAL varchar(30000); declare variable I1_X double precision; declare variable I1_Y double precision; declare variable I2_Y double precision; declare variable I2 integer; declare variable I1 integer; declare variable I2_X double precision; declare variable VAL2 varchar(30000); declare variable STR varchar(30000); begin STR = POLYGON_VALUES; result=0; val2=replace(str, "]",""); I2=0; I1=char_length(str)-char_length(val2); while (I1>0) do begin select first 1 res from get_coordinates(:I1,:polygon_values) into :val; I1_x = substring(val from 1 for position(",",val)-1); i1_y = substring(val from position(",",val)+1 for CHAR_LENGTH(val)); select first 1 res from get_coordinates(:I2,:polygon_values) into :val; i2_x = substring(val from 1 for position(",",val)-1); i2_y = substring(val from position(",",val)+1 for CHAR_LENGTH(val)); x = lng_n; y = lng_e; bool1 = 0; bool2 = 0; if (I1_x < x) then bool1=1; else bool1=0; if (x <= i2_x) then bool2=1; else bool2=0; if (bool1 = bool2) then begin if ((y - i1_y) < (x - i1_x) * (i2_y - i1_y) / (i2_x - i1_x)) then begin if (result=0) then result=1; else result=0; end end i2=I1; I1=I1-1; end suspend; end^ create or alter procedure GET_COORDINATES ( IDX integer, COORDINATES varchar(10000)) returns ( RES varchar(100)) as declare variable KON integer; declare variable VAL varchar(10000); declare variable STR varchar(10000); declare variable Y double precision; declare variable X double precision; declare variable N integer; declare variable NACH integer; begin n=0; STR = COORDINATES; kon = -1; nach = position("[",str,1); while ((nach > 0)and(n <> idx)) do begin kon = position("]",str,nach); val = substring(str from nach+1 for (kon-nach)-1); x = substring(val from 1 for position(",",val)-1); y = substring(val from position(",",val)+1 for CHAR_LENGTH(val)); val = x||","||y; nach = position("[",str,kon); n = n + 1; end if (n = idx) then res = val; suspend; end^ SET TERM ; ^

Числа GPS координат точки и точек многоугольника как видите имеют разную длину, возможно это разные системы GPS координат , но Яндекс карты отображают все верно. Голова не варит совсем от жары, не могу сам вникнуть ... (
Помогите разобраться пожалуйста

← →
Dimka Maslov © (2015-07-17 16:55) [1]

А у нас прохладно и града насыпало как зимой снега. Поэтому прежде всего советую выкинуть эту "функцию" и обратиться к аналитической геометрии, она даёт однозначный ответ на вопрос. Если нет возможности обратиться к аналитической геометрии, можно обраться к функциям... WinAPI. Там в разделе GDI есть замечательные функции для работы с регионами. Я сам так поступал для решения задачи о площади пересечения двух невыпуклых многоугольников.

← →
ВладОшин © (2015-07-17 17:49) [2]

"сократить на точку", умножить нацело на k (~100, 1000), взять простой PtInRgn
"сократить на точку" = точка всегда 0,0 и соотв, из всех вершин вычесть ее

← →
ВладОшин © (2015-07-17 17:54) [3]

"сократить на точку" = вспомнил, параллельный перенос )

← →
ВладОшин © (2015-07-17 17:56) [4]

аа.. геокоординаты.. это засада )
"Жук, ползущий по поверхности шара, уверен что он ползет по полскости"

← →
delphin1986 © (2015-07-17 18:33) [5]

Dimka Maslov © (17.07.15 16:55) [1]
Функцию необходимо использовать в SQL запросе

ВладОшин © (17.07.15 17:49) [2]
Ничего не понял )

← →
Dimka Maslov © (2015-07-17 18:40) [6]

> Функцию необходимо использовать в SQL запросе

Тогда остаётся подружиться с аналитической геометрией.

← →
MBo © (2015-07-17 18:56) [7]

Нет ли в используемой базе данных встроенных функций работы с географическими координатами?

Для плоскости проверка вхождения в многоугольник тут:
http://delphimaster.net/view/9-1347083790/
Однако для геогр. координат это не работает

> Если отобразить многоугольник и точку на карте то визуально
> видно что она не входит в многоугольник
>

В курсе, что кратчайшее расстояние на глобусе (дуга большого круга) может выглядеть несколько неожиданно? См. картинку Багдад-Осака тут:
http://www.movable-type.co.uk/scripts/latlong.html

Лучше найти готовую функцию вхождения для географических координат. Если толкового решения нет, можно построить её самостоятельно, например, с использованием метода подсчета количества пересечений сторон с произвольным лучом из точки. В помощь - секции из последнейй ссылки
Intersection of two paths given start points and bearings и Distance
Distance

← →
megavoid © (2015-07-17 20:27) [8]

[1] гуглите Firebird spatial geocode, pointfromWKB и подобное

У нас в продакшене такое решение, с базой максмайнда, думаю и для FB есть WKB.

← →
megavoid © (2015-07-17 20:28) [9]

DECLARE PL_maxmind_geo ENUM("UNKNOWN","A1","A2","AD","AE","AF","...","YE","YT","ZA","ZM","ZW"); SELECT SQL_CACHE country_tld INTO PL_maxmind_geo FROM maxmind_spatial WHERE MBRCONTAINS(pool_polygon,POINTFROMWKB(POINT(IN_ip,0))) LIMIT 1; IF (isnull(PL_maxmind_geo)) THEN SET PL_maxmind_geo="UNKNOWN"; END IF; RETURN PL_maxmind_geo;

что-то типа того

← →
megavoid © (2015-07-17 20:28) [10]

← →
megavoid © (2015-07-17 20:29) [11]

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

← →
delphin1986 © (2015-07-18 07:12) [12]

MBo © (17.07.15 18:56) [7]
К сожалению готовых функций для FireBird нет.
Моя функция отлично работает проверяя обычные числа на принадлежность полигону. Правильно ли я понял, что можно преобразовать координаты точки и вершин многоугольника на плоскость и все начнет работать правильно?
http://forum.sources.ru/index.php?showtopic=371062

← →
MBo © (2015-07-18 07:19) [13]

>Правильно ли я понял, что можно преобразовать координаты точки и вершин многоугольника на плоскость и все начнет работать правильно?

Нет, не получится.

Может быть есть подходящая функция на Delphi которую я бы переписал под FireBird?

Нашел вроде бы подходящую функцию в MySQL(есть возможность поменять СУБД) - ST_contains, однако не могу заставить ее работать:
select * from table where ST_contains(ST_GeomFromText
("POLYGON(43.210180617618484 76.85760498046875, 43.18965832646819 76.80404663085937, 43.07440531650471 76.85554504394531, 43.14258116631987 77.1295166015625, 43.23669920384741 76.97433471679687)"),
Point(43.197193, 76.930123))

Подскажите почему ST_contains возвращает false ведь точка принадлежит полигону?

Почему-то функция ST_GeomFromText не преобразовывает текст в полигон

Пример отличается количеством скобок. И на всякий случай - разделитель дробной части стоит нужный?

SELECT ST_GeomFromText("POLYGON((-71.1776585052917 42.3902909739571,-71.1776820268866 42.3903701743239, -71.1776063012595 42.3903825660754,-71.1775826583081 42.3903033653531,-71.1776585052917 42.3902909739571))");

Кратчайшая прямая на глобусе это кривая.

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

Поэтому и прямоугольник состоит из дуг. Так что одни вершины расставить на плоскости не достаточно. Нужны нелинейные преобразования. Либо плоскость растянуть. Либо грани многоугольника выгнуть.

> MBo © (18.07.15 14:35) [17]

Мистика ) Ваш пример работает, подставляю свои координаты, возвращает NULL
Разделитель "." MySQL 5.6.20

SELECT ST_GeomFromText("POLYGON((43.210180617618484 76.85760498046875,43.18965832646819 76.80404663085937,43.07440531650471 76.85554504394531,43.14258116631987 77.1295166015625,43.23669920384741 76.97433471679687))");

Функция проверки вхождения точки в многоугольник Найти похожие ветки