Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

geom2graph tool loses some edges #87

Open
Notgnoshi opened this issue Apr 18, 2021 · 5 comments
Open

geom2graph tool loses some edges #87

Notgnoshi opened this issue Apr 18, 2021 · 5 comments
Labels
bug Something isn't working C++ graph Geometry type tool a new tool, or an enhancement to an existing one

Comments

@Notgnoshi
Copy link
Owner

Take the following linestring.

LINESTRING (642.0893565886494 -132.868231326413, 611.9583329777174 -92.96683515839021, 562.3371984442772 -99.11036896347433, 592.4682220552086 -139.011765131497, 572.9781111326996 -185.0566951046037, 523.3569765992592 -191.2002289096877, 493.2259529883277 -151.2988327416649, 542.8470875217681 -145.155298936581, 562.3371984442772 -99.11036896347434, 512.7160639108369 -105.2539027685583, 482.5850402999055 -65.35250660053562, 532.2061748333458 -59.20897279545168, 551.6962857558549 -13.16404282234498, 521.5652621449235 26.73735334567774, 471.9441276114831 20.5938195405938, 502.0751512224144 -19.30757662742892, 482.5850402999054 -65.35250660053553, 432.963905766465 -71.49604040561947, 402.8328821555336 -31.59464423759677, 452.4540166889741 -25.45111043251287, 471.944127611483 20.59381954059384, 441.8131040005518 60.49521570861653, 392.1919694671113 54.35168190353261, 422.3229930780427 14.45028573550988, 402.8328821555336 -31.59464423759673, 372.7018585446023 8.306751930425987, 323.0807240111619 2.163218125342081, 353.2117476220933 -37.73817804268065, 333.7216366995842 -83.78310801578723, 284.1005021661439 -89.92664182087121, 253.9694785552125 -50.02524565284849, 303.5906130886528 -43.88171184776456, 323.0807240111619 2.163218125342079, 273.4595894777215 -3.980315679741835, 243.3285658667901 35.92108048828082, 292.9497004002306 42.06461429336476, 312.4398113227396 88.10954426647139, 282.3087877118082 128.0109404344941, 232.6876531783679 121.8674066294102, 262.8186767892992 81.96601046138746, 243.3285658667901 35.92108048828083, 213.1975422558588 75.82247665630354, 163.5764077224185 69.67894285121963, 193.7074313333498 29.77754668319692, 174.2173204108408 -16.26738328990969, 124.5961858774003 -22.41091709499365, 94.46516226646898 17.49047907302905, 144.0862967999094 23.63401287811298, 163.5764077224185 69.67894285121959, 133.4453841114872 109.5803390192422, 83.82424957804677 103.4368052141583, 113.955273188978 63.53540904613569, 94.46516226646898 17.49047907302905, 44.84402773302858 11.34694526794512, 14.7130041220973 51.24834143596773, 64.3341386555377 57.39187524105166, 83.82424957804675 103.4368052141582, 34.20311504460634 97.29327140907432, 4.072091433674963 137.194667577097, 53.69322596711535 143.3382013821809, 73.1833368896244 189.3831313552876, 43.05231327869304 229.2845275233103, -6.568821254747306 223.1409937182263, 23.56220235618402 183.2395975502036, 4.072091433675 137.194667577097, -15.41801948883404 91.14973760399045, -65.03915402227445 85.00620379890651, -45.54904309976537 131.0511337720131, -75.68006671069671 170.9525299400358, -125.3012012441371 164.8089961349519, -144.7913121666462 118.7640661618453, -95.17017763320578 124.9075999669292, -65.03915402227445 85.00620379890651, -114.6602885557149 78.86266999382258, -134.150399478224 32.81774002071592, -84.52926494478355 38.9612738257999, -54.39824133385221 -0.9401223422228059, -73.88835225636133 -46.98505231532945, -123.5094867898019 -53.12858612041348, -104.0193758672927 -7.083656147306765, -134.150399478224 32.81774002071593, -183.7715340116645 26.6742062156319, -203.2616449341736 -19.37072375747469, -153.6405104007332 -13.22718995239079, -123.5094867898019 -53.12858612041348, -142.9995977123109 -99.17351609352005, -192.6207322457515 -105.3170498986041, -173.1306213232422 -59.27211992549738, -203.2616449341735 -19.3707237574747, -222.7517558566828 -65.41565373058143, -272.3728903901228 -71.55918753566503, -252.8827794676142 -25.51425756255874, -283.0138030785455 14.38713860546395, -332.6349376119855 8.243604800380334, -352.1250485344946 -37.80132517272632, -302.5039140010541 -31.65779136764236, -272.3728903901228 -71.55918753566503, -302.5039140010541 -31.65779136764236, -352.1250485344946 -37.80132517272632, -321.9940249235633 -77.70272134074901, -341.4841358460723 -123.7476513138557, -391.1052703795129 -129.8911851189396, -421.2362939904442 -89.98978895091693, -371.6151594570036 -83.84625514583296, -352.1250485344946 -37.80132517272632, -401.746183067935 -43.94485897781028, -431.8772066788663 -4.043462809787615, -382.2560721454259 2.100070995296354, -362.7659612229167 48.14500096840301, -392.8969848338481 88.04639713642568, -442.5181193672885 81.90286333134172, -412.3870957563572 42.00146716331905, -431.8772066788663 -4.043462809787599, -451.3673176013755 -50.08839278289424, -500.988452134816 -56.23192658797824, -481.4983412123068 -10.18699661487157, -511.6293648232382 29.71439955315114, -561.2504993566786 23.57086574806712, -580.7406102791875 -22.47406422503942, -531.1194757457472 -16.33053041995554, -500.988452134816 -56.23192658797824, -531.1194757457472 -16.33053041995555, -580.7406102791875 -22.47406422503943, -550.6095866682563 -62.37546039306211, -570.0996975907651 -108.4203903661685, -589.5898085132742 -154.4653203392752, -639.2109430467148 -160.6088541443592, -589.5898085132742 -154.4653203392752)

