Als je op zoek bent naar een benaderingsalgoritme, raad ik aan om te zoeken naar een k-means-algoritme of een hiërarchische cluster, vooral een monstercurve of een ruimtevullende curve. Allereerst kun je een minimale opspannende boom van de grafiek berekenen en vervolgens de langste en duurste randen verwijderen. Dan maakt de boom veel kleine bomen en kun je de k-means gebruiken om een groep punten, d.w.z. clusters, te berekenen.
"Het single-link k-clustering-algoritme ... is precies het algoritme van Kruskal ... gelijk aan het vinden van een MST en het verwijderen van de k-1 duurste randen." Zie bijvoorbeeld hier:https://stats.stackexchange.com/ vragen/475/visualisatie-software-voor-clustering .
Een goed voorbeeld van een monstercurve is de hilbertcurve. De basisvorm van deze curve is een U-vorm en door veel ervan samen te kopiëren en te roteren, vult de curve de euklidische ruimte. Verrassend genoeg kan een grijze code helpen om de oriëntatie van deze U-vorm te achterhalen. Je kunt Nick's ruimtelijke index quadtree hilbert curve opzoeken blogartikel over meer details . In plaats daarvan kunt u, om de index van de curve te berekenen, een quadkey samenstellen zoals in bing-kaarten. De quadkey is uniek voor elke coördinaat en kan worden gebruikt met normale stringbewerkingen. Elke positie in de toets maakt deel uit van de U-vormige curve en dus kunt u dit puntengebied selecteren uit gedeeltelijk van links naar rechts selecteren vanaf de quadkey.
In deze afbeelding kun je zien dat de groene polygoon is gevonden met behulp van een hilbert-curve:
Je kunt mijn php-klassen hier vinden:http://www.phpclasses.org/package/6202-PHP-Generate-points-of-an-Hilbert-curve.html