- Note taken on [2016-10-09 Du 19:06]
This spec should be updated with the part that describes when the polygon should be split with just one line, and when it should be split with two lines.There’s also some details that are pending related to rotation of the polygon in order to reduce the number of cases to be analyzed.
We have a polygon P (also known as big parcel) and the nearest road R. We get the bounding box B for P and all our searches for cutting points/lines will be confined to B. We get the points that are on the boundary and on the bounding box at the same time, we call these “extreme points” and denote them with E, and we label them with their cardinal direction.
Goal: We want to cut a corner C (also called subdivision) from P that contains the nearest-to-road point. The cut will be done using two lines, one horizontal (the green-line) and one vertical (the red-line). We want C to be of a given area A.
Now get the closest two points on E to R, and depending on them, we decide which corner to cut.
We’ll use sweeping-lines for this. Any sweeping-lines mentioned will be moving away from the corner (in other words, away from the closest road point).
In what follows, we assume the north-west corner needs to be cut.
We place an inset (a horizontal line) that will be located sqrt(A) to the south (relative to the north edge). The inset is positioned there because we anticipate the target area to have a rectangular shape.
If the area above the inset (the one we aim for) is larger than our target, we split the polygon, take the upper half and use another sweeping (the red-line) line that goes from west to east, to find another cutting line that allows us to get to target area.
If the area above the inset is insufficient (below the target area), we search for a better position for it, using binary search, along the north-south direction.
Additional details: The way the cut search works, using the inset, is such that we avoid getting thin horizontal strips when our initial polygon is a square/rectangle (and it is expected to be a square in the vast majority of cases).
Details about corner cases (other than NW which was covered above):
- NE corner: green-line goes north->south and red-line goes east->west
- SE corner: green-line goes south->north and red-line goes east->west
- SW corner: green-line goes south->north and red-line goes west->east
So the green and red-lines always move away from the corner.
SELECT
name, way
FROM planet_osm_polygon
WHERE tags->'leisure'='park'
AND name LIKE '%Herăstrău%'
ORDER BY ST_Area(way) DESC
LIMIT 1;| Parcul Herăstrău | 010300002031BF0D0001000000A4000000713D0AF7CC254641F6285CCF30225541AE47E1BACE254641B81E852B3D2255411F85EB71D4254641666666464522554152B81EE5DB254641AE47E1BA462255410AD7A370F2254641713D0A174A22554185EB51F8192646413D0AD7434F225541E17A148E1F2646417B14AE474D2255411F85EBF12C264641F6285C4F4E225541295C8F2237264641333333134F2255410AD7A3104F264641E17A148E532255413333335367264641F6285C5F582255415C8FC2D582264641EC51B86E5F22554152B81E259E2646415C8FC2E567225541D7A370BDAA264641E17A147E6C225541B81E85CBBB26464148E17A7475225541713D0A57CC264641CDCCCC1C802255413D0AD723E4264641F6285CCF8D225541D7A370DDE42646413D0AD7D3902255417B14AEE7E826464185EB5158942255410AD7A3B0EB2646418FC2F56898225541000000E0F3264641AE47E14A98225541C3F528BCF52646413D0AD713992255418FC2F5E8F3264641295C8F229B225541A4703D6AF3264641C3F5281C9D2255411F85EB1100274641000000F0A7225541000000E005274641CDCCCCECA822554185EB515806274641D7A3702DAC225541D7A370BD0B27464114AE4711B0225541B81E852B132746415C8FC2C5B6225541C3F5287C1C274641713D0AA7BA225541F6285C4F23274641295C8F82BD2255419A999979272746410AD7A3B0C1225541E17A142E2E274641C3F5281CC92255419A999959402746417B14AE27DE2255417B14AEA7432746415C8FC2C5E5225541F6285C0F4827464100000080E8225541E17A14EE4B2746411F85EB71F3225541666666464E274641B81E852BF4225541D7A370DD4D274641F6285C0FF82255410AD7A3F04C274641F6285CCFFF225541000000604C27464185EB51B80B235541333333734D2746416666669614235541295C8FC246274641713D0A771823554152B81E4542274641295C8FE21F235541EC51B8BE3B2746418FC2F5682323554152B81E2541274641EC51B8CE27235541E17A142E3F2746417B14AE272F235541AE47E15A39274641F6285C5F33235541CDCCCCEC2427464152B81E853923554114AE47A11E27464148E17A243C2355417B14AE4718274641AE47E17A3E235541E17A14CE0F274641CDCCCC5C41235541000000600D274641CDCCCC7C44235541C3F528DC04274641F6285C3F48235541D7A3703D02274641D7A3707D4823554185EB5158FD2646413D0AD7F34923554148E17A74F7264641AE47E14A52235541A4703DAAF5264641EC51B81E55235541E17A146EF3264641666666D65923554185EB5158F4264641EC51B89E5E235541E17A146EF2264641AE47E1DA662355418FC2F588EB2646417B14AEE76E2355419A999959E2264641713D0A377E23554100000080D82646417B14AE4788235541295C8F42D02646417B14AEB78F235541A4703D8AC4264641D7A370AD97235541A4703D8AB72646419A9999899F235541333333B3A3264641CDCCCC8CA5235541EC51B8DE9126464152B81E35A9235541333333337E264641333333C3AB235541A4703DCA6726464166666676AE2355419A999979512646417B14AEB7B0235541AE47E1DA392646417B14AE57B1235541E17A14EE30264641000000A0AF235541D7A370DD292646410AD7A3C0AD235541C3F5289C27264641A4703D2AB0235541295C8F02382646410AD7A3F0B6235541A4703DEA552646415C8FC2D5B52355418FC2F56871264641333333D3B2235541D7A3703D8E264641F6285C0FAF2355410AD7A350A6264641AE47E14AAA235541295C8FA2C22646418FC2F558A32355415C8FC275D9264641F6285CFF9C2355415C8FC255EC264641CDCCCCFC97235541EC51B81EFB26464148E17A3494235541C3F5287C3F2746415C8FC2157F2355410AD7A3B04D27464148E17A54792355419A9999395A274641B81E85AB72235541E17A142E7B274641295C8F925C235541C3F5287C8E27464148E17AC455235541C3F5281C95274641666666C64823554185EB51F896274641295C8FF23B235541F6285C2F9F27464166666626DE2255418FC2F548A1274641000000B0C32255415C8FC2F5A22746417B14AE27AB22554185EB51B8A4274641713D0AF7922255410AD7A3D0A5274641295C8F62822255417B14AEE7A82746417B14AED764225541A4703DEAAE274641333333034E22554100000040B627464185EB51883E2255415C8FC215C0274641713D0A9730225541AE47E13ACB274641666666D6222255418FC2F508DC27464166666646152255410AD7A3F0FD274641666666E6F82155419A9999D91F2846418FC2F548DD215541295C8F222728464185EB5198D521554148E17A344828464100000020B72155411F85EB71562846419A999999AB215541AE47E15A6C2846410AD7A3809C21554166666686B3284641666666C67621554114AE4781B728464152B81E156E215541D7A3701DB728464114AE475165215541AE47E1BAB4284641E17A14EE5D215541C3F5285CAD2846415C8FC295572155411F85EBF1BB2846415C8FC2154D215541EC51B87EB1284641CDCCCCFC462155410AD7A3308B28464152B81EA53B215541C3F5287C612846413D0AD7C32F2155413D0AD7C352284641295C8FD23E2155411F85EBF15628464114AE473143215541D7A370FD4F284641C3F528FC4F215541EC51B8FE402846411F85EB717721554114AE47413A284641000000C08921554185EB51582F28464152B81EB59821554185EB51D817284641EC51B84EAB215541AE47E1FA0C2846413D0AD793B0215541B81E85EBFE2746410AD7A3F0B42155413D0AD7A3DE27464166666686BE215541F6285C4FB4274641AE47E1AAC6215541B81E85AB9D274641A4703DFACA215541EC51B89E762746417B14AE87CF2155418FC2F508542746410AD7A360D4215541D7A3709D1C274641C3F528ACCF21554114AE47A10B27464114AE4731CD215541C3F528FCFA264641F6285C4FC82155410AD7A310EA2646410AD7A3A0C2215541C3F5283CC6264641A4703D7AB9215541B81E858BB7264641A4703D8AB8215541AE47E1DAA9264641E17A14AEBB215541000000409F264641713D0A47BE215541C3F5289C942646417B14AE17C02155410AD7A3107D2646417B14AE87C1215541EC51B8BE69264641B81E859BC021554185EB5138592646413D0AD703BF215541F6285CCF41264641E17A145EBC215541F6285CAF29264641295C8F02B9215541AE47E15A18264641295C8F62B6215541D7A3703D0C2646413D0AD723B8215541C3F528FCFF2546419A9999B9BC215541F6285CCFF625464148E17A84C221554152B81EA5F42546417B14AE27CA21554100000040F625464133333313D12155417B14AE67FE2546411F85EB11DC215541C3F528BC042646415C8FC245E4215541B81E856B06264641713D0A07EA21554185EB511807264641A4703D9AF4215541295C8F4201264641A4703D2A0622554152B81E25FB25464185EB51B80E225541666666E6F525464152B81E8519225541295C8F62EC2546418FC2F5B821225541666666E6E3254641D7A3701D2622554185EB5198D8254641295C8F52272255413D0AD743CE254641C3F528AC29225541713D0AF7CC254641F6285CCF30225541 |
|---|
WITH
parcels AS (
SELECT
osm_id, name, way
FROM planet_osm_polygon
WHERE
tags->'leisure'='park'
AND name LIKE '%Herăstrău%'
LIMIT 3
), roads AS (
SELECT
osm_id, name, way
FROM planet_osm_line
WHERE tags->highway = 'motorway'
)
-- do KNN cross-join between parcels and roads
-- to get nearby roads (rn)
SELECT
DISTINCT ON (rn.osm_id)
rn.osm_id, rn.name, p.osm_id, p.name, dr
FROM parcels p
CROSS JOIN LATERAL (
SELECT
*,
-- distance to road
ST_Distance(p.way,r.way) as dr
FROM roads r
ORDER BY p.way <-> r.way
LIMIT 5
) rn;| osm_id | name | osm_id | name | dr |
|---|---|---|---|---|
| 256097200 | Autostrada A3 București - Brașov | 88337012 | Parcul Herăstrău | 3886.49711984996 |
| 284325578 | Autostrada A3 București - Brașov | 91797290 | Parcul Herăstrău | 5643.86537188825 |
| 284325581 | Autostrada A3 București - Brașov | 88337012 | Parcul Herăstrău | 4716.35617574639 |
| 284325583 | Autostrada A3 București - Brașov | 91797290 | Parcul Herăstrău | 4810.48244180351 |
| 284325584 | Autostrada A3 București - Brașov | 88337012 | Parcul Herăstrău | 4886.17496682222 |
- [X] Need to use ST_GeometryType to draw parcels and roads differently
- [X] Refactoring
- [ ] Round off coordinates to save space on the SVG.
- [X] Need to sort clock-wise to determine cardinal directions for boundary extremes and label them. This is needed so we know which corner to cut.
- [X] Need to look again at specs and write down with examples, when the red-line cut will be used.
- [X] Get green-line sweep trajectory
- [X] Find green-line
- [X] Use inset-based green-line and red-line search as described in the spec
- [X] Update the cut polygon and insert the corner in the DB
CREATE VIEW roads_by_type AS SELECT *, tags->’highway’ AS road_type FROM planet_osm_line WHERE tags ? ‘highway’;
- Note taken on [2016-10-10 Lu 18:26]
Refined spec and simplified some parts of the code. - Note taken on [2016-10-10 Lu 14:32]
Need to detail how the red-line cut works and when it’s being used. - Note taken on [2016-10-09 Du 17:52]
I noticed that the first cut would solve the problem, meaning it’s able to find the required line.After discussing with John, we agreed that a 2nd cut is actually required but only under certain conditions.