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

10 次查看（过去 30 天）
Joshua
Joshua 2013-7-16
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 个评论
显示 2更早的评论
Matt J
Matt J 2013-7-16
编辑：Matt J 2013-7-16
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 2013-7-17
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.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Matt J
Matt J 2013-7-16
编辑：Matt J 2013-7-16
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 个评论
显示 6更早的评论
Joshua
Joshua 2013-7-17
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 2013-7-17
编辑：Matt J 2013-7-17
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.

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Computational Geometry 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by