Determining the region of a system

[Spansh]

I've recently added region names to my systems search at https://spansh.co.uk/systems however the calculation for these is "experimental" to put it nicely and "hacked together and just about works most of the time" putting it more honestly.

What I'm hoping is that we can come up with a way of reliably determining the region of a system from it's coordinates in a somewhat more accurate way.

Currently I have the galaxy partitioned into shapes which roughly map up with the regions, we can't get this information from the player journals currently. So I think we would have to stick with this method. What I'm hoping for is that we can get some substantially more accurate shapes which we can use to determine this.

Anyone have any bright ideas?

 

[marx]

I think @Orvidius 's EDAstro has the best region borders determined. I'd suggest asking him about them.

 

[MattG]

I actually started work on a project before Christmas to determine systems mathmatically but took a break because I was trying to do it from the galaxy map and it's not accurate enough to work out the coordinates so I'm going to have to travel to (some of) the boundaries. I also need to come up with an algorithm to then calculate the formula for the line based of a set of points. All do-able, but requires me being somewhere different, and I've just embarked of scanning an entire mass d sub-sector so it'll be a while before I revisit.

However, all that's actually needed is a) the centrepoint, b) the radius of the circles - I believe these will show patterns, they're clearly not arbitrary and many parts join to parts on the other side of the map, and c) the angles for the straight parts - these too will show patterns, there are lines that break and continue further down. Once the minimum angle between lines is known, it will make the others easier to determine and once the radii are known each region can be split into arches.

This does assume there are patterns, but I think they're there.

 

[Spansh]

I actually started work on a project before Christmas to determine systems mathmatically but took a break because I was trying to do it from the galaxy map and it's not accurate enough to work out the coordinates so I'm going to have to travel to (some of) the boundaries. I also need to come up with an algorithm to then calculate the formula for the line based of a set of points. All do-able, but requires me being somewhere different, and I've just embarked of scanning an entire mass d sub-sector so it'll be a while before I revisit.

However, all that's actually needed is a) the centrepoint, b) the radius of the circles - I believe these will show patterns, they're clearly not arbitrary and many parts join to parts on the other side of the map, and c) the angles for the straight parts - these too will show patterns, there are lines that break and continue further down. Once the minimum angle between lines is known, it will make the others easier to determine and once the radii are known each region can be split into arches.

This does assume there are patterns, but I think they're there.

Yes, that's one thing I forgot to mention. Currently I'm using cartesian coordinates with the curves being represented by multiple edges. However I have no problem working with polar coordinates with distance and angle (I can relatively easily convert between the two), which obviously makes much more sense and would make the actual region definitions much more accurate and smaller.

 

[Orvidius]

Yeah, those curves make this a really interesting problem. I think arcs with a radius and center might be necessary. By appearance, it looks like it's based on a center point that is somewhat north of Sagittarius-A*. (Raxxla? )

The outlines I use for my maps were hand-traced from the in-game map, and then I flew out to a few of the intersections to verify some coordinates, in order to align and scale the entire image. Unfortunately this in no way translates to an algorithm that can be used to predict region assignments by coordinates. But something similar can work, in the sense of gathering some in-game data on where those intersections are, and build up some selections of radius-bands in an algorithm.

 

[Orvidius]

Having said that, I'm working on a region-estimation in my database, based on the map image borders I've been using. This will get the region correct for the bulk of systems within it, but I can guarantee there will be many errors along the borders. Any place that the map image borders are off by even just a pixel or two, the mapping in the data will be off by 10-20 lightyears. Most of the time, the error might be larger. There's a reason I made the border lines about 200 ly thick for the map images.

 

[Orvidius]

OK, so here's some numbers from the EDSM data, matching systems up with regions using a color-map to determine region areas.

