1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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, 2013 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, 2013 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, 2013 at 12:51

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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