многоугольник на основе точек периметра - пространственный оракул

У меня есть таблица с баллами. Я хотел бы создать многоугольник на основе этих точек, а затем вернуть только те точки, которые находятся на периметре (исключить точки, которые находятся внутри многоугольника). Есть ли простой способ сделать это на уровне базы данных с помощью SDO GEOMETRY? Я нахожу что-то вроде GrahamScan, но не могу найти ничего подобного для Spatial


person Marcin Erbel    schedule 15.06.2013    source источник
comment
Как определить периметр неупорядоченного множества точек? Вы ищете выпуклую оболочку (погуглите, если не знаете, что это такое) множества точек?   -  person Spacedman    schedule 15.06.2013


Ответы (2)


Я не могу придумать никакого простого ответа со встроенными пакетами, которые предоставляет Oracle. Возможно, вам придется подумать о написании довольно ужасного кода для этого, если вы хотите решить проблему в Oracle.

Дрянное решение может состоять в том, чтобы разбить это на несколько шагов:

  1. Перебор всех возможных линий между каждым набором из двух точек (выберите декартово произведение точек, постройте их в линии):
  2. Найдите все линии, которые не пересекаются ни с одной другой линией (самый внешний периметр), и получите значения точек.
  3. Присоедините значения точек к исходной таблице, чтобы получить любые данные (при необходимости).

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

Вот краткая иллюстрация (непроверенный SQL)...

Входные данные:

SELECT sdo_geometry(2001, NULL, sdo_point_type(tbl.x, tbl.y,  NULL), NULL, NULL)
FROM my_table tbl

Входные данные для алгоритма

Декартово произведение координат, преобразованное в линии:

WITH point_cartesian AS (
  SELECT 
    tbl.x x1
  , tbl.y y1
  , tbl2.x x2
  , tbl2.y y2
  FROM my_table tbl
  CROSS JOIN my_table tbl2
  WHERE tbl.x != tbl2.x 
  OR tbl.y != tbl2.y
)
SELECT sdo_geometry(
  2002
, NULL
, NULL
, sdo_elem_info_array(1, 2, 1)
, sdo_ordinate_array(x1, y1, x2, y2)
)
FROM point_cartesian

Декартово произведение координат, преобразованное в прямые

Определите нужные строки:

WITH point_cartesian AS (
  SELECT 
    tbl.x x1
  , tbl.y y1
  , tbl2.x x2
  , tbl2.y y2
  FROM my_table tbl
  CROSS JOIN my_table tbl2
  WHERE tbl.x != tbl2.x 
  OR tbl.y != tbl2.y
)
, lines AS (
  SELECT sdo_geometry(
    2002
  , NULL
  , NULL
  , sdo_elem_info_array(1, 2, 1)
  , sdo_ordinate_array(x1, y1, x2, y2)
  ) geom
  , ROWNUM line_id
  FROM point_cartesian
)
SELECT *
FROM lines l1
WHERE NOT EXISTS (
  SELECT 1
  FROM lines l2
  WHERE l2.line_id != l1.line_id
  AND sdo_geom.sdo_intersect (l1.geom, l2.geom, 0.05) IS NOT NULL
)

Определить линии

Обратите внимание: SQL не тестировался, но, надеюсь, вы уловили идею.

person Ben    schedule 16.06.2013

Если данные действительно соответствуют описанию в первом ответе, то самый простой и быстрый способ - просто получить выпуклую оболочку вокруг вашего набора точек. Предполагая, что вы вводите таблицу MY_TABLE, содержащую два столбца, X и Y, которые представляют долготу и широту (отсюда и SRID 4326):

select sdo_aggr_convexhull (
         sdoaggrtype (
           sdo_geometry(2001, 4326, sdo_point_type(x, y,  NULL), NULL, NULL),
           0.5
         )
       )
from my_table;

Результатом является многоугольник, построенный с использованием точек периметра.

person Albert Godfrind    schedule 18.10.2013