3

I'm in no way a professional programmer so, pls don't expect a sophisticated approach or language here. I'll however appreciate your advice and recommendations to materialize an algorithm which, at a later stage, I could programmatically add to my project... Here is the problem:

Imagine an arbitrary point (Point X) in space with the following properties:

  • has coordinates
  • lies on a 2D-surface
  • is stationary
  • belongs to a single area (boundary coordinates of which are also known) at any given time. Namely, it's the only "child" of its "parent" element. Again, if it doesn't sit in one area, it definitely sits inside another one!

An area is NOT a simple square, quadrangle, or a circle but instead is an irregular shape.

Now, my question is: How can I determine: (i) if Point X lies inside that particular area and NOT the adjacent one; (ii) which specific area (among a set of areas A, B, or C) the point belongs to?!? See the linked image to better visualize the problem:

PS: I perused a possibility of dealing with Point in Polygon problem (especially, the "ray casting algorithm" sounds quite smart!) but it doesn't seem to be a solution since (i) areas may be adjacent to each other; (ii) I need to determine the area a point belongs to more than it lies inside/outside of it.

Thank you very much in advance!!!

Mohsen Safari
  • 6,669
  • 5
  • 42
  • 58
Rustam Alhas
  • 69
  • 6
  • 1
    How do the "boundary coordinates" of the areas represent the actual boundary of the area if the area's boundary might have curvature? Are you using some sort of curve parameterization or approximating the area by a polygon? – ajd Sep 08 '12 at 16:36
  • A variation of the ray-casting algorithm would probably work. If you projected one ray out from your point and looked at the first edge that it hit, you would know your point was inside of one of the (up to) two areas that share that edge. Then you could just use the ray-casting algorithm twice for each of the two candidate areas. – ajd Sep 08 '12 at 16:39
  • Sorry, my fault - I further edited my question: the coordinates of shape (area) segments are defined in 2D, there are no curvatures! – Rustam Alhas Sep 08 '12 at 16:55
  • 1
    Do you have the co-ordinates of the bounded regions (areas) ? If yes, then how many co-ordinates do you have ? I do not know what is the exact input data you are having. I am assuming you have sufficient co-ordinates for the areas so that the areas can be drawn with a good approximation. In that case, one solution can be to find out the points which have max. & min. value of X co-ordinate. This gives the bounds of an area on X-axis. If your point lies inside that area, its x co-ordinate must be between these values. Do the same for the Y coordinate. But, this may not be an efficient algorithm. – sandyiscool Sep 08 '12 at 18:12
  • Not sure what you mean by "I need to determine the area a point belongs to more than it lies inside/outside of it." Unless you're using a meaning of "belongs to" that I don't understand, the way you determine which area the point belongs to is by testing whether it's inside each of the possible areas in your set: it will be inside exactly 1 of them. (You may be able to speed things up by eliminating some areas as possibilities using bounding boxes/circles as sandyiscool suggested.) – j_random_hacker Nov 18 '12 at 05:54

1 Answers1

0

A programmer would do it so:

  1. A function is taking as parametres an array of areas and a point.

  2. Make a cycle - check ALL your areas and for every one

    check by the ray casting algorythm if the point belongs there.

    If no, continue the cycle,

    If yes, finish the function returning the number of the current area.

  3. If you are out of areas, return -1.

Of course, you can improve the algorythm, taking into account the common borders, not repeating the counting of angles for them, but such algorythms are obviously out of your possiblilities now. And even a good programmer will start by something easy, but working.

Gangnus
  • 24,044
  • 16
  • 90
  • 149