Data structure for intersecting polygon segments in Haskell?

Question

I have an unordered list of horizontal / vertical segments of length 1 that build one or more polygons. Now I need to find a list of all the connected angles in each polygon.

Example:

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

represents such a string

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

I would look for angles [(2,0), (2,2)].

In imperative languages, I would probably use a (doubly connected) data structure and intersect them. I cannot come up with an elegant presentation for this in Haskell. How do you do this?

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 that build one or more polygons. Now I need to find a list of all the connected angles in each polygon.

The "search" and the "unordered lists" do not really match, as I'm sure you understand! This is true even in simple searches, but it is even worse for what you do, which is conceptually closer to finding duplicates, because it requires correlation of the elements of the collection with each other, and not for checking each independently.

So, you will definitely want something with a much larger structure. One option would be a more semantically meaningful representation in terms of complete polygons allowing for a simple walk around the continuous perimeter, but I assume that you do not have this information (for example, if you are trying to create such a structure here).

Now in the comment you said:

The reason for this is that the segments were previously stored in “Set” to remove overlapping segments. This representation ensures that there is only one segment (x, y) - (x + 1, y).

It is worth considering. How does Data.Set work and why is it better to remove duplicates than an unordered list? This is the last bit of the distribution because Data.Set is a precisely ordered collection, therefore, providing each element with a unique view, you get the combined benefits of automatic duplicate removal and quick search.

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

Alas, it cannot. To understand why, think about how sorting works. Given the two elements X and Y, there are three possible comparisons: X <Y, X == Y or X> Y. If different adjacent elements differ in the smallest possible sum, you can safely examine only elements that are adjacent in a sorted collection. But this cannot be generalized to line segments for several reasons, the simplest of which is that up to four separate elements can be contiguous, which cannot be described in a sorted sequence.

I hope I was heavy enough with my hints that now you are wondering what a sorted collection would look like that would allow adjacent four neighboring elements, and whether it would make it easy to find the way Data.Set does.

The answer to the latter is yes, absolutely, and the answer to the former is that it will be a larger search tree. A simple binary search tree looks something like this:

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

... where you guarantee that in any branch all the values ​​of the leaves in the left half are less than on the right. A simple two-dimensional search tree would 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, comparing two axes independently of each other. Otherwise, it works in the same way as the familiar one-dimensional search trees, with direct translations of many standard algorithms, and taking into account a specific line segment, you can quickly search for any adjacent segments.

---

Change Looking back, I changed into the exposition a bit and forgot to give links. This is not a new concept at all and has many surviving variations:

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

• The same concept can be performed with regions, rather than with discrete points, and search queries end in regions that are either fully included or excluded. These are similar try extensions, for example, Data.IntSet .

• An option called R-trees is similar to B-trees and has useful performance for some purposes.

The concepts also apply to higher sizes. The data structures in these lines are used to visualize and detect collisions in simulations and video games, spatial databases with the “nearest neighbor” search, as well as more abstract applications that you usually don’t consider geometrically, where sparse data points can be sorted along several axes and some combined concept of "distance" makes sense.

Oddly enough, I could not find any implementation of such data structures in Hackage, except for one incomplete and seemingly refused package.

Answer 2

If I understand the description of the problem correctly, each segment can take part in four possible angles, each of which identifies a specific additional segment. Given the list of segments, we can than go down the list, seeing what possible two-segment angles are present, and then find out where these segments meet. This is a very slow approach due to repetitive transitions of the list, but if you are dealing only with heaps of segments, it is at least brief enough.

 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')