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?

  • $\begingroup$ 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 $\endgroup$ – bgoosman Nov 6 '13 at 7:03
  • 2
    $\begingroup$ If it is only $8$, then best bet is prolly brute force checking; it is an interesting question for arbitrary number of points. $\endgroup$ – Realz Slaw Nov 6 '13 at 7:40
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 6 '13 at 12:51

Hint: Instead of storing them as cartesian points, store them as polar coordinates (with a tiny drop of preprocessing).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.