Select a few coordinates from a large set that look evenly distributed in the area

user_4489580 0
Viewed 129

I have a MySQL table with area and lat/lon location columns. Every area has many locations, say 20.000. Is there a way to pick just a few, say 100, that look somewhat evenly distributed on the map?

The distribution doesn't have to be perfect, query speed is more important. If that is not possible directly with MySQL a very fast algorithm that somehow picks evenly distributed locations might also work.

Thanks in advance.

Edit: answering some requests in comments. The data doesn't have something that can be used, it's just area and coordinates of locations, example:

+-------+--------------+----------+-----------+------------+--------+--------+
| id    | area         | postcode | lat       | lon        | colour | size   |
+-------+--------------+----------+-----------+------------+--------+--------+
| 16895 | Athens       |    10431 | 37.983917 | 23.7293599 | red    | big    |
| 16995 | Athens       |    11523 | 37.883917 | 23.8293599 | green  | medium |
| 16996 | Athens       |    10432 | 37.783917 | 23.7293599 | yellow | small  |
| 17000 | Thessaloniki |    54453 | 40.783917 | 22.7293599 | green  | small  |
+-------+--------------+----------+-----------+------------+--------+--------+

There are some more columns with characteristics but those are just used for filtering.

I did try getting the nth row in the meantime, it seems to work although a bit slow

SET @a = 0;
select * from `locations` where (@a := @a + 1) % 200 = 0

using random() also works but a bit slow too.

Edit2: Turns out it was easy to add postal codes on the table. Having that, getting grouped by postal code seems to give a nice to the eye result. Only issue is that there are very large areas with around 3000 distinct postcodes and getting just 100 may end up many of them show in one place, so will probably need to further process in PHP.

Edit3, answering @RickJames questions in comments so they are in one place:

  1. Please define "evenly distributed" -- evenly spaced in latitude? no two are "close" to each other? etc.
    • "Evenly distributed" was a bad choice of words. We just want to show some locations on the area that are not all in one place
  2. Are the "areas" rectangles? Hexagons? Or gerrymandered congressional districts?
    • They can be thought roughly as rectangles but it shouldn't matter. Important thing I missed, we also need to show locations from multiple areas. Areas may be far apart from each other or neighboring (but not overlap). In that case we'd want the sample of 100 to be split between the areas.
  3. Is the "100 per area" fixed? Or can it be "about 100"
    • It's not fixed, it's around 100 but we can change this if it doesn't look nice
  4. Is there an AUTO_INCREMENT id on the table? Are there gaps in the numbers?
    • Yes there is an AUTO_INCREMENT id and can have gaps
  5. Has the problem changed from "100 per area" to "1 per postal code"?
    • Nope the problem is still the same, "show 100 per area in a way that not all of them are in the same place", how this is done it doesn't matter
  6. What are the total row count and desired number of rows in output?
    • Total row count depends on area and criteria, it can be up to 40k in an area. If total is more than 1000 we want to fall back showing just a random of 100. If 1000 or less we can just show all of them
  7. Do you need a different sample each time you run the query?
    • Same sample or different sample even with the same criteria is fine
  8. Are you willing to add a column to the table?
    • It's not up to me but if I have good argument then most probably we can add a new column
coordinates mysql algorithm php
1 Answers

Here's an approach that may satisfy the goals.

  1. Preprocess the table, making a new table, to get rid of "duplicate" items.
  2. If the new table is small enough, a full scan of it may be fast enough.

As for "duplicates", consider this as a crude way to discover that two items land in the same spot:

 SELECT  ROUND(latitude * 5),
         ROUND(longitude * 3),
         MIN(id) AS id_to_keep
     FROM tbl
     GROUP BY 1,2

The "5" and "3" can be tweaked upward (or downard) to cause more (or fewer) ids to be kept. "5" and "3" are different because of the way the lat/lng are laid out; that ratio might work most temperate latitudes. (Use equal numbers near the equator, use a bigger ration for higher latitudes.)

There is a minor flaw... Two items very close to each other might be across the boundaries created by those ROUNDs.

How many rows are in the original table? How many rows does the above query generate? ( SELECT COUNT(*) FROM ( ... ) x; )

user_17668310
Related