如何检查点是否属于 ConvexShape? [英] How to check if point belongs to ConvexShape?
问题描述
我为我的平台游戏编写了地图编辑器.我正在使用 SFML.地图由多边形组成 - ConvexShapes.我需要通过单击它们来添加 ConvexShapes 的选择.我知道我可以使用 cv.getLocalBounds() 来获取矩形并接下来检查它，但我需要更精确的解决方案.如何检查点击的点是否属于任何形状?
基于问题评论
如果它们的数量每边都是奇数，则该点属于该形状.那么简单:
bool contains(sf::ConvexShape shape, sf::Vector2f point){std::vectorintersectPoints = getIntersectionPoints(shape, point);int nodesAtLeft = 0;int nodesAtRight = 0;for (sf::Vector2f po : intersectPoints){如果(po.x < point.x){左节点++；}否则 if(po.x > point.x){节点在右++;}}返回 ((nodesAtLeft % 2) == 1) &&((nodesAtRight % 2) == 1);} 那么，我们如何获得这些交点呢?我们应该检查形状的每一边在哪里交叉点与由我们给定的点确定的水平线.请注意，交叉点可能远离形状，由于交叉点的计算考虑整条线，不是线段
所以，一旦我们得到了那个交叉点，我们应该检查它是否属于该段.
std::vectorgetIntersectionPoints(sf::ConvexShape 形状，sf::Vector2f 点){std::vector相交点；SF::Vector2f p;布尔穿越线；//这将用于避免特殊情况下的重复点如果(shape.getPointCount()<3){返回相交点；}sf::FloatRect bounds = shape.getLocalBounds();//为了确定水平线，我们使用两个点，一个在形状的最左边(实际上是它的边界)，另一个在最右边线点线，形状线；pointLine.p1 = sf::Vector2f(bounds.left, point.y);pointLine.p2 = sf::Vector2f(bounds.left + bounds.width, point.y);unsigned int nPoints = shape.getPointCount();for (int i = 0; i 我认为检查一个点 C 是否属于一个段(由点 A 和 B 定义)的最简单方法是通过距离检查，如:
distance(A,C) + distance(C,B) == distance(A,B)
但由于这可能会过于严格，我对其进行了调整以考虑一点误差范围:
abs((distance(A, C) + distance(C, B)) - distance(A, B)) <边距
在我忘记之前，这是如何定义Line
struct Line{SF::Vector2f p1;SF::Vector2f p2;bool contains(sf::Vector2f point) const{浮动保证金 = 0.1;返回 std::abs((distance(p1, point) + distance(point, p2)) - distance(p1, p2)) <利润;}};有了这个，现在唯一剩下的就是计算两条给定线之间的交点.真诚的，我不打算解释这个(主要是因为我刚刚从
可能是一篇很长的帖子，但我已经尽量说清楚了.
I wrote map editor to my platform game. I'm using SFML. Map consists of polygons - ConvexShapes. I need to add selection of ConvexShapes by clicking on them. I know that I can use cv.getLocalBounds() to obtain rectangle and next check that but I need more precise solution. How to check if clicked point belongs to any shape?
Based on question comments link, this is what I got.
Using the algorithm described there, we could determine if a given point is inside a shape counting how many crossing points are on each side
If the number of them are odd on each side, the point belongs to the shape. Easy then:
bool contains(sf::ConvexShape shape, sf::Vector2f point){
std::vector<sf::Vector2f> intersectPoints = getIntersectionPoints(shape, point);
int nodesAtLeft = 0;
int nodesAtRight = 0;
for (sf::Vector2f po : intersectPoints){
if (po.x < point.x){
nodesAtLeft++;
}
else if(po.x > point.x){
nodesAtRight++;
}
}
return ((nodesAtLeft % 2) == 1) && ((nodesAtRight % 2) == 1);
}
So, how do we get those intersection points? We should check for each side of the shape where is the crossing point with the horizontal line determined by our given point. Note that the crossing point could be far away from the shape, due to calculation of the crossing point consider whole lines, not segments
So, once we have got that crossing point, we should check if it belongs to the segment.
std::vector<sf::Vector2f> getIntersectionPoints(sf::ConvexShape shape, sf::Vector2f point){
std::vector<sf::Vector2f> intersectPoints;
sf::Vector2f p;
bool crossingLine; // This will be used to avoid duplicated points on special cases
if (shape.getPointCount() < 3){
return intersectPoints;
}
sf::FloatRect bounds = shape.getLocalBounds();
// To determine horizontal line, we use two points, one at leftmost side of the shape (in fact, its bound) and the other at rightmost side
Line pointLine, shapeLine;
pointLine.p1 = sf::Vector2f(bounds.left, point.y);
pointLine.p2 = sf::Vector2f(bounds.left + bounds.width, point.y);
unsigned int nPoints = shape.getPointCount();
for (int i = 0; i < nPoints; ++i){
try{
shapeLine.p1 = shape.getPoint(i % nPoints); // Last one will be nPoints-1
shapeLine.p2 = shape.getPoint((i + 1) % nPoints); // So this one must be 0 in order to check last side (returning to origin)
crossingLine = (shapeLine.p1.y >= point.y && shapeLine.p2.y <= point.y) || (shapeLine.p2.y >= point.y && shapeLine.p1.y <= point.y);
p = intersection(shapeLine, pointLine);
if (crossingLine && shapeLine.contains(p))
intersectPoints.push_back(p);
}
catch (std::runtime_error e){
}
}
return intersectPoints;
}
I think the easiest way to check if a point C belongs to a segment (defined by points A and B) is by doing a distance check like:
distance(A,C) + distance(C,B) == distance(A,B)
But as this one could end being too restrictive, I've adapted it to consider a little error margin:
abs((distance(A, C) + distance(C, B)) - distance(A, B)) < margin
Before I forget, this is how a Line is defined
struct Line{
sf::Vector2f p1;
sf::Vector2f p2;
bool contains(sf::Vector2f point) const{
float margin = 0.1;
return std::abs((distance(p1, point) + distance(point, p2)) - distance(p1, p2)) < margin;
}
};
With this, the only thing left now is to calculate the intersection points between two given lines. Sincerely, I'm not going to explain this (mainly because I've just copied this from wikipedia)
sf::Vector2f intersection(Line lineA, Line lineB){
int x1 = lineA.p1.x;
int y1 = lineA.p1.y;
int x2 = lineA.p2.x;
int y2 = lineA.p2.y;
int x3 = lineB.p1.x;
int y3 = lineB.p1.y;
int x4 = lineB.p2.x;
int y4 = lineB.p2.y;
try{
double retX = ((x1*y2 - y1*x2)*(x3 - x4) - (x1 - x2)*(x3*y4 - y3*x4)) / ((x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4));
double retY = ((x1*y2 - y1*x2)*(y3 - y4) - (y1 - y2)*(x3*y4 - y3*x4)) / ((x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4));
return sf::Vector2f(retX, retY);
}
catch (std::exception){
throw new std::exception("");
}
}
If the lines are parallel or the same line, both denominators are zero, and it will throw an DivideByZero exception, not really a problem simply there is not intersection.
I've made also a snippet to test this:
int main()
{
sf::RenderWindow v(sf::VideoMode(600,400), "SFML");
sf::ConvexShape shape;
std::vector<sf::Vector2i> points;
std::vector<sf::CircleShape> intPoints;
shape.setPointCount(0);
shape.setOutlineColor(sf::Color::Blue);
shape.setFillColor(sf::Color::Black);
shape.setOutlineThickness(1);
while (v.isOpen()){
sf::Event event;
while (v.pollEvent(event)){
if (event.type == sf::Event::Closed)
v.close();
else if (event.type == sf::Event::MouseButtonPressed){
if (event.mouseButton.button == sf::Mouse::Button::Left){
// Add a point to the shape
intPoints.clear();
sf::Vector2i p = sf::Mouse::getPosition(v);
points.push_back(p);
shape.setPointCount(points.size());
for (int i = 0; i < points.size(); ++i){
shape.setPoint(i, sf::Vector2f(points[i]));
}
}
else if (event.mouseButton.button == sf::Mouse::Button::Right){
// Delete shape
points.clear();
intPoints.clear();
shape.setPointCount(0);
}
else if (event.mouseButton.button == sf::Mouse::Button::Middle){
// Set testing point
intPoints.clear();
sf::Vector2i p = sf::Mouse::getPosition(v);
if (contains(shape, sf::Vector2f(p))){
std::cout << "Point inside shape" << std::endl;
}
else{
std::cout << "Point outside shape" << std::endl;
}
auto v = getIntersectionPoints(shape, sf::Vector2f(p));
for (sf::Vector2f po : v){
sf::CircleShape c(2);
c.setFillColor(sf::Color::Green);
c.setOrigin(1, 1);
c.setPosition(po);
intPoints.push_back(c);
}
// testing point added too, to be visualized
sf::CircleShape c(2);
c.setFillColor(sf::Color::Red);
c.setOrigin(1, 1);
c.setPosition(sf::Vector2f(p));
intPoints.push_back(c);
}
}
}
v.clear();
v.draw(shape);
for (sf::CircleShape c : intPoints){
v.draw(c);
}
v.display();
}
return 0;
}
Some captures:
May be a long post, but I've tried to be clear.
这篇关于如何检查点是否属于 ConvexShape?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