mysql> select distinct systems.region regionID,regions.name Name,count(*) systems from systems,regions where region=regions.id and deletionState=0 group by region order by region;           +----------+-----------------------------+----------+
| regionID | Name                        | systems  |
+----------+-----------------------------+----------+
|        0 | Unknown                     |      625 |
|        1 | Galactic Centre             |  1899030 |
|        2 | Empyrean Straits            |  2281625 |
|        3 | Ryker's Hope                |  1027302 |
|        4 | Odin's Hold                 |  2320306 |
|        5 | Norma Arm                   |  1665875 |
|        6 | Arcadian Stream             |   506254 |
|        7 | Izanami                     |   682226 |
|        8 | Inner Orion-Perseus Conflux |   324521 |
|        9 | Inner Scutum-Centaurus Arm  |  7420003 |
|       10 | Norma Expanse               |  1327449 |
|       11 | Trojan Belt                 |   160842 |
|       12 | The Veils                   |   315230 |
|       13 | Newton's Vault              |  1043416 |
|       14 | The Conduit                 |   129543 |
|       15 | Outer Orion-Perseus Conflux |   174566 |
|       16 | Orion-Cygnus Arm            |   335363 |
|       17 | Temple                      |   368615 |
|       18 | Inner Orion Spur            | 13204424 |
|       19 | Hawking's Gap               |  1069536 |
|       20 | Dryman's Point              |   217749 |
|       21 | Sagittarius Carina Arm      |   136371 |
|       22 | Mare Somnia                 |   172218 |
|       23 | Acheron                     |   475492 |
|       24 | Formorian Frontier          |  1685594 |
|       25 | Heironymous Delta           |   176713 |
|       26 | Outer Scutum-Centaurus Arm  |   174391 |
|       27 | Outer Arm                   |   278414 |
|       28 | Aquila's Halo               |    12083 |
|       29 | Errant Marches              |   337523 |
|       30 | Perseus Arm                 |   147841 |
|       31 | Formidine Rift              |   587939 |
|       32 | Vulcan Gate                 |   222797 |
|       33 | Elysian Shore               |  1990290 |
|       34 | Sanguineous Rim             |  1372884 |
|       35 | Outer Orion Spur            |   980490 |
|       36 | Achilles' Altar             |   193911 |
|       37 | Xibalba                     |    51458 |
|       38 | Lyra's Song                 |   157704 |
|       40 | The Abyss                   |   473695 |
|       41 | Kepler's Crest              |   332961 |
|       42 | The Void                    |    88036 |
+----------+-----------------------------+----------+
42 rows in set (1 min 3.94 sec)

mysql> select count(*) from systems where region is null and deletionState=0;
+----------+
| count(*) |
+----------+
|  2286430 |
+----------+
1 row in set (16.91 sec)

Using this image map: (click for full size, 10ly per pixel resolution)

 

[marx]

This is what I see with my eyes closed when I snort meta-alloys.

Also, poor little Aquila's Halo. I should go there sometime, see if it really is this rare, or it's just people rarely popping in there, and popping out soon afterwards.

Hm, say, could you do a rough approximation of the areas of regions?

 

[Spansh]

So we need a few things from my perspective, and we need to make a few assumptions.

First, we need to start using polar coordinates. In order for this to work the very first thing we need to do is determine the x,z coordinates of the centre point. I had assumed it was going to be Sagittarius A* but from your comments it appears it may not be (though it probably should be).

The second thing we need to do is pick out the coordinates of all the corners of each region. This isn't quite as much work as it may be due to each corner being associated with at least 2, sometimes 4 regions. For each of those coordinates we need distance from the centre point and angle around.

If we refer to the distance from the centrepoint as radius and the angle as azimuth.

