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.

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

Invert s2 loop instead of rebuilding #4782

Merged
merged 2 commits into from
Mar 16, 2020
Merged

Conversation

sams96
Copy link
Contributor

@sams96 sams96 commented Feb 14, 2020

I was using loopFromPolygon in my own project and I noticed a weird issue with some polygons which results in the contains query always returning true, using Invert instead of rebuilding the loop here seems to fix it. To reproduce, open a clean dgraph instance and push this mutation:

{
  "set":[
    {
      "name": "Sudan",
      "geometry":{"type":"Polygon","coordinates":[[[24.567369,8.229188],[23.805813,8.666319],[23.459013,8.954286],[23.394779,9.265068],[23.55725,9.681218],[23.554304,10.089255],[22.977544,10.714463],[22.864165,11.142395],[22.87622,11.38461],[22.50869,11.67936],[22.49762,12.26024],[22.28801,12.64605],[21.93681,12.58818],[22.03759,12.95546],[22.29658,13.37232],[22.18329,13.78648],[22.51202,14.09318],[22.30351,14.32682],[22.56795,14.94429],[23.02459,15.68072],[23.88689,15.61084],[23.83766,19.58047],[23.85,20],[25,20.00304],[25,22],[29.02,22],[32.9,22],[36.86623,22],[37.18872,21.01885],[36.96941,20.83744],[37.1147,19.80796],[37.48179,18.61409],[37.86276,18.36786],[38.41009,17.998307],[37.904,17.42754],[37.16747,17.26314],[36.85253,16.95655],[36.75389,16.29186],[36.32322,14.82249],[36.42951,14.42211],[36.27022,13.56333],[35.86363,12.57828],[35.26049,12.08286],[34.83163,11.31896],[34.73115,10.91017],[34.25745,10.63009],[33.96162,9.58358],[33.97498,8.68456],[33.963393,9.464285],[33.824963,9.484061],[33.842131,9.981915],[33.721959,10.325262],[33.206938,10.720112],[33.086766,11.441141],[33.206938,12.179338],[32.743419,12.248008],[32.67475,12.024832],[32.073892,11.97333],[32.314235,11.681484],[32.400072,11.080626],[31.850716,10.531271],[31.352862,9.810241],[30.837841,9.707237],[29.996639,10.290927],[29.618957,10.084919],[29.515953,9.793074],[29.000932,9.604232],[28.966597,9.398224],[27.97089,9.398224],[27.833551,9.604232],[27.112521,9.638567],[26.752006,9.466893],[26.477328,9.55273],[25.962307,10.136421],[25.790633,10.411099],[25.069604,10.27376],[24.794926,9.810241],[24.537415,8.917538],[24.194068,8.728696],[23.88698,8.61973],[24.567369,8.229188]]]}
    }
  ]
}

Which uses the 1:110m outline of Sudan from http://naturalearthdata.com/. Then the query:

{
  broken(func: contains(geometry, [0, 0])) {name}
}

Using any coordinates will always return that node.


This change is Reviewable

@sams96 sams96 requested review from manishrjain and a team as code owners February 14, 2020 22:31
@pawanrawal pawanrawal self-requested a review February 24, 2020 09:38
Copy link
Contributor

@pawanrawal pawanrawal left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for your contribution @sams96. Could you please add a test case for this that was failing earlier and now passes after your change?

Reviewable status: 0 of 1 files reviewed, all discussions resolved (waiting on @manishrjain and @pawanrawal)

To show that inverting the loop makes a difference.
I was using loopFromPolygon in my own project and I noticed a weird
issue with some polygons which results in the contains query always
returning true, using Invert instead of rebuilding the loop here seems
to fix it.
@sams96
Copy link
Contributor Author

sams96 commented Feb 24, 2020

@pawanrawal Test added, not sure if I need to add some kind of legal statement for the test data I added though, It comes from natrual-earth-vector and is public domain so I think it's ok.

Copy link
Contributor

@pawanrawal pawanrawal left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @sams96. Its been a long time since I looked at this piece of code so please give me a couple of days to get back to you.

Reviewable status: 0 of 3 files reviewed, all discussions resolved (waiting on @manishrjain)

@sams96
Copy link
Contributor Author

sams96 commented Feb 26, 2020

@pawanrawal cool thanks. I've noticed through working on some of my own projects that creating the s2 loops is very slow, I just managed to get a >10x >100x speed increase of contains queries by using geom's IsPointInRing function. If there's an easy way to cache the s2 loops I expect that will be generally quicker but otherwise it seems to be better to avoid using it. Geom doesn't have functions for most of the rest of the geo queries but it might be worth using where possible, and I might try to implement some of the other functions into geom myself.

Edit: 10x -> 100x

@CLAassistant
Copy link

CLA assistant check
All committers have signed the CLA.

1 similar comment
@CLAassistant
Copy link

CLA assistant check
All committers have signed the CLA.

@sams96
Copy link
Contributor Author

sams96 commented Mar 6, 2020

Thanks @CLAassistant

Copy link
Contributor

@manishrjain manishrjain left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@pawanrawal Are you reviewing this? Looks like a nice PR.

Reviewable status: 0 of 3 files reviewed, all discussions resolved (waiting on @manishrjain)

@manishrjain manishrjain merged commit 0832fc1 into hypermodeinc:master Mar 16, 2020
@manishrjain
Copy link
Contributor

Went ahead and accepted the PR, considering @pawanrawal is busy with other things. Thanks for your contribution, @sams96 . Happy to accept other PRs related to geo stuff, if you're interested in contributing.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Development

Successfully merging this pull request may close these issues.

4 participants