Screenshot from 2021-04-18 13-33-33

when running this LINESTRING through the geom2graph tool, it loses some of the edges.

./tools/geom2graph/build/src/geom2graph --tolerance 1e-3 -i /tmp/test.wkt |  # Use geom2graph round trip to simplify geometries
./tools/geom2graph/build/src/geom2graph --tolerance 1e-3 --graph2geom -o /tmp/test-after.wkt

this produces

POLYGON ((562.3371984442772 -99.11036896347433, 592.4682220552086 -139.011765131497, 572.9781111326996 -185.0566951046037, 523.3569765992592 -191.2002289096877, 493.2259529883277 -151.2988327416649, 542.8470875217681 -145.155298936581, 562.3371984442772 -99.11036896347433))
POLYGON ((532.2061748333458 -59.20897279545168, 482.5850402999055 -65.35250660053562, 502.0751512224144 -19.30757662742892, 471.9441276114831 20.5938195405938, 521.5652621449235 26.73735334567774, 551.6962857558549 -13.16404282234498, 532.2061748333458 -59.20897279545168))
POLYGON ((502.0751512224144 -19.30757662742892, 482.5850402999055 -65.35250660053562, 432.963905766465 -71.49604040561947, 402.8328821555336 -31.59464423759677, 452.4540166889741 -25.45111043251287, 471.9441276114831 20.5938195405938, 502.0751512224144 -19.30757662742892))
POLYGON ((471.9441276114831 20.5938195405938, 452.4540166889741 -25.45111043251287, 402.8328821555336 -31.59464423759677, 422.3229930780427 14.45028573550988, 392.1919694671113 54.35168190353261, 441.8131040005518 60.49521570861653, 471.9441276114831 20.5938195405938))
POLYGON ((323.0807240111619 2.163218125342081, 353.2117476220933 -37.73817804268065, 333.7216366995842 -83.78310801578723, 284.1005021661439 -89.92664182087121, 253.9694785552125 -50.02524565284849, 303.5906130886528 -43.88171184776456, 323.0807240111619 2.163218125342081))
POLYGON ((292.9497004002306 42.06461429336476, 243.3285658667901 35.92108048828082, 262.8186767892992 81.96601046138746, 232.6876531783679 121.8674066294102, 282.3087877118082 128.0109404344941, 312.4398113227396 88.10954426647139, 292.9497004002306 42.06461429336476))
POLYGON ((163.5764077224185 69.67894285121963, 193.7074313333498 29.77754668319692, 174.2173204108408 -16.26738328990969, 124.5961858774003 -22.41091709499365, 94.46516226646898 17.49047907302905, 144.0862967999094 23.63401287811298, 163.5764077224185 69.67894285121963))
POLYGON ((163.5764077224185 69.67894285121963, 144.0862967999094 23.63401287811298, 94.46516226646898 17.49047907302905, 113.955273188978 63.53540904613569, 83.82424957804677 103.4368052141583, 133.4453841114872 109.5803390192422, 163.5764077224185 69.67894285121963))
POLYGON ((113.955273188978 63.53540904613569, 94.46516226646898 17.49047907302905, 44.84402773302858 11.34694526794512, 14.7130041220973 51.24834143596773, 64.3341386555377 57.39187524105166, 83.82424957804677 103.4368052141583, 113.955273188978 63.53540904613569))
POLYGON ((53.69322596711535 143.3382013821809, 4.072091433674963 137.194667577097, 23.56220235618402 183.2395975502036, -6.568821254747306 223.1409937182263, 43.05231327869304 229.2845275233103, 73.1833368896244 189.3831313552876, 53.69322596711535 143.3382013821809))
POLYGON ((-45.54904309976537 131.0511337720131, -65.03915402227445 85.00620379890651, -95.17017763320578 124.9075999669292, -144.7913121666462 118.7640661618453, -125.3012012441371 164.8089961349519, -75.68006671069671 170.9525299400358, -45.54904309976537 131.0511337720131))
POLYGON ((-134.150399478224 32.81774002071592, -84.52926494478355 38.9612738257999, -54.39824133385221 -0.9401223422228059, -73.88835225636133 -46.98505231532945, -123.5094867898019 -53.12858612041348, -104.0193758672927 -7.083656147306765, -134.150399478224 32.81774002071592))
POLYGON ((-134.150399478224 32.81774002071592, -104.0193758672927 -7.083656147306765, -123.5094867898019 -53.12858612041348, -153.6405104007332 -13.22718995239079, -203.2616449341736 -19.37072375747469, -183.7715340116645 26.6742062156319, -134.150399478224 32.81774002071592))
POLYGON ((-153.6405104007332 -13.22718995239079, -123.5094867898019 -53.12858612041348, -142.9995977123109 -99.17351609352005, -192.6207322457515 -105.3170498986041, -173.1306213232422 -59.27211992549738, -203.2616449341736 -19.37072375747469, -153.6405104007332 -13.22718995239079))
POLYGON ((-252.8827794676142 -25.51425756255874, -272.3728903901228 -71.55918753566503, -302.5039140010541 -31.65779136764236, -352.1250485344946 -37.80132517272632, -332.6349376119855 8.243604800380334, -283.0138030785455 14.38713860546395, -252.8827794676142 -25.51425756255874))
POLYGON ((-352.1250485344946 -37.80132517272632, -321.9940249235633 -77.70272134074901, -341.4841358460723 -123.7476513138557, -391.1052703795129 -129.8911851189396, -421.2362939904442 -89.98978895091693, -371.6151594570036 -83.84625514583296, -352.1250485344946 -37.80132517272632))
POLYGON ((-382.2560721454259 2.100070995296354, -431.8772066788663 -4.043462809787615, -412.3870957563572 42.00146716331905, -442.5181193672885 81.90286333134172, -392.8969848338481 88.04639713642568, -362.7659612229167 48.14500096840301, -382.2560721454259 2.100070995296354))
POLYGON ((-481.4983412123068 -10.18699661487157, -500.988452134816 -56.23192658797824, -531.1194757457472 -16.33053041995554, -580.7406102791875 -22.47406422503942, -561.2504993566786 23.57086574806712, -511.6293648232382 29.71439955315114, -481.4983412123068 -10.18699661487157))
LINESTRING (642.0893565886494 -132.868231326413, 611.9583329777174 -92.96683515839021)
LINESTRING (611.9583329777174 -92.96683515839021, 562.3371984442772 -99.11036896347433)
LINESTRING (-589.5898085132742 -154.4653203392752, -639.2109430467148 -160.6088541443592)
LINESTRING (-570.0996975907651 -108.4203903661685, -589.5898085132742 -154.4653203392752)
LINESTRING (-550.6095866682563 -62.37546039306211, -570.0996975907651 -108.4203903661685)
LINESTRING (-580.7406102791875 -22.47406422503942, -550.6095866682563 -62.37546039306211)

