# Partition points on a 2d plane with arbitrary line segment

Let's say I have a 11x11 grid with a few points (around 8) marked in the grid. One of the points is in the center cell. Call it point P.

I choose a point other than P and connect it with a line segment to P. Call that point C1

I choose another point that is not C1 and connect it with a line segment to P. Call that point C2.

Now, if we extend the line segments out from P to the edges of the grid, then the grid will be split into two regions A and B.

How can I determine which of the remaining points are in A and B efficiently?

• I thought of connecting the test point to C1 and C2 and then defining the sets A and B as: A: resulting polygon is convex. B: polygon is complex or simple concave – bgoosman Nov 6 '13 at 7:03
• If it is only $8$, then best bet is prolly brute force checking; it is an interesting question for arbitrary number of points. – Realz Slaw Nov 6 '13 at 7:40
• For such a tiny number of points, just brute-force it. For the more general problem, look up "Half-space range searching" in computational geometry. – David Richerby Nov 6 '13 at 12:51