Merging Sites

[rurounijones]

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😀

[RudyTheDev]

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.

[rurounijones]

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.

[RudyTheDev]

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).

[rurounijones]

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.

[rurounijones]

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 MergeToSite1 vs MergeToSite2 confuses me as I expected that it would have been only merge or no merge and then the algorithm handles everything else in terms of merging sites and their metadata things like neighbours so that we can continue merging.

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 Generate Unit Polygons button

You can generate these by clicking the Generate Frontlines button

Here is the result using MergeToSite1

Here is the result using MergeToSite2

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.

[RudyTheDev]

Thanks for checking it out!

My first comment is that the fact we have to choose which site to merge into MergeToSite1 vs MergeToSite2 confuses me as I expected that it would have been only merge or no merge and then the algorithm handles everything else in terms of merging sites and their metadata things like neighbours so that we can continue merging.

The reason I do this is because VoronoiSite isn't a sealed class - you can derive from it and add your own data. Even if you don't derive from it, it's not against the design to just reference it.

Imagine I have a class MyVoronoiSite : VoronoiSite and it has an int oilAmount. When it comes time to merge two sites, you might choose to keep the site with the higher oilAmount. Futher imagine I have some cashed List<MyVoronoiSite> oilSites - I would need to remove the merged entry.

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 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.

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.

[RudyTheDev]

It was a bug in algorithm - I never actually updated the edges for the new sites. I pushed an update with the fix. I added basic test checks for the few tests I have and it seems to work. I checked out your project and it seems to now work for this scenario:

Note that there are "extra points" here, because the edges are collinear with a pair of matching vertices. This would be especially noticeable at the plane borders. The algorithm doesn't merge the edges that happen to be like that. It might be worth adding a feature to do this. Although, this shouldn't really impact anything logically - it might be undesirable visually.

[rurounijones]

Good point on the fact that the sites may have extra information, I am infact using a class that inherits from VoronoiSite but I didn't think about that use-case.

Also thanks for testing it with my little app! I shall give it a thorough going over and put it through its paces.

[rurounijones]

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.

                new UnitSite(1, 1, CoalitionId.RedFor),
                new UnitSite(2, 2, CoalitionId.BlueFor),
                new UnitSite(1, 2, CoalitionId.BlueFor),
                new UnitSite(2, 1, CoalitionId.BlueFor)

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.

[RudyTheDev]

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 1.5,1.5 then "back" to 0,1.5. I never even considered this, but I guess the original Fortune's algorithm "accidentally" produces the edge list in a "correct" order. So it looks like asking for points always produces a sorted list - but that is actually not a true assumption.

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 ClockwiseCell and ClockwisePoints. However, if you perform site merging, then sorting no longer works, because sorting depends on some Voronoi plane properties, namely that points have ordered rotation - that is, they go around the center, which may not be true once you start merging sites.

I'll check it out a bit later.

[rurounijones]

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.

[RudyTheDev]

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.

[rurounijones]

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.

[rurounijones]

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.

[rurounijones]

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.

[RudyTheDev]

Glad you got it working.

Basically I ignore the cell direction and just look at points that match an existing point then look for the other end.

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 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.

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.