1

I have rectangular regions in a plane. I want to consistently order them in a human-friendly way that a typical y-x sort won't work for. Basically I want (0,0), (1,0), and (0,1) to sort the same as (0,0), (1, -0.1), and (-0.1, 1).

Ideas?


From comments:

  • The obvious answers, y-x and x-y sort, result in different orders for the short example I posted. The things I'm coming up with, now, are clustering approaches where I cluster the y values, sort by cluster y means, then by x.

Question: What are you sorting your rectangles for? Searching? Displaying?

  • Numbering the regions, and I want two region sets a human would say are nearly identical to get numbered identically.

Question: Is the orientation of the rectangles really important (what is the difference between (0,1) and (-1,0) in the problem domain)? Would primarily sorting by area or diagonal be ok?

  • I can't tell the orientation of them beyond portrait or landscape, and size doesn't work because a lot might be practically the same.
7
  • 1
    Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask
    – gnat
    Oct 1, 2013 at 16:54
  • The obvious answers, y-x and x-y sort, result in different orders for the short example I posted. The things I'm coming up with, now, are clustering approaches where I cluster the y values, sort by cluster y means, then by x. Oct 1, 2013 at 17:03
  • 1
    What are you sorting your rectangles for? Searching? Displaying? Is the orientation of the rectangles really important (what is the difference between (0,1) and (-1,0) in the problem domain)? Would primarily sorting by area or diagonal be ok?
    – amon
    Oct 1, 2013 at 17:12
  • Numbering the regions, and I want two region sets a human would say are nearly identical to get numbered identically. Oct 1, 2013 at 19:22
  • 2
    If you need to find rectangles based on similarity, maybe your real problem is to find nearest neighbors rather than ordering. An axis-aligned rectangle is defined by 4 co-ordinates, therefore you're searching for the nearest neighbor in 4 dimensions. Here's a blog post about VP-trees, but they're probably more for very high dimensions. You might be better off with a k-d tree or the 4D variation of quadtrees and octrees.
    – user8709
    Oct 2, 2013 at 1:58

2 Answers 2

5

In principle, a Hilbert curve can do that. It's a fractal that fills a two-dimensional space.

This paper defines a generalization of the Hilbert curve and uses a relationship with reflected binary Gray code to define efficient conversions, with the main application being multi-dimensional database indexes.

The key point is that a fractal can be evaluated to any level of detail. So in principle, if two different points hit the same point on a Hilbert curve at one resolution, you can just evaluate the Hilbert curve at higher and higher resolutions until you find one where the points on the Hilbert curve are different, ordering the two points based on that. Because you're just evaluating the same curve to a higher level of detail, ordering relative to other points (assessed at lower resolution) is unchanged.

That said, this is just a the basic idea - I don't know if it has been done (probably it has, but I don't have a reference) or the detail of how to implement it well.

2
  • 1
    iirc there is a geospatial databse that uses this sort of technique for its spatial index. it also sort of begs the question does the OP real just want some form of spatial indexing?
    – jk.
    Oct 2, 2013 at 11:10
  • I'm not sure if it would work when points are close to each other geometrically, but far on the Hilbert curve, but it's a really interesting idea. Jun 10, 2015 at 6:15
0

I realized there's a better way to approach the problem. What I was really trying to do was match (0,0), (1,0), and (0,1) to (0,0), (1, -0.1), and (-0.1, 1), respectively. Ordering them, then matching up sequences like Python's itertools.zip() seemed like an elegant solution.

But what's easier is to treat this as a clustering problem. Running K-means on the concatenated list of points where K = n/2 (3 in the case of my example above) would to the matching I needed.

1
  • Can you show an example?
    – shinzou
    Apr 24, 2017 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.