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

30 views (last 30 days)
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?
  4 Comments
Matt J
Matt J on 16 Jul 2013
Edited: Matt J on 16 Jul 2013
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
Joshua on 17 Jul 2013
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.

Sign in to comment.

Accepted Answer

Matt J
Matt J on 16 Jul 2013
Edited: Matt J on 16 Jul 2013
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..
  8 Comments
Joshua
Joshua on 17 Jul 2013
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
Matt J on 17 Jul 2013
Edited: Matt J on 17 Jul 2013
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.

Sign in to comment.

More Answers (0)

Categories

Find more on Elementary Polygons in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!