Data structure for traversing polygon segments in Haskell?

Question

i have an unordered list of horizontal/vertical segments of length 1, which build one or many polygons. I now need to find the list of all connected corners in each polygon.

Example:

[Horizontal (0,0), Vertical (2,0), Horizontal (1,0), Horizontal (2,2), Vertical (2,1)]

represents a line like this

2         X--X
          |
1         X
          |
0   X--X--X

    0  1  2

I would be looking for the corners [(2,0), (2,2)].

In imperative languages i would probably use a (doubly-)linked data structure and traverse those. I can't come up with a elegant representation for this in Haskell. How would you do it?

Answer 1

Before we go looking for corners, let's take a step back. What are you trying to do?

I have an unordered list of horizontal/vertical segments of length 1, which build one or many polygons. I now need to find the list of all connected corners in each polygon.

"Searching" and "unordered lists" don't really go together, as I'm sure you realize! This is true even in simple lookups, but it's even worse for what you're doing, which is conceptually closer to finding duplicates because it requires correlating elements of the collection with each other, instead of inspecting each independently.

So, you're definitely going to want something with a lot more structure to it. One option would be a more semantically-meaningful representation in terms of complete polygons, allowing a simple traversal of an unbroken perimeter, but I'm guessing you don't have that information available (for instance, if you're trying to create such a structure here).

Now, in a comment you said:

The reason for this is, that the segments were stored in "Set"s before, in order to remove overlapping segments. This representation guarantees that there is only one segment (x,y)--(x+1,y).

This is worth further thought. How does Data.Set work, and why is it better for removing duplicates than an unordered list? That last bit's kind of a give-away, because Data.Set is precisely an ordered collection, so by giving each item a representation that sorts uniquely, you get the combined benefits of automatically removing duplicates and fast lookup.

As mentioned above, your actual problem is conceptually similar to finding duplicates; instead of finding overlapping segments, you want adjacent ones. Can using Data.Set help you here as well?

Alas, it cannot. To see why, think about how the sorting works. Given two items X and Y, there are three possible comparisons: X < Y, X == Y, or X > Y. If distinct, adjacent elements differ by the minimum amount possible, you can safely examine only elements that are adjacent in the sorted collection. But this cannot generalize to line segments for multiple reasons, the simplest being that up to four distinct elements can be adjacent, which cannot be described in a sorted sequence.

Hopefully I've been heavy-handed enough with my hints that you're now wondering what a sorted collection that does allow four distinct elements to be adjacent would look like, and whether it would allow easy searching the way Data.Set does.

The answer to the latter is yes, absolutely, and the answer to the first is that it would be a higher-dimensional search tree. A simple binary search tree looks something like this:

data Tree a = Leaf | Branch a (Tree a) (Tree a)

...where you ensure that at any branch, all leaf values in the left half are smaller than those in the right. A simple 2-dimensional search tree would instead look something like this:

data Tree a = Leaf | Branch a (Tree a) (Tree a) (Tree a) (Tree a)

...where each branch represents a quadrant, sorting by comparing on the two axes independently. Otherwise, it works just like familiar 1-dimensional search trees, with straightforward translations of many standard algorithms, and given a specific line segment you can quickly search for any adjacent segments.

---

Edit: In hindsight, I got a little too wrapped-up in exposition and forgot to give references. This is not at all a novel concept, and has many extant variations:

• What I described would be called a point Quadtree and is a simple extension of binary search trees, like Data.Set.

• The same concept can be done with regions instead of discrete points, with lookups ending at regions that are either fully included or excluded. These are similar extensions of tries, like Data.IntSet.

• A variation called R-trees are similar to a B-trees and have useful performance characteristics for some purposes.

The concepts extend just as well to higher dimensions, as well. Data structures along these lines are used for rendering and collision detection in simulations and video games, spatial databases with "nearest neighbor" searches, as well as more abstract applications you wouldn't normally think of geometrically, where sparse data points can be sorted along multiple axes and some combined notion of "distance" is meaningful.

Oddly enough, I've been unable to find any implementation of such data structures on Hackage, besides one incomplete and seemingly-abandoned package.

Answer 2

If I understand the problem description correctly, each segment can take part in up to four possible corners that each identifies a specific complementary segment. Given a list of segments, we can than walk down the list seeing which possible two-segment corners are present, then figure out where those segments meet. This is a very slow approach due to the repeated list traversals, but if you are only dealing with handfuls of segments, it is at least fairly concise.

data Segment = Horizontal (Int,Int) | Vertical (Int,Int) deriving (Eq, Show)

example = [ Horizontal (0,0)
          , Vertical (2,0)
          , Horizontal (1,0)
          , Horizontal (2,2)
          , Vertical (2,1) ]

corners [] = []
corners (Horizontal (x,y):xs) = ns ++ corners xs
  where ns = map cornerLoc . filter (`elem` xs) $ 
             map Vertical [(x,y),(x+1,y),(x,y-1),(x+1,y-1)]
        cornerLoc (Vertical (x',_)) = (max x x', y)
corners (Vertical (x,y):xs) = ns ++ corners xs
  where ns = map cornerLoc . filter (`elem` xs) $ 
             map Horizontal [(x,y),(x,y+1),(x-1,y),(x-1,y+1)]
        cornerLoc (Horizontal (_,y')) = (x, max y y')