-
Notifications
You must be signed in to change notification settings - Fork 3
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
Merging Sites #5
Comments
I've been meaning to publish a Nuget package, so I'll look into it a bit later. I was originally looking for a library myself and there wasn't one in C# and the closest working one was your fork. I haven't had much time to add additional features though. That said, I can always look into it. I have some extra time now. Arbitrary site merging sounds like an interesting feature. I can see how there could be some complications. Besides all the Voronoi rules no longer applying, there are some extra weird things that can happen. For example, after merging the average site location could be outside its cell edges. But I can see how it would be useful for certain applications, so it's likely a useful addition. Basically, you wouldn't need to make your own "regions" of cells, rather ask the plane to combine cells according to the "region's" rules. I'll have to think about the actual algorithm to implement this. |
The nuget package owuld be great. I am not expecting you to add the merging feature (Although that would be great since I am not confident I could figure it out myself!) since I am not sure it would be "on-topic" to this library for the reasons you mention above. I am fiddling with the result now with niaive approach to see if I can get it working. For my particular use-case the combined regions are just converted to polygons for geospatial work where the only thing that is done is "Is point in polygon" type stuff where the only wrinkle would be support polygons with holes in them although this is a nice-to-have. The Voronoi generation is just a stepping stone after which most information is discarded. I am more than willing to sponsor this development if need be since it may not be core to the library's goal. |
I wrote a basic site merge algorithm. It's barely tested so use at your own risk! I have not checked that all the edges and neighbours are correct after merging. But it seems the basic logic works. I will test it some more later and verify other cases (and write documentation). |
Fantastic, thank you, I particularly like the idea of having a query callback that allows the merge decision to live outside this code. I shall play with it this evening. |
Thanks for looking at this. I have had a very small play with it. I am using it in this project which may be handy for experimenting visually: https://github.com/rurounijones/frontline . My first comment is that the fact we have to choose which site to merge into I have a visualiser in the repo so here are some screenshots of the default test I have when I was trying to work on this myself but now running the code you wrote. Here is a Voronoi with the individual sites. The white labels are the points, the red/blue points are the site origin. You can see there is one red and a bunch of blue. With a successful merge the entire map within the boundaries should be blue apart from that red corner square bottom left. You can generate this by clicking the You can generate these by clicking the Here is the result using Here is the result using All the relevant code lives in https://github.com/rurounijones/frontline/blob/main/FrontLine/Generator.cs I haven't had time to look into this in detail so it is possible the issue lies with me, I will continue looking into it during the week when I can. |
Thanks for checking it out!
The reason I do this is because Imagine I have a Granted, this is not important if you don't assign distinguishable data to your sites or don't keep any external references besides iterating them from the algorithm. Perhaps I can add an overload method that is happy with just a yes/no decision.
I will l check it out. As I mentioned, I haven't tested neighbours or points being correct. It's most likely a bug in the algorithm. |
Good point on the fact that the sites may have extra information, I am infact using a class that inherits from Also thanks for testing it with my little app! I shall give it a thorough going over and put it through its paces. |
I am going through the tests in the test package and it looks like there may still be some niggles as sone of the tests in the test package are failing: Note: I am assuming, based on earlier discussion, that merging to site 1 or 2 should have no effect on the end result in terms of just the resulting polygons with no site properties.
However I think I need to modify the visualizer to make it easier to add points and sample sets of sites for visualisation. So if you prefer to wait until I have done that then no worries. |
Ohhh, yeah, that actually makes sense. I don't actually insert merged edges in any sensible order. But asking for the points iterates through the edges as if they are sorted. This is why it went to I guess I need to insert edges in the right order to the merged site if I want to preserve this "accidentally sorted" property. However, the proper way is supposed to be to use I'll check it out a bit later. |
Makes sense. I have updated https://github.com/rurounijones/frontline with some more scenarios that show issues and allow you to add your own using Samples.cs for easier visualisation. Not sure if useful or not to you but never know. |
I've checked it out. It's definitely the edges that are incorrect. I'm thinking out loud next. I'm afraid, this has turned out to be a much more complicated problem than I even anticipated and I definitely expected issues. The problem is that the original tessellation algorithm's output makes no guarantee about the order of the site's edges and points. It just so happens to be ordered. I also never assumed it was when adding border edges or doing anything with the results. And the additional border edges that I add don't have the edge start/end points in the "expected" order - after all, you would use the points list if you need actual vertices and use the clockwise-sorted list if you need them in the right order. But now I am trying to merge the sites assuming that the edges make a "loop" both in the right order and the edges are in the right orientation. This quickly breaks, as I end up with sites that have edges in all sorts of combinations. Trying to combine the edge lists is an adventure in itself. But once merged, I can no longer rely on anything being ordered - edges, points, etc. And I cannot use any of the clockwise sorted results, because they just don't work for non-Voronoi geometry. Basically, I end up with sites like this: I'm not even sure how to do this. I am guessing that first I need to change the border edge logic to be in the right orientation. Then I should be able to set the assumption that the edges and points actually are always in the right order, if not clockwise or starting from a particular angle. (I mean, I don't know if that's even true for Fortune's algorithm for all cases - I need to actually verify that. (And I don't even want to think what happens if I change the algorithm or add any alternative ones...)) And from there, any changes I make, I can follow the rule of receiving sorted stuff and returning sorted stuff in the same way. But the border generation touches the main algorithm though, so I need to be way more careful at this point because I could break everything. My unit tests don't ever test the orientation of edges, because it was never defined, so I need to add all the new assumptions to it. At that point, the clockwise collections are at best redundant and at worse incorrect for non-Voronoi site shapes. I guess having the correct border edge order is something one might expect even from the base algorithm. I didn't really think of this before - the original library never closed the borders. I tried adding this as part of to the main algorithm, but I just couldn't figure it out. I've even tried to understand Fortune's and/or write my own, but that's been put off for now. I'll look into this, but I can make no guarantee about getting any of this done in a timely manner. I didn't expect this to get quite so convoluted. I'll try to at least get the border edges sorted correctly. |
Thanks for the work so far. I think I may be able to get my use-case working well enough based on what you have although it may not be something generalisable. I will leave this issue open to report my progress unless you prefer to close it. |
I believe I have gotten it working for my specific requirements although I think I am doing it very inefficiently which is good enough for my use-case. There are still errors occuring when I put it up against a real scenario that I need to work out, but for the examples it seems things are on the right track. I shall put some code up when I get a moment. |
Here are the changes I made, they may not be generalisable or efficient enough to merge into this library directly but it works in my use-case: rurounijones/frontline@c8145c9#diff-0e3ab512dd687bc3de6fe30f575cfcc42dab89871a7f7b893e7c205a2eb6712cR152-R196 Basically I ignore the cell direction and just look at points that match an existing point then look for the other end. I won't close this issue in case you want to do anything with it, but I am happy with the current situation. Thank you very much for the work you did on this. |
Glad you got it working.
Yeah, that's basically what has to be done, because the edges are not sorted. It's what I have to do internally too and I tried doing it efficiently, but as I mentioned I realized the original cell edges weren't sorted. So I'd have to do what you are doing and just ignore any order and manually construct the sorted list. Of course, this may get really slow for large planes.
I'll keep it open. Since there's a bit more work than I expected to do this internally, I would need a bit more time to fix some of the things (notably, original edge order), so I'll get back to this at some later point. |
Great to see this fork and all the improvements on it. I think, with all the stuff you have added, that this could be the turn-key solution I am looking for where my lack of brain-power is covered by the library itself 😆
My use-case is to generate a Voronoi Diagram then merge all sites with neighours that share an arbitrary property.
So having said all that; A Nuget package would be great😀
The text was updated successfully, but these errors were encountered: