Sorting Line segments

Unity Engine
1

I have a List of line segments composed of 2 vector2d’s (start and end). But they aren’t ordered in a way that would make one continuous line.

972×919 25.5 KB

I’ve tried various sorts but I’m having trouble getting a list where the list is ordered so that the end point of i matches the start point of i+1.

I thought something like this would have worked.

coastSegments.Sort (delegate(Vector2[] v1, Vector2[] v2) {
            if (v1[1] == v2[0]) {
                return 1;
            }
            if (v1[1] != v2[0]){
                return -1;
            }
            else {
                return 0;
            }
        });

I’m trying to pass this off to Vectrosity in order to generate a continuous coastline for a map.

2

wouldn’t it be a lot easier if you sorted it out at generation of the V2’s?

3

Possibly. But I’m grabbing the list based off of a lookup table of polygons that share an edge. One side ocean and one side land. Rewriting it to accommodate this would be problematic. Which is why I want to take this list of edges and sort them so they make one continuous line.

587×592 124 KB

4

Are you sure you have no start to start or end to end connected lines? This could be why your sorting doesn’t work.
I’d do it something like this:

  • Put all segments in a pool
  • Grab a first random segment from it and start a new group of lines.
  • Go through your pool comparing each segments start and end against the last end in your current group.
  • If a match is found, remove it from the pool and add it to the curren group. Also reverse segment if needed so the matched vertex is not at the last end.
  • Repeat until no more matches are found, or if you’re back at the start.
  • If you still have segments left, make a new group and repeat.
5

I was hoping there was something elegant that I was missing. :smile:

Definitely getting there though. I’ve gotten everything written out except starting a new group when there is no connecting line. At the moment I’m just skipping that tidbit and moving onto the next segment. Which is why the line continues to the outlaying islands. Also need to pay attention to winding. The thin lines are supposed to be the ocean side.

753×751 66.3 KB

Edit:

735×741 113 KB

6

Awesome! Looks good. I’m interested in how you tackle the ocean side problem. If you allow lakes you need to grab that info from the source data. As Otherwise you would have to assume water is on the outside of the generated polygons, which is inverted for lakes, so impossible to know unless you have more data than the segments.

7

I have more data than just the segments. :stuck_out_tongue:

I’m grabbing all the data via AmitP’s implementation of a voronoi graph.

I rewrote the graph and rendering (GL lines and quads) in C#, some others rewrote the Voronoi and Deluanay it uses.
Here is the result of that: (Spacebar to regen random map)
https://1c36bc3e19de554a801fc6af0eb88d212acd4968.googledrive.com/host/0B7vPiT3iPFmKMGc1OEVqalN6VnM/Web.html

Which is all fine and good but not the aesthetic I’m going for. I want to make a random map that looks hand drawn.
Like this: Interactive Map of Middle-Earth - LotrProject

1 Like