🔒 Locked

Fast 2d polygon self-intersect test?

Started by Emergent Sep 25, 2009 at 10:39 AM 2 replies 13.9k views

Original Post

Sep 25, 2009 at 10:39 AM

Is it possible to determine if a polygon (represented as a sequential list of n vertices) intersects itself in faster than O(n^2) time? If so, how? Anybody here with strong computational-geometry-fu got some nice winding number or sweepline tricks? :-) I mean, I could always do the usual, - Put all the edges into buckets using a spatial hash: O(n) - Check each edge against other edges in the same bucket: Expected O(n^2/m) if I have m buckets and edges are uniformly distributed between buckets (not exactly true, but O(n^2/m) is still basically correct). and maybe I should be happy with this -- by choosing small enough buckets I can trade memory for making the quadratic portion of the cost arbitrarily small. But I feel like this problem has so much structure that there have got to be smarter approaches. Any ideas?

alvaro

Sep 25, 2009 at 12:26 PM

A sweep line algorithm will do this in time O(n*log(n)), if I am thinking about it right.

EDIT: It's basically a particular case of this algorithm.

Emergent

Sep 25, 2009 at 1:08 PM

Thanks alvaro; that's perfect. I thought there was a sweepline way to do this. I was confused about finding intersections between segments as you swept the line though, and thought it introduced another factor of 'n.' Thanks.

Sirisian

Sep 26, 2009 at 2:14 AM

For small n's you can use the naive method. I quickly implemented the code below. (I might comment it later. I was just curious. Sorry for the massive use of 1 letter variables).

This algorithm can return true when it detects a self-intersecting polygon. It's worst case is when the polygon isn't self-intersecting (O(n^2)). But yeah if you're generating random polygons with a low number of verts and throwing out the self-intersecting ones this is probably your best bet. (I might have missed an optimization. If so tell me since I might need this code later.)

        public bool SelfIntersectTest(List<Vector2> vertices)        {            for (int i = 0; i < vertices.Count; ++i)            {                if (i < vertices.Count - 1)                {                    for (int h = i + 1; h < vertices.Count; ++h)                    {                        // Do two vertices lie on top of one another?                        if (vertices == vertices[h])                        {                            return true;                        }                    }                }                int j = (i + 1) % vertices.Count;                Vector2 iToj = vertices[j] - vertices;                Vector2 iTojNormal = new Vector2(iToj.Y, -iToj.X);                // i is the first vertex and j is the second                int startK = (j + 1) % vertices.Count;                int endK = (i - 1 + vertices.Count) % vertices.Count;                endK += startK < endK ? 0 : startK + 1;                int k = startK;                Vector2 iTok = vertices[k] - vertices;                bool onLeftSide = Vector2.Dot(iTok, iTojNormal) >= 0;                Vector2 prevK = vertices[k];                ++k;                for (; k <= endK; ++k)                {                    int modK = k % vertices.Count;                    iTok = vertices[modK] - vertices;                    if (onLeftSide != Vector2.Dot(iTok, iTojNormal) >= 0)                    {                        Vector2 prevKtoK = vertices[modK] - prevK;                        Vector2 prevKtoKNormal = new Vector2(prevKtoK.Y, -prevKtoK.X);                        if ((Vector2.Dot(vertices - prevK, prevKtoKNormal) >= 0) != (Vector2.Dot(vertices[j] - prevK, prevKtoKNormal) >= 0))                        {                            return true;                        }                    }                    onLeftSide = Vector2.Dot(iTok, iTojNormal) > 0;                    prevK = vertices[modK];                }            }            return false;        }

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.