Update polygone center algorithm
As mentioned in #4965 fixed the awkward placement of some of the quest marker in center of polygons. The change is mostly contained in a single folder.
Fixes #4965
I'm confused on how those appeared, I'm conviced I checked there were no unexpected changes so I don't know how they are here. I'll give it a look to fix all that next week, I'm still way too busy for now to work on that this week.
I'll give a look into everything you mentionned, I admit the maths kinda melted my brain and I don't remember everything I did, I'll give a look into that as well and keep you posted. Thank you for the feedback
There are still unrelated changes. You can check for yourself (latest) in the "Files Changed" tab. Maybe put your code into a new PR instead of trying to revert all those changes made in that fork-repo?
[...] * the place where you ported it certainly had test cases, right? These should be ported, too * where is the difference between a `Point` and a `LatLon`? Do we need the `Point`? * why is the extra data structure `Polygon` needed? Can't it operate on a `List<List<LatLon>>`, just like for example `List<List<LatLon>>.measuredMultiPolygonArea` does? For consistency within the project * PriorityQueue: I am not familiar with it. It would be nice if there was a doc comment that explained what it should do. What are you trying to do? `poll()` for example reads like it returns the first element, but then removes the last element and replaces the first element with it, only to basically bubble-sort that element back to the end of the list?? If I understood that right, it sounds _very_ imperformant!
Okay so I've looked a bit into it and am now able to come back to you.
-
I'll look deeper into tests now and will keep you posted about it.
-
Here, there is no actual difference between a
Pointand aLatLon. So no, we do not need thePoint. However, as you mentionned it would be a good thing to make this as an asset available to whomever it may concern, and in this context, using aPointmakes more sense. So I developed it with this in mind, so it will be was easier to export later and have minimal changes here to go from direct implementation to a call of the library. -
Similar to previous point, I expect to do an update later to leave as many things as possible in the library and restore that consistancy. It's also why I've put everything in a separate folder, to be sure I won't forget anything (I or whoever would like to do it, I'm don't mind sharing that work)
-
I admit I wasn't familiar with the concept before, so I redid some research about it and unless I missed something in my implementation, it should work as intended. The idea is to use a heap, but sort it before pulling datas from it. So you treat the biggest values first. Which what we need in the polylabel algorithm. About it's complexity, I'm not an expert in maths so I can't give you a full detailed evidence about it, but according to what I checked it should be a O(log(n)), so nothing alarming.
If you have anything more on your mind while I look into those tests, feel free to ask me, we're less available than at the start, but we didn't forget nor give up on StreetComplete !