5
$\begingroup$

Say, I am given a point and a closed curve. I don't know anything about the curve (where it is, what it is, its size etc.;say it is hidden somewhere)."I just can't see the curve but I can see the point where it is." I am supplied with a pencil and a ruler with no measurement marks on it, or in other words, I can only draw straight lines with the ruler, nothing else I can do with the ruler.

What is the general procedure that I should follow to determine whether the point lies inside the curve or outside it irrespective of the nature, size, shape or any other parameter of the curve?

$\endgroup$
  • 4
    $\begingroup$ There is no terminating procedure if you know nothing whatsoever about the curve. The usual procedure which just draws an arbitrary ray from the point and counts the number of times the ray crosses the curve assumes that the curve is bounded enough that you know when you can stop counting. $\endgroup$ – DRF Oct 15 '15 at 9:22
  • $\begingroup$ By the Jordan curve theorem, all simple closed curves have a well-defined interior and exterior. They know that it's a closed curve―if it were unbounded, the curve would no longer be closed, would it? $\endgroup$ – eyqs Oct 24 '15 at 5:33
4
+50
$\begingroup$

What the OP really wants, I think, is a crossing number algorithm for a simple closed continuous curve. Such a curve can be considered, however, as the limiting case of a simple polygon, for its edges becoming infinitesimally small. A relevant reference therefore may be this Wikipedia one:

and especially the crossing number algorithm.
But there is much more to tell about the Inside / Outside Problem, once you take a good look at it.
After some (in vain) attempts to answer the question in a concise manner, and while making too many duplicates of existing material, I've decided to simply redirect to my best shot so far:

If the points of the simple closed curve are considered as pixels (i.e. integer coordinates), then we can even devise a never fail algorithm (only assuming that our picture is not too large).

It is seen in the picture below that, for a continuous curve, simple and straightforward application of the crossing number algorithm will be OK for the points $A$ and $B$, but it certainly will go wrong for the points $C$ and $D$. According to Murphy's law , Anything that can go wrong will go wrong. Meaning that ignoring special cases, especially in a computational geometry environment, sooner or later, will be disastrous. It is noticed that the "wrong" cases have to do with rays that are tangent to the curve.

enter image description here

$\endgroup$
0
$\begingroup$

By the order of intersection between curve and a cutting line which produces two points of intersection $P,Q$.

If given point is $O$, the line cuts the closed curve at extreme points $P$ and $Q$, then proceeding in one direction without retracing path,

you are outside if the order is $ O,P, Q $ or $ Q,P,O $ and inside if the order is $ P,O,Q $ or $ Q,O,P.$

Ignore (all even number of) points of intersection between the extreme points.

$\endgroup$
  • $\begingroup$ I did not understand that part where you said the curve and the line intersect at 2 points.Why only 2 points? $\endgroup$ – SchrodingersCat Oct 15 '15 at 9:59
  • $\begingroup$ After ignoring all points lying between extreme points, as already stated. $\endgroup$ – Narasimham Oct 15 '15 at 12:30
  • $\begingroup$ You do not know whether the number of such points of intersection will be finite or infinite. $\endgroup$ – SchrodingersCat Oct 22 '15 at 15:50
  • $\begingroup$ You mean fractals? For non self-intersecting boundary there would be finite number of points. Please give some examples for the type of oval given with infinite number of cross-overs by a straight line intersection. $\endgroup$ – Narasimham Oct 22 '15 at 16:11

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.