6

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?

J. M. ain't a mathematician
  • 75,051
SchrodingersCat
  • 24,472
  • 4
    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. – DRF Oct 15 '15 at 09:22
  • 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? – eyqs Oct 24 '15 at 05:33

2 Answers2

4

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

Han de Bruijn
  • 17,070
  • Sorry for necropost, is it true that Jordan curves in " General Position" ( not tangent to each other) intersect an even number of times ( including 0 if they are disjoint). I reason that, given curves C1, C2 intersecting, every time C1 intersects C2 the curve C1 must come from the exterior of C1 , enter into the interior of C1 and ultimately exit C2. So for every intersection there are two points: entrance and exit, meaning the number of intersection points is even? – MSIS Nov 20 '19 at 00:30
  • @MSIS: Honestly, I don't know. Perhaps it's a good idea to post this as a question at the MSE forum? – Han de Bruijn Nov 20 '19 at 15:28
  • I asked it. Here is the link if you're interested: https://math.stackexchange.com/questions/3443990/parity-of-intersection-of-jordan-curves-in-general-position – MSIS Nov 20 '19 at 19:13
0

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.

Narasimham
  • 40,495
  • I did not understand that part where you said the curve and the line intersect at 2 points.Why only 2 points? – SchrodingersCat Oct 15 '15 at 09:59
  • After ignoring all points lying between extreme points, as already stated. – Narasimham Oct 15 '15 at 12:30
  • You do not know whether the number of such points of intersection will be finite or infinite. – SchrodingersCat Oct 22 '15 at 15:50
  • 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. – Narasimham Oct 22 '15 at 16:11