Пресичане на точков полигон в SQL - 💡 Fix My Ideas

Пресичане на точков полигон в SQL

Пресичане на точков полигон в SQL


Автор: Ethan Holmes, 2019

update: Както отбелязват читателите, проблемът не е 0 градусовата дължина, а е на 180 градуса, където можете да срещнете проблеми. Освен това избягах символите gt и lt. Съжалявам за това.

Прекарах уикенда, участвайки в F1 Website Challenge, кодиращ маратон, в който всеки отбор изработва митичен човек-месец за уеб сайт за достойна организация с нестопанска цел - всичко това в рамките на 24 часа.

Едно от предизвикателствата пред моя екип по време на разработката беше намирането на ефективен начин за откриване на конкретна област от услуги за даден адрес. Нашият клиент, Metro Meals on Wheels, има редица различни региони, в които те доставят храна, като всеки регион се обслужва от определена организация за хранене на колела. Тези региони са дефинирани от неприпокриващи се сложни полигони. Това не е толкова просто, колкото обикновеното търсене на продавача, където се връща най-близкото място до искания адрес. Вместо това трябва да търсите в базата данни с полигони, за да намерите конкретната, която пресича местоположението на адреса.

Един от моите съотборници, Марк Сиймън, се оказа доста елегантно решение на проблема и успя да го приложи в прост SQL запитване. За да разберете дали дадена точка пресича многоъгълник, тя е толкова проста, колкото да изтеглите вектор от точката и да видите колко линейни сегменти от полигона, който пресича. Ако номерът е четен, той е извън полигона. Ако е странно, имате пресечка.

Така че нека да кажем, че имате многоъгълна база данни, която има ред за всеки сегмент от полигон. Можете бързо да изтеглите всички сегменти, които се пресичат с вектор, сочещ директно на изток от геокодираното ви местоположение, по следния начин:

SELECT poly_id, segment_id FROM сегменти WHERE (lnga> thelng ИЛИ lngb> thelng) AND ((lata> thelat И latb <thelat) OR (latb> thelat И lata <thelat))

Това ще ви върне списък на всички линейни сегменти, които бихте пресекли, ако сте тръгнали направо на изток от мястото в [thelat, thelng] (да, това предполага, че не пресичате 180 градуса дължина). За да определите многоъгълника (или многоъгълниците), който пресича адреса ни, той е толкова просто, колкото групирането по поли и връща всички редове, които имат нечетен брой съвпадения:

SELECT poly_id, COUNT (segment_id) AS segment_count FROM сегменти WHERE (lnga> thelng ИЛИ lngb> thelng) AND ((lata> thelat И latb <thelat) ИЛИ (latb> thelat И lata <thelat)) И segment_count% 2 = 1 GROUP BY poly_id

Разбира се, светът не е плосък, макар че аз го третирах по този начин за простота. Ако искате това да работи за всички случаи, трябва да ограничите търсенето до определено разстояние и да преведете координатите, така че търсенето да не се пресича на 180 градуса дължина.



Може Да Се Интересувате

Роуд Айлънд Mini Maker Faire тази събота, 11 октомври

Роуд Айлънд Mini Maker Faire тази събота, 11 октомври


Това звучи като ... когато Тамагочи плаче

Това звучи като ... когато Тамагочи плаче


Как да: Батик и Rit боя стена висящи

Как да: Батик и Rit боя стена висящи


DIY Game Boy Pocket Използвайки Raspberry Pi

DIY Game Boy Pocket Използвайки Raspberry Pi