which, when rendered, looks like

Screenshot from 2021-04-18 13-36-57
@Notgnoshi Notgnoshi added bug Something isn't working tool a new tool, or an enhancement to an existing one C++ geometry labels Apr 18, 2021
@Notgnoshi
Copy link
Owner Author

Here are more test cases 😢

example-9-after.txt
example-9-before.txt
example-10-after.txt
example-10-before.txt

@Notgnoshi Notgnoshi mentioned this issue Jun 6, 2021
Open
@Notgnoshi Notgnoshi mentioned this issue Jun 20, 2021
Closed
@Notgnoshi Notgnoshi pinned this issue Jan 9, 2022
@Notgnoshi Notgnoshi mentioned this issue Feb 21, 2022
Closed
@Notgnoshi Notgnoshi added graph Geometry type and removed geometry labels Feb 21, 2022
@Notgnoshi Notgnoshi moved this to Up next in Generative Art Nov 27, 2022
@Notgnoshi
Copy link
Owner Author

Here's another problem.

Given a graph:

0	POINT(0 0)
1	POINT(1 0)
2	POINT(2 0)
3	POINT(3 0)
4	POINT(0 1)
5	POINT(1 1)
6	POINT(2 1)
7	POINT(3 1)
8	POINT(0 2)
9	POINT(1 2)
10	POINT(2 2)
11	POINT(3 2)
12	POINT(0 3)
13	POINT(1 3)
14	POINT(2 3)
15	POINT(3 3)
#
0	1
0	3
1	2
1	4
2	5
3	6
3	2
3	4
4	5
4	7
5	8
6	9
6	5
6	7
7	8
9	8
9	10
10	11
10	7
11	8
12	11
12	9

