Test point for its position relative to the convex hull in log(n)

Question

I have a collection of 2D points S and I need to test if an input point q is inside or outside the convex hull of S.

Since it's about a binary decision, I was thinking I could theoretically achieve O(log(N)) by using a decision tree.

However I have no idea how to organize the data and how the algorithm would look like to really get an answer in O(log(N)).

While researching with this idea in mind, I've found this:

How can we find these two cases more quickly? Binary search. Just search for x in the first coordinates of points in the two chains. If it is in the chain, you have found a crossing through a vertex (and you don't have to be as careful to tell what kind of crossing, either). If x is not the coordinate of a vertex in the chain, the two nearest values to it tell you which segment the ray from (x,y) might cross. So we can test whether a point is in a convex polygon in time O(log n).

It turns out that there are data structures that can test whether a point is in an arbitrary polygon (or which of several polygons it's in) in the same O(log n) time bound. But they're more complicated, so I don't have time to describe them here; I'll talk about them at some point in ICS 164.

(http://www.ics.uci.edu/~eppstein/161/960307.html)

So do you have any ideas:

1. How the data structure should look like to get it down in O(log(N))?
2. How the algorithm should look like?

Answer 1

Let's deal with only one chain first. We want to check whether (qx, qy) is above a convex chain of line segments.

The expensive part is is binary searching on a list of x coordinates to find the biggest one less than your query point. All you need for this is an array of the points of the chain sorted in x order. Then it's a simple "point above line?" test.

Now we want to see whether a point is in a convex polygon. If you represent the edges of that convex polygon as an upper chain and a lower chain, then it's the intersection of the stuff below the upper chain with the stuff above the lower chain. So it's two binary searches.

(Even if you've just got the points in clockwise sorted order or something, you can find the smallest and largest x coordinates in the polygon in logarithmic time using binary search or four-point search. So you don't even have to precompute the upper and lower chains if you don't want to.)

EDIT: I see that your question can also be parsed as "what do point location data structures look ilke?" rather than "how do I store the convex hull to permit efficient inside/outside testing?"

It is natural to study point location in a slightly more general context than inside-outside testing. There is a

CGAL can do point location in a couple of different ways. It's written by smart people with a good understanding of the algorithms they're implementing and the computers the algorithms are going to use. You probably won't be able to find anything too much faster that still works correctly.

With that said, Haran and Halperin compared the performance of CGAL's various algorithms. They used a modern computer as of 2008 and they made up a lot of test data and tried CGAL's different point location strategies on each test case. Among other things, they have a case of about 1.4 million randomly-placed edges where their best data structure only needs about 190 microseconds to answer a point location query.

This is very fast considering the complexity of typical point location algorithms --- I couldn't do that myself. And the theory tells us that it grows like O(log n). However, that O(log n) is several orders of magnitude slower than the O(log n) time it takes to search a sorted array. Bear that in mind when you do computational geometry; the constants matter and they're often not very small.

Answer 2

This problem can be categorized as a classic point-location problem.

• The preprocessing would include calculating convex hull for the set of points, and the line segments of the convex hull would be used in the next step (or the whole of CH as a region).

• There are many standard O(log n) query-time algorithms for this kind of problems (http://en.wikipedia.org/wiki/Point_location) like Kirkpatrick triangulation, randomized trapezoidal maps, etc..

Also note that in expectation, the number of points in CH(S) is O(log N) where N is the number of total points in S. So the number of line segments considered for point location is already reduced to O(log N), which means that the query time is actually O(log log N) in expectation (in terms of total points in S).

Answer 3

You should be able to do this using a sweep algorithm (like rasterization, say using a horizontal sweep line). Building up the sorted edges of vertices is n*log(n), but once sorted you could find set the sweep line based on point q and find the edges that the sweep line crosses.

Rasterization is simplified in the convex case since you don't have to worry about concavities in the sweep line.

A simple outline is to go around the polygon, constructing edge objects, using the winding to determine left and right sides. All y-values for each point go into a sorted list (or array, or set, or map, whatever).

Your point q.y is used to look up the edge(s) in left and right sides, then you can simply determine if q.x is between the left and right coordinates. You can compute the convex hull first to make sure your left/right sides are convex.

(Wow, in searching out raster-scan conversion, I came across the notes from my undergrad class here from the year after I graduated.)

Answer 4

struct point {
     LL x,y ;
} C[100010];


/*return area of triangle */
LL areaTriangle(const point &a, const point &b, const point &c) {
    return (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
}

/*An user define function to calculate where a point p inside a convex hull or not */

bool inConvexPoly(int N, const point p) {

/*Input: C is an array with vertex x, y of a convex hull, points must be anticlock-wise, If it's clockwise then just reverse it. p is a point and we have to find does p inside polygon C or not*/

/*Most important part, finding two point using binay search such that point p may be lie inside the trianle
  made by those two points and point0 or point p may be lie inside the triangle which is
  made by point0, point_last, point_start */


LL start = 1, last = N - 1;
while(last - start > 1) {
    LL mid = (start + last) >> 1;
    if(areaTriangle(C[0], C[mid], p) < 0)   last = mid;
    else    start = mid;
}

/*Area of triangle form by point0, start point and last point*/
LL r0 = abs(areaTriangle(C[0], C[start], C[last]));


/*If point p is inside a triangle then the area of that triangle must be equal to
  the area ((point0, poin1, p) + (point0, point2, p) + (point1, point2, p))
  here point0 = C[0], point1 = C[start], point2 = C[last]*/

LL r1 = abs(areaTriangle(C[0], C[start], p));
LL r2 = abs(areaTriangle(C[0], C[last], p));
LL r3 = abs(areaTriangle(C[start], C[last], p));

/*Point p must not lie on any border line of the convex hull, So if the area is 0 then that three point lie on the
  same line */

LL r4 = areaTriangle(C[0], C[1], p);
LL r5 = areaTriangle(C[0], C[N - 1], p);

/*If the area of triangle form by point0, start and last point is equal to area
  from by triangle (point0, last, p) + (point0, start, p) + (last, start, p)
  and p don't lie on start-last line, point0-point1 line, point0-point[N - 1] line
  then the point p inside the convex hull */


 return (r0 == (r1 + r2 + r3) && r3 != 0 && r4 != 0 && r5 != 0);
}

 /*Try to draw picture for better understand */ 

 //End

Answer 5

You can do it in Log(h) where h is the amount of point being the already calculated hull points. It is totally false that it is bound by Log(n) although this is what is written in Wikipedia.

You should note that Wikipedia "Convex hull algorithms" is filtered by David Eppstein which you refer. This guy prevent useful information to be added. If that guy would accept to add useful information (new algorithm) and would understand it, he will realize that you can achieve your goal in O(Log h).Please look at the Wikipedia page for the history of the page.

In algorithm Ouellet convex Hull AVL you can use intermediate result (avl tree by quadrant) and look inside directly. You will achieve your goal in the fastest way possible (best performance: Log(h)).

2 important points:

• You have to identify the quadrant first. You should check if it could be a quadrant boundary itself. After, using either only root point for disjoint quadrant, or using the cross product with first and last point of quadrant to know if its to the right (in case of cross product, if no quadrant is found it is because the point can't be a hull point - no need to identify the quadrant).
• Points are ordered by the x coordinate.

If I could find some time, I will add an interface to my class to check/add new point dynamically. But you can do it right now: get the convex hull intermediate result and use it directly (see the 2 important points) .

Answer 6

An alternative solution using angles:

Pick some point C inside the convex hull using some heuristic of your choice.

Pick some line L passing through C, for instance the line parallel to the OX axis.

For every point P on the convex hull, calculate the angle between the line CP and L and use it to sort the convex hull points.

Now if you want to know if some given point T is inside the convex hull, calculate the angle between the lines CT and L and using binary search look for the points in the convex hull which are just after and before it (A and B respectively).

Now you only have to check it T is at the same side of the line AB than C (inside) or not (outside).