确定一个点是否在形状内 [英] determine whether a point is within shape
问题描述
我正在尝试确定一个形状内的一个点。
我找到了一个算法来完成这项工作
http://www.ecse.rpi.edu/Homepages/wrf/Research/ Short_Notes / pnpoly.html
我用方形测试了算法。
总角落一个正方形= 4
然而它会给我一个错误的结果。（见下面的输出结果）我的代码之后
Shape.h
I am trying to determine whether a point within a shape.
I found a algorithm that does the job
http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
I tested the algorithm out with a square shape.
total corners of a square = 4
but however it returns me a wrong result.(see my output results below) after my codes
Shape.h
#ifndef __Shape__Shape__
#define __Shape__Shape__
class Shape {
private:
int xArray[4];
int yArray[4];
int x;
int y;
public:
bool inPoly(int x,int y);
void pointInShape();
};
#endif
Shape.cpp
Shape.cpp
#include "Shape.h"
#include <iostream>
bool Shape::inPoly(int x,int y) {
xArray[0] = 1;
xArray[1] = 1;
xArray[2] = 3;
xArray[3] = 3;
yArray[0] = 1;
yArray[1] = 3;
yArray[2] = 3;
yArray[3] = 1;
int i, j, nvert = 4, c = 0;
for (i = 0, j = nvert - 1; i < nvert; j = i++) {
if ( ((yArray[i]>y) != (yArray[j]>y)) &&
(x < (xArray[j]-xArray[i]) * (y-yArray[i]) / (yArray[j]-yArray[i]) + xArray[i]) )
c = !c;
}
return c;
}
void Shape::pointInShape() {
std::cout << "results" << std::endl;
std::cout << inPoly(1,1) << std::endl;
std::cout << inPoly(1,2) << std::endl;
std::cout << inPoly(1,3) << std::endl;
std::cout << inPoly(2,1) << std::endl;
std::cout << inPoly(2,2) << std::endl;
std::cout << inPoly(2,3) << std::endl;
std::cout << inPoly(3,1) << std::endl;
std::cout << inPoly(3,2) << std::endl;
std::cout << inPoly(3,3) << std::endl;
}
main.cpp
main.cpp
#include "Shape.h"
#include <iostream>
int main() {
Shape shape;
shape.pointInShape();
}
它会将此输出返回给我
it returns me this output
results
1 <-- (means that 1,1 is is within polygon)
1 <-- (means that 1,2 is is within polygon)
0 <-- (means that 1,3 is is not within polygon)
1 <-- (means that 2,1 is is within polygon)
1 <-- (means that 2,2 is is within polygon)
0 <-- (means that 2,3 is is not within polygon)
0 <-- (means that 3,1 is is not within polygon)
0 <-- (means that 3,2 is is not within polygon)
0 <-- (means that 3,3 is is not within polygon)
右边正确的输出应该只返回2,2为真实
by right the correct output should only return 2,2 as true
results
0 <-- (means that 1,1 is not within polygon)
0 <-- (means that 1,2 is not within polygon)
0 <-- (means that 1,3 is not within polygon)
0 <-- (means that 2,1 is not within polygon)
1 <-- (2,2 is is within polygon)
0 <-- (means that 2,3 is is not within polygon)
0 <-- (means that 3,1 is is not within polygon)
0 <-- (means that 3,2 is is not within polygon)
0 <-- (means that 3,3 is is not within polygon)
有什么建议/意见吗？
推荐答案
您关联的网站明确说明
The site you linked explicitely states that
PNPOLY将平面划分为多边形内的点并指向多边形外部。 边界上的点被分类为内部或外部。
PNPOLY partitions the plane into points inside the polygon and points outside the polygon. Points that are on the boundary are classified as either inside or outside.
（强调我的）
这意味着算法有效作为指定。
请注意，那里发布的算法应该适用于浮点坐标，边缘可能与坐标轴平行也可能不平行。因此，通常不太可能找到恰好位于边界上的点。
如果您需要不同的结果（例如，边界上的点被归类为外部），那么您需要一个额外的算法来检查这种情况。可以调整比较公式，但我怀疑是否可以在不添加额外的检查和条件的情况下防止除以0，或者捕获位于顶点而不是仅在边缘上的点的情况。 br />
PS：
算法从测试点投射半无限线（与x轴平行）并检查多少它相交的边缘。对于每个交叉点，假设在多边形外部或内部的状态翻转。
交叉点是通过比较线段的倾斜度与线的倾斜度来确定的。测试点指向其中一个端点：如果它更大，那么该线将传递到测试点的左侧，因此不会与光线相交;如果它较低，则该线相交。
这就是修复它的方法：如果倾斜度相等，则测试点位于边界上。这意味着你需要预先检查相等性并在这种情况下中止整个测试：
(Emphasis mine)
This means the algorithm works as specified.
Note that the algorithm published there is supposed to work on floating point coordinates, with edges that may or may not be parallel to the coordinate axes. Therefore it is generally unlikely you'll find a point that lies exactly on the boundary.
If you need a different result (e. g. that points on the boundary are classified as outside), then you either need an additional algorithm that checks specifically this condition. It may be possible to adjust the comparison formula, but I doubt that it is possible without adding additional checks and conditions to prevent division by 0, or to catch the case of a point that lies on a vertex rather than just on an edge.
P.S.:
The algorithm projects a semi-infinite line (parallel to the x-axis) from the test point and checks how many of the edges it intersects. For each intersection, the assumed state of being outside or inside the polygon flips.
The intersection is determined by comparing the inclination of the line segments to that of the line from the test point to one of the end points: if it is greater, then the line passes to the left of the test point and thus is not intersected by the ray; if it is lower, the line is intersected.
And here comes the way to fix it: If the inclinations are equal, then the test point lies on the boundary. This means you need to pre-check equality and abort the entire test in that case:
int i, j, nvert = 4, c = 0;
for (i = 0, j = nvert - 1; i < nvert; j = i++) {
if ((yArray[i]>y) != (yArray[j]>y)) {
int testval = (xArray[j]-xArray[i]) * (y-yArray[i]) / (yArray[j]-yArray[i]) + xArray[i]);
if (x == testval) {
// point is on boundary!
c = 0; // set indicator to "not inside"
break; // abort loop
}
if (x < testval)
// intersection found
c = !c;
}
这篇关于确定一个点是否在形状内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