The geom2graph output is empty:

geom2graph --graph2geom --log-level DEBUG
INFO - Converting graph to geometries...
INFO - Reading graph...
DEBUG - Adding node POINT (0 0) at index 0
DEBUG - Adding node POINT (1 0) at index 1
DEBUG - Adding node POINT (2 0) at index 2
DEBUG - Adding node POINT (3 0) at index 3
DEBUG - Adding node POINT (0 1) at index 4
DEBUG - Adding node POINT (1 1) at index 5
DEBUG - Adding node POINT (2 1) at index 6
DEBUG - Adding node POINT (3 1) at index 7
DEBUG - Adding node POINT (0 2) at index 8
DEBUG - Adding node POINT (1 2) at index 9
DEBUG - Adding node POINT (2 2) at index 10
DEBUG - Adding node POINT (3 2) at index 11
DEBUG - Adding node POINT (0 3) at index 12
DEBUG - Adding node POINT (1 3) at index 13
DEBUG - Adding node POINT (2 3) at index 14
DEBUG - Adding node POINT (3 3) at index 15
INFO - Finished reading 16 nodes
INFO - Read graph with 16 nodes
INFO - Read 22 edges from graph
INFO - Polygonizing graph...
INFO - Got 0 polygons and 0 dangles.

@Notgnoshi
Copy link
Owner Author

First step - try updating to a recent Geos release? It appears to be a bug in the Polygonizer, and not in the graph parsing...

@Notgnoshi Notgnoshi mentioned this issue Mar 31, 2023
Open
Notgnoshi added a commit that referenced this issue Apr 7, 2023
@Notgnoshi
Add missing data test
3c11270 
Reproduces the failure from [1], which seems to be because the graph was
not correctly noded, which is one of the requirements to use the Geos
Polygonizer.

[1] #87
@Notgnoshi
Copy link
Owner Author

First step - try updating to a recent Geos release? It appears to be a bug in the Polygonizer, and not in the graph parsing...

#154 does not fix this bug.

image

Notgnoshi added a commit that referenced this issue Apr 7, 2023
@Notgnoshi
Add missing data test
844c5f6 
Reproduces the failure from [1], which seems to be because the graph was
not correctly noded, which is one of the requirements to use the Geos
Polygonizer.

[1] #87
@Notgnoshi Notgnoshi moved this from Up next to TODO in Generative Art Apr 10, 2023
@Notgnoshi
Copy link
Owner Author

This is still an issue with #166

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working C++ graph Geometry type tool a new tool, or an enhancement to an existing one
Projects
Generative Art
Status: TODO
Milestone
No milestone
Development

No branches or pull requests
1 participant
@Notgnoshi