Determining if a point is inside a polygon or along the outer edge

I have a 2D polygon in 3 dimensions. Some of the points are inside of this polygon, and some define the outer edge of it. How can I detect which points are inside the polygon, and which define the outside of it?

My initial idea is to create a vector that is defined by a set of 2 points, then see if that vector intersects a line segment in the positive and negative direction. If it only intersects on one side, then the point is on the outside of the polygon. If it intersects a line segment in the positive and negative direction, then the point is inside the polygon. But, in order for that to be any use, I need to figure out a condition that tells me if the line defined by that vector intersects any of the line segments defined by the other points.

Any ideas?

[Jos (10584)]

You mean that the vertices are in a single plane that is oriented in 3D space? You could rotate the plane parallel to the XY plane, transform the points accordingly, and then use INPOLYGON.

[the cyclist]

If all the points are guaranteed to be on the same plane, can you just project onto (x,y) instead of rotating? Seems easier if it works.

[Matt J]

No matter what you do, you will need to define some tolerances. No set of 2D points are ever exactly coplanar in 3D when floating point calculation errors are involved. Likewise, no 3 points that are all supposed to lie at the edge of a polygon can be relied upon to be exactly colinear.

[Joshua]

Jos, the cyclist, what you guys suggest sounds like it might work. I didn't make it very clear, but in this problem, I don't know what points define the outside of the polygon, so idk if inpolygon would work.

What I'm doing is taking a geometric shape, projecting its points onto a plane, and then trying to get the outline of the projected shape.

Answer 1

[Matt J]

If the polygon is convex, then using vert2lcon and lcon2vert available here you could do

 [A,b,Aeq,beq]=vert2lcon(points);

vertices = lcon2vert(A,b,Aeq,beq);

All points that are not vertices are considered by the code as lying inside of it or along an edge, up to the tolerance parameters of the code.

If you really have to distinguish between interior points and edge points. the points satisfying

 A*points<=b-tolInterior

can be considered interior points up to a tolInterior tolerance parameter set by you..

[Joshua]

What are A, b, Aeq, and beq supposed to represent?

[Matt J]

That is explained in the documentation at the link I provided.

Briefly, they contain data for the linear equalities/inequalities describing the polygon.

[Joshua]

I get the following error when trying to run those

Warning: qhull precision warning: The initial hull is narrow (cosine of min. angle is 0.9999999999999999). A coplanar point may lead to a wide facet. Options 'QbB' (scale to unit box) or 'Qbb' (scale last coordinate) may remove this warning. Use 'Pp' to skip this warning. See 'Limitations' in qh-impre.htm.

Error using lcon2vert>con2vert (line 308) Non-bounding constraints detected. (Consider box constraints on variables.)

Error in lcon2vert (line 236) Zt=con2vert(AAA,bbb,TOL,checkbounds);

Error in projection_v14 (line 84) Pr = lcon2vert(A,b,Aeq,beq);

Any idea what's causing that?

[Matt J]

Not without seeing the data.

[Joshua]

This is the matrix of points that define the polygon

Pr =

     -0.51035     -0.46508     -0.52103
      0.42904     -0.26068     -0.64412
     -0.30595     -0.15447     -0.10588
      0.63344     0.049927     -0.22897
     -0.63344    -0.049927      0.22897
      0.30595      0.15447      0.10588
     -0.42904      0.26068      0.64412
      0.51035      0.46508      0.52103

And these are the outputs

EDU>> A

A =

     -0.24618       0.8303         -0.5
      0.24618      -0.8303          0.5

EDU>> b

b =

    5.594e-08
   8.7354e-09

EDU>> Aeq

Aeq =

     []

EDU>> beq

beq =

     []

[Matt J]

If Aeq=[] and beq=[], it means that your data aren't co-planar within the default tolerance of vert2lcon. When I relax the tolerance to 1e-5, I seem to get the right answer.

>> [A,b,Aeq,beq]=vert2lcon(Pr,1e-5);
>> vertices = lcon2vert(A,b,Aeq,beq)

vertices =

     -0.5103   -0.4651   -0.5210
     -0.6334   -0.0499    0.2290
     -0.4290    0.2607    0.6441
      0.4290   -0.2607   -0.6441
      0.6334    0.0499   -0.2290
      0.5103    0.4651    0.5210

[Joshua]

thank you, Matt, that fixed it and works perfectly. Idk if it matters to you, but I have my own code that was able to do this (only for rectangular prisms though), and your function and mine give end results that are off by a max of 10^-12 (a few are off by zero), so it's got great accuracy and precision.

[Matt J]

Glad it's working Joshua, but I'm starting to think that it's better, since you know a prior that it's a 2D polygon, to take advantage of that and pre-map the coordinates into 2D space, like Jos and cyclist were suggesting.

At that point you could still use vert2lcon to derive inequalities for the polygon from the 2D coordinates, but it would be more stable and you wouldn't have to fuss with tolerances.