After that from my perspective (since there aren't any libraries which deal with polar coordinates and polygons in this manner) the easiest thing to do would be for each region to be converted to multiple (potentially overlapping only within the same region) shapes each with 4 sides (2 curved, 2 straight) denoted by a start and end radius and a start and end azimuth

The reason for that is that is makes the test for whether a point is within a shape particularly easy. I can simply convert the point being tested to polar coordinates, then it's simpy a matter of testing each shape we now have to see if the radius of this point lies between the start and end radius and check the same for the azimuth. If that is the case then the point is in that region. Since we have chosen our shapes so that only points within the same region overlap we can stop looking through. The code for this then becomes pretty trivial.

This all brings us down to the million dollar questions which were the first 2 paragraphs in this post. We may be able to determine the coordinates of the regions by taking a selection of systems on either side of the border and then taking an average.

I will admit I haven't been in game for quite a long time, so I'm not sure how easy that would be (especially if we haven't actually visited those systems and recorded the coordinates on the various developer sites).

One other option would be for someone from frontier to wade in and help out.

WIth regards to the system counts etc, you can see the numbers of systems I have in each region on this URL https://spansh.co.uk/api/systems/field_values/region .What is interesting there is that my numbers are wildly different to yours, which may mean I have some mapping issues. I should probably plot the coordinates I'm using somewhere to make sure.

 

[Romeo India Charlie]

@Orvidius that's what I was referring to in the wrong thread. You'd need a 1:1 pixel to light-year resolution or some sort distortion to accommodate for the density in the middle of the galaxy though.

 

[Deleted member 38366]

I may add that the Game itself seems often unsure about which Sector the Player really is in.

I've seen borderline cases where the HUD Jump Target proclaimed "jumping into {New Sector}" and a following Codex Discovery there was still credited to the previous Sector, as was any Codex-lookup (focus and data display for the wrong Sector).
I guess some rounding errors, since ELITE loves rounding errors... which many parts of the Code seem to perform differently

I guess that's indeed a tricky issue to get a truly "clean" separation of those Sectors, if even the Game struggles with it.
Unsure how to tackle that, short of sampling alot of such borderline cases while moving arund the bordering areas between 2 Sectors.

 

[Orvidius]

Hm, say, could you do a rough approximation of the areas of regions?

Yep, though it really depends on how you count it. Here's a count of the pixels (10x10 ly squares), but that makes those outer regions look huge since I just extended them to the edge of the map:

It might also be useful to do an estimate based on how many of those have star systems in them, but considering how many unvisited pixels there are, that won't be accurate either.

Spoiler

mysql> select region,name,count(*) from regions,regionmap where regions.id=region and region>0 group by region order by region;
+--------+-----------------------------+----------+
| region | name                        | count(*) |
+--------+-----------------------------+----------+
|      1 | Galactic Centre             |   269892 |
|      2 | Empyrean Straits            |   998525 |
|      3 | Ryker's Hope                |   704163 |
|      4 | Odin's Hold                 |   870513 |
|      5 | Norma Arm                   |   521044 |
|      6 | Arcadian Stream             |  1922218 |
|      7 | Izanami                     |   799756 |
|      8 | Inner Orion-Perseus Conflux |   697360 |
|      9 | Inner Scutum-Centaurus Arm  |  1022521 |
|     10 | Norma Expanse               |  1912442 |
|     11 | Trojan Belt                 |  1082378 |
|     12 | The Veils                   |  1518750 |
|     13 | Newton's Vault              |  1515316 |
|     14 | The Conduit                 |  1177644 |
|     15 | Outer Orion-Perseus Conflux |   855821 |
|     16 | Orion-Cygnus Arm            |   926999 |
|     17 | Temple                      |   563638 |
|     18 | Inner Orion Spur            |  1101284 |
|     19 | Hawking's Gap               |  1989341 |
|     20 | Dryman's Point              |  1761777 |
|     21 | Sagittarius Carina Arm      |  1810223 |
|     22 | Mare Somnia                 |  4416723 |
|     23 | Acheron                     |  7226192 |
|     24 | Formorian Frontier          |  2387130 |
|     25 | Heironymous Delta           |  1684421 |
|     26 | Outer Scutum-Centaurus Arm  |  6441723 |
|     27 | Outer Arm                   |  2364939 |
|     28 | Aquila's Halo               |  1694646 |
|     29 | Errant Marches              |  6462880 |
|     30 | Perseus Arm                 |  1031372 |
|     31 | Formidine Rift              |  4221989 |
|     32 | Vulcan Gate                 |  1336249 |
|     33 | Elysian Shore               |  1265046 |
|     34 | Sanguineous Rim             |  1271795 |
|     35 | Outer Orion Spur            |   740027 |
|     36 | Achilles' Altar             |  1369454 |
|     37 | Xibalba                     |  4653182 |
|     38 | Lyra's Song                 |  1376332 |
|     40 | The Abyss                   |  2222357 |
|     41 | Kepler's Crest              |  3236760 |
|     42 | The Void                    |  1569815 |
+--------+-----------------------------+----------+
41 rows in set (28.79 sec)

First, we need to start using polar coordinates. In order for this to work the very first thing we need to do is determine the x,z coordinates of the centre point. I had assumed it was going to be Sagittarius A* but from your comments it appears it may not be (though it probably should be).

Right, it's quite a bit off from Sagittarius A*:

 

[marx]

I've tried looking for the center of the galactic regions with the galaxy map, but even then, it's odd. It's certainly somewhere within the Stuemeae sector (assuming it's on the galactic plane, but regions seem to ignore height completely), which makes sense, as it's the center of the sector grid. It appears to be more along the border of the sector than at its center though. That makes me wonder... which would be the first system to be generated in the sector?

 

[Orvidius]

I was a little short on time earlier so I didn't get to include some further thoughts.

I agree that it will be best to build a vector map using a polar coordinate system divided into bands/arcs defined by inner and outer curved edges, and two straight lines. Overlap is fine within a region, of course.

When I was calibrating my border map, I flew out to 3 or 4 boundary intersections to get coordinates, so that I could scale and reposition the border map to match. I don't think I have my notes anymore, as to what those positions were and their coordinates. But to make an accurate map, we would need to do this for every single vertex in the map. With vertices on hand for all of the straight edges, we could extrapolate and find the best center position. Or fudge a center first, and refine it as those points become available, etc.

This won't be accurate, but in eyeballing the map, the center looks like it's somewhere around 480, 0, 27000 (I'm, including Y=0 for completeness and clarity, but of course the Y coordinate doesn't matter).

 

[marx]

Right, so I had a go at the in-game galaxy map. My method was fairly simple: center the view on Sagittarius A*, zoom in as far as I could while still having some usable sector borders, take a high-res screenshot (from my 1440p monitor, that goes up to 10240 x 5760), then butcher the contrast and brightness until the borders become visible. As an added bonus, the outliners in the middle of the borders are also visible, which help with aligning the lines. Still plenty of room for error, of course.

Here's what I came up with. The blue grid denotes the closest grid-lines on the shot, but they seem slightly off. (Unless I'm mistaken, those are 1000 ly.)
link because it's a big one

