Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Inserting intervals does not work correctly #3

Open
seppestas opened this issue Apr 22, 2015 · 3 comments
Open

Inserting intervals does not work correctly #3

seppestas opened this issue Apr 22, 2015 · 3 comments

Comments

@seppestas
Copy link
Contributor

Hi

I finally found out what the real problem is with this library. CompareTo does not report INTERSECT_OR_SUPERSET when s is a subset of other, even though this implies that they also intersect. This means the algorithm for inserting the intervals in the tree can not be implemented correctly:

// CompareTo compares two Segments and returns: DISJOINT, SUBSET or INTERSECT_OR_SUPERSET
func (s *Segment) CompareTo(other *Segment) int {
    if other.From > s.To || other.To < s.From {
        return DISJOINT
    }
    if other.From <= s.From && other.To >= s.To {
        return SUBSET // this means there is also an intersection
    }
    return INTERSECT_OR_SUPERSET
}
// Inserts interval into given tree structure
func insertInterval(node *node, intrvl *Interval) {
    switch node.segment.CompareTo(&intrvl.Segment) {
    case SUBSET:
        // interval of node is a subset of the specified interval or equal
        if node.overlap == nil {
            node.overlap = make([]*Interval, 0, 10)
        }
        node.overlap = append(node.overlap, intrvl)
    case INTERSECT_OR_SUPERSET:
        // In the original algorithm we should directly check if `node.left` intersects with `intrvl`.
        // In this algorithm we check this after calling `insertInterval`. However, we never land
        // here when `s.left` is a subset of `intrvl`.
        if node.left != nil {
            insertInterval(node.left, intrvl)
        }
        // In the original algorithm we should directly check if `node.right` intersects with `intrvl`.
        // In this algorithm we check this after calling `insertInterval`. However, we never land
        // here when `s.right` is a subset of `intrvl`.
        if node.right != nil {
            insertInterval(node.right, intrvl)
        }
    case DISJOINT:
        // nothing to do
    }
}

My suggestion is to use separate function to check if an interval is a subset of another interval, and a function to check if intervals intersect. This makes it possible to implement the correct algorithm.

On page 43 of http://www.cs.uu.nl/geobook/pseudo.pdf there is some pretty good pseudo code. This is the pseudo code used in Computational Geometry: Algorithms and Applications, that is referenced (and pretty much copy-pasted) a lot in the segment tree wiki page.

I already tested this in my code, and it should be fairly easy to fix this in your library. Shall I create a pull request for this? If yes, could you first please merge #2?

@toberndo
Copy link
Owner

Sure, PR is welcome. I merged #2.

seppestas added a commit to seppestas/go-stree that referenced this issue Apr 27, 2015
@cenkalti
Copy link

Hi @toberndo,

@seppestas has fixed some problems. You should merge those changes.

@seppestas
Copy link
Contributor Author

@cenkalti I’m not sure why I didn’t create a PR for my latest changes, but it might be I never properly finished it. I think I gave up writing unit tests at some point.

Also, note that I made a seperate library based on this one that has a more concurrency friendly interface...

@toberndo feel free to merge in any fixes from fork.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants