5

If I have an array of points (x,y,z) and am given a single point (x,y,z), what code do I use to determine if that point resides within the shape defined by the array?

I am drawing a blank on this one...

I'm using C#

EDIT

Thanks for the responses guys, from the comments I have found this link (http://alienryderflex.com/polygon/) which explains the process quite well.

Thanks!

FYI:

bool pointInPolygon() {
    
      int      i, j=polySides-1 ;
      boolean  oddNodes=NO      ;
    
      for (i=0; i<polySides; i++) {
        if (polyY[i]<y && polyY[j]>=y
        ||  polyY[j]<y && polyY[i]>=y) {
          if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
            oddNodes=!oddNodes; }}
        j=i; }
     
      return oddNodes; }

It'll need some work, but thats the guts of it.

Thanks again

Community
  • 1
  • 1
Matt
  • 4,140
  • 9
  • 40
  • 64
  • 1
    possible duplicate of [C# Point in polygon](http://stackoverflow.com/questions/4243042/c-point-in-polygon) – Jim Lewis Feb 10 '11 at 21:49
  • 1
    This is a well known propblem. See http://en.wikipedia.org/wiki/Point_in_polygon – Elian Ebbing Feb 10 '11 at 21:50
  • 2
    Your problem is underspecified. How does the array define the shape? Is it the convex hull of the points in the array? Or is there some kind of multipatch triangle strip order which defines a polyhedron? – Nordic Mainframe Feb 10 '11 at 21:52
  • Maybe not quite an exact duplicate of the other post I found -- just noticed that Matt is looking for a solution in 3 dimensions. – Jim Lewis Feb 10 '11 at 21:52
  • 1
    @Jim, @Elian. No not it's not. It's point in POLYHEDRON. He has three dimensional coordinates. – Nordic Mainframe Feb 10 '11 at 21:53
  • @Elian: Does it differ when the shape is 3D? @Michal: not that simple; min/max XYZ gives you a "hitbox"; a cube within which the shape will fit. The point could be outside the shape but in the hitbox. – KeithS Feb 10 '11 at 21:53
  • Ah I hadn't seen that Question when I searched. Thanks for that.. – Matt Feb 10 '11 at 21:54
  • 1
    http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/ – Jaroslav Jandek Feb 10 '11 at 21:58

3 Answers3

16

Use a point that you know is outside the shape, and check if the line from that point to the given point passes through the surfaces of the shape. If it passes through an odd number of surfaces, the given point is inside the shape.

Guffa
  • 687,336
  • 108
  • 737
  • 1,005
  • 2
    Excellent answer, but actually doing this is harder than it sounds. – KeithS Feb 10 '11 at 22:03
  • 5
    You have just created 3 new questions for Matt. – Amy West Feb 10 '11 at 22:04
  • This is the method I'll use.. Thanks for your help – Matt Feb 10 '11 at 22:27
  • A better way of doing this might be to start with the point you want to test and keep increasing its x value in a loop. Every time your current position is over a wall coordinate, add 1 to your counter (unless the previous point was also a wall). If your counter is odd after you've iterated over your horizontal window, the original point was inside the shape. If the counter is even, the original point was outside the shape. You can make this method faster by using a QuadTree to check if a coordinate is a wall. You could also do a quick rectangle check at the start to dismiss far away points. – John Kurlak Jun 04 '12 at 15:58
  • This is a 2D solution, but the conclusion is still valid. Pick a direciton and go, if there is an odd number of intersections, you are inside the shape, otherwise you aren't. You just have to modify the if statements and loops appropriately to account for 3 dimensions, rather than 2. – Nevyn Mar 08 '13 at 21:44
  • @Nevyn: No, as stated it's a solution that is agnostic of dimensions. The solution works just as well with two or three dimensions, or even four or fourteen. The actual implementation gets more complicated with more dimensions, of course. – Guffa Mar 08 '13 at 23:03
2

Further to Guffa's answer, it's harder than it sounds to determine if a line intersects a surface. Here's the math behind that: Intersection of lines and planes. You have to take that basic algorithm (which involves finding the normal of each surface to that point, then determining the angle between the normal and the line to form a right triangle that you find the third point of; WPF's Media3D library has functions on Points and Vectors that make all this easier), then determine if the point you found intersects the plane of the surface within the bounds of that surface. To do THAT, you can take any 2D projection of that surface that has an area > 0, and perform the "point in polygon" test, which is the 2D version of the "point in polyhedron" test you're trying to do.

Good luck.

KeithS
  • 70,210
  • 21
  • 112
  • 164
0

If you are drawing Shapes on a Canvas this is a quick and easy Solution.

    private void Canvas_MouseMove(object sender, MouseEventArgs e)
    {
        if (e.OriginalSource is Polygon)
        {
            //do something
        }
    }

"Polygon" can be any shape from System.Windows.Shapes.

Florian_Schaf
  • 47
  • 1
  • 6