Having looked at the possible area, nothing seems to jump out at me as a center candidate still. Any ideas?

 

[MattG]

First, we need to start using polar coordinates. In order for this to work the very first thing we need to do is determine the x,z coordinates of the centre point. I had assumed it was going to be Sagittarius A* but from your comments it appears it may not be (though it probably should be).

Yep, even my initial approximations of lines had them converging outside of Sag A*. Makes me curious what is at the center point though.

The second thing we need to do is pick out the coordinates of all the corners of each region. This isn't quite as much work as it may be due to each corner being associated with at least 2, sometimes 4 regions. For each of those coordinates we need distance from the centre point and angle around.

The point I got to before I had to pause was trying to get accurate data of ideally 4 lines to determine the centre point. There is a complication that the boundaries up close are very jagged - as if they drew the boundaries over a low-res version of the galaxy and then stretched it. It means there is a margin of error trying to determine the centre point or the path of the lines. Because I didn't have accurate co-ordinate data, just estimated from galmap it meant my initial attempts didn't converge in exactly the same place.

 

[Spansh]

The point I got to before I had to pause was trying to get accurate data of ideally 4 lines to determine the centre point. There is a complication that the boundaries up close are very jagged - as if they drew the boundaries over a low-res version of the galaxy and then stretched it. It means there is a margin of error trying to determine the centre point or the path of the lines. Because I didn't have accurate co-ordinate data, just estimated from galmap it meant my initial attempts didn't converge in exactly the same place.

Yes @Lance 'Spacecat' D. had mentioned when I was talking about this on discord the other day that it appeared that the regions on the galaxy map seemed to show as jagged 90 degree angles approximating curves when zoomed in to extreme lengths, it feels like it's going to be difficult to get something which works all the time.

 

[Redfox]

From the info above it seems clear, but has it been verified that the borders are independent from they Y-axis? Theoretically, the borders could be based on spheres (like the permit-locked areas) which would require a different approach.

 

[Spansh]

I've written out an SVG of my region mapping (which seems to be accurate and is taken from the EDSM image, so only contains coordinates for that) overlayed with 10million systems from the galaxy. It feels to me like my conversion of galactic coordinates to image coordinates and the scaling are both off so I might have to revisit that.

Be warned this SVG is nearly 100MB in size: http://downloads.spansh.co.uk/regions.svg

Edit: I checked the various regions and was slightly off, I've fixed that and it's made things better but on that SVG it still feels like it's wrong on the right hand side (remember it is still flipped top to bottom).

 

[marx]

A fun fact crossed my mind: imagine if that joking suggestion were actually true, and the center point of galactic regions really were Raxxla. That would mean that they would have placed it in the most dense region of the galaxy, with nothing of interest nearby. And hey, even if you had a 50 ly cube to search, you'd still have a whole lot of systems to go through. Scanning the entire bubble would be quicker.

From the info above it seems clear, but has it been verified that the borders are independent from they Y-axis? Theoretically, the borders could be based on spheres (like the permit-locked areas) which would require a different approach.

Yes. You can check it for yourself too: no matter how high or low you go on the y axis, region borders remain the same.
This way, at least you don't end up with "regionless" areas, whereas with spherical borders, you'd be hard pressed to fill out the entire map - it goes quite far both above and below the galactic plane, after all.