编码挑战：是多边形中的一个点？ [英] Coding challenge: is a point in a polygon?
问题描述
今天的挑战是迟到但很简单。
给定一组（x，y）点数表示多边形，确定给定的（x，y）点是在多边形内部还是外部。
例如，由点（逆时针）定义的多边形 {（2,0），（4,1），（ 4,4），（2,5），（1,2）和（2,0）} 包含点（3,3）但不包含点（5,4）。
你可以为你做任何数据类型想。双精度浮点，整数，肘 - 没关系。你可以使用你想要的任何语言。你只需要能够提供输入数据并输出问题这是多边形中的这一点。
这里有几篇文章这可能会有所帮助（ Computational Geometry，C ++和Wykobi [ ^ ]和计算几何的类 [ ^ ]）
上周的挑战被 Peter Leow [ ^ ]，特别提及 C64实施 [ ^ ]由Kornfeld Eliyahu Peter和 LINQ实施 [ ^ ]来自Maciej Los。彼得的解释和过度设计的方法让法官大为愉快。彼得 - 发送给我们你的详细信息和一个CodeProject马克杯就好了。
对本周末的挑战表示歉意。多伦多冬天在办公室造成了混乱。
我尝试过：
一把新的雪铲 - 但这并没有多大帮助
Today's challenge is late but simple one.
Given a set of (x,y) points representing a polygon, determine whether a given (x,y) point is inside or outside the polygon.
For example, the polygon defined by the points (counter-clockwise) { (2,0), (4,1), (4,4), (2,5), (1,2) and (2,0) } contains the point (3,3) but does not contain the point (5,4).
You can make the data type whatever you want. Double precision floating point, integer, cubits - it doesn't matter. You can use whatever language you wish to. You just need to be able to supply the input data and get the output to the question "is this point in the polygon".
There are a couple of articles here that may help (Computational Geometry, C++ and Wykobi[^] and Classes for computational geometry[^])
Last week's challenge was won (and that's a loose term) by Peter Leow[^], with special mentions for the C64 implementation[^] by Kornfeld Eliyahu Peter and the LINQ implementation[^] by Maciej Los. Peter's explanation and over-engineered approach amused the judge immensely. Peter - send us your details and a CodeProject mug is on it's way.
Apologies for the lateness of this week's challenge. Toronto winter has caused mayhem in the office.
What I have tried:
A new snow shovel - but that didn't help much
推荐答案
使用OriginalGriff编写的大部分内容添加另一个例子，除了没有foreach循环。
Adding another example using most of what OriginalGriff wrote except no foreach loop.
public class TestPoints {
GraphicsPath path;
public TestPoints(Point[] points) {
path = new GraphicsPath(points);
}
public bool CheckVisible(int x, int y) {
if (null == path) {
return false;
}
Region region = new Region(path);
bool visible = region.IsVisible(x, y);
string output = string.Format("Point ({0}, {1}) is {2} the polygon.", x, y, visible ? "within" : "outside");
Console.WriteLine(output);
return visible;
}
}
public class Program {
public static void Main(string[] args) {
Point[] points1 = new Point[] {
new Point(2, 0), new Point(4, 1), new Point(4, 4),
new Point(2, 5), new Point(1, 2), new Point(2, 0)
};
Point[] points2 = new Point[] {
new Point(2, 0), new Point(44, 1), new Point(44, 46),
new Point(24, 57), new Point(10, 26), new Point(2, 0)
};
TestPoints test = new TestPoints(points1);
test.CheckVisible(3, 3);
test.CheckVisible(5, 4);
test = new TestPoints(points2);
test.CheckVisible(35, 40);
test.CheckVisible(45, 43);
}
}
输出：
点（3,3）是在多边形内。
点（5,4）在多边形之外。
点（35,40）在多边形内。
点（45,43）在多边形之外。
Output:
Point (3, 3) is within the polygon.
Point (5, 4) is outside the polygon.
Point (35, 40) is within the polygon.
Point (45, 43) is outside the polygon.
一些数学的时间！我的代码使用光线投射算法：它查看从给定点到任何方向的光线与多边形相交的次数。如果此数字为奇数，则该点位于多边形内。如果它是偶数，则数字在多边形之外。
Time for some maths! My code uses the ray casting algorithm: it looks at how many times a ray, starting from the given point to whatever direction, intersects with the polygon. If this number is odd, the point is inside the polygon. If it's even, the number is outside the polygon.
/* Usage:
Polygon polygon = new Polygon(new Point(2, 0), new Point(4, 1), new Point(4, 4), new Point(2, 5), new Point(1, 2), new Point(2, 0));
Console.WriteLine(polygon.PointInPolygon(new Point(3, 3))); // True
Console.WriteLine(polygon.PointInPolygon(new Point(5, 4))); // False
*/
public class Polygon
{
Point[] _points;
List<LineSegment> _segments;
public Polygon(params Point[] points)
{
if (points[0] == points[points.Length - 1])
{
_points = points;
}
else
{
_points = points.Concat(new Point[] { points[0] }).ToArray();
// auto-close the polygon
}
_segments = new List<LineSegment>();
for (int i = 0; i < _points.Length; i++)
{
if (i != _points.Length - 1)
{
_segments.Add(new LineSegment(_points[i], _points[i + 1]));
}
}
}
public bool PointInPolygon(Point point)
{
Ray ray = new Ray(point, new Point(point.X + 1, point.Y + 1));
int counter = 0;
foreach (LineSegment segment in _segments)
{
if (segment.IntersectsWithRay(ray))
{
counter++;
}
}
return counter % 2 == 1;
}
}
public class Point
{
public double X { get; private set; }
public double Y { get; private set; }
public Point(double x, double y)
{
X = x;
Y = y;
}
}
public class LineSegment
{
public Point Point1 { get; private set; }
public Point Point2 { get; private set; }
public LineSegment(Point p1, Point p2)
{
Point1 = p1;
Point2 = p2;
}
public bool IntersectsWithRay(Ray ray)
{
Line raySupport = new Line(ray.Origin, ray.AlsoGoesThrough);
Line segmentSupport = new Line(Point1, Point2);
Point intersection = raySupport.IntersectionWithOtherLine(segmentSupport);
if (intersection == null) return false;
bool intersectionOnRay = !((ray.Direction.Item1 == 1 && intersection.Y < ray.Origin.Y) || (ray.Direction.Item1 == -1 && intersection.Y > ray.Origin.Y) ||
(ray.Direction.Item2 == 1 && intersection.X < ray.Origin.X) || (ray.Direction.Item1 == -1 && intersection.X > ray.Origin.X));
double segmentMinX = Math.Min(Point1.X, Point2.X);
double segmentMaxX = Math.Max(Point1.X, Point2.X);
double segmentMinY = Math.Min(Point1.Y, Point2.Y);
double segmentMaxY = Math.Max(Point1.Y, Point2.Y);
bool intersectionOnSegment = intersection.X >= segmentMinX && intersection.X <= segmentMaxX && intersection.Y >= segmentMinY && intersection.Y <= segmentMaxY;
return intersectionOnRay && intersectionOnSegment;
}
}
public class Ray
{
public Point Origin { get; private set; }
public Point AlsoGoesThrough { get; private set; }
public Tuple<int, int> Direction { get; private set; }
// Item1 specifies up (1) or down (-1), Item2 specifies right (1) or left (-1)
public Ray(Point origin, Point alsoGoesThrough)
{
Origin = origin;
AlsoGoesThrough = alsoGoesThrough;
int directionUp;
if (origin.Y == alsoGoesThrough.Y)
{
directionUp = 0;
}
else if (origin.Y > alsoGoesThrough.Y)
{
directionUp = -1;
}
else // origin.Y < alsoGoesThrough.Y
{
directionUp = 1;
}
int directionRight;
if (origin.X == alsoGoesThrough.X)
{
directionRight = 0;
}
else if (origin.X > alsoGoesThrough.X)
{
directionRight = -1;
}
else // origin.X < alsoGoesThrough.X
{
directionRight = 1;
}
Direction = new Tuple<int, int>(directionUp, directionRight);
}
}
public class Line
{
public double Slope { get; private set; }
public double YOfIntersectionWithYAxis { get; private set; }
public Line(Point goesThrough1, Point goesThrough2)
{
Slope = (goesThrough1.Y - goesThrough2.Y) / (goesThrough1.X - goesThrough2.X);
YOfIntersectionWithYAxis = goesThrough1.Y - Slope * goesThrough1.X;
}
public Point IntersectionWithOtherLine(Line other)
{
if (Slope == other.Slope) return null;
double intersectionX = (other.YOfIntersectionWithYAxis - YOfIntersectionWithYAxis) / (Slope - other.Slope);
double intersectionY = Slope * intersectionX + YOfIntersectionWithYAxis;
return new Point(intersectionX, intersectionY);
}
}
仅适用于JSOP :-)
For JSOP only :-)
IDENTIFICATION DIVISION.
PROGRAM-ID. CPCC4-POINT-IN-POLYGON.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 T1 PIC S9(6) VALUE ZERO.
01 T2 PIC S9(6) VALUE ZERO.
01 T3 PIC S9(6) VALUE ZERO.
01 T4 PIC S9(6) VALUE ZERO.
LOCAL-STORAGE SECTION.
01 POLYGON.
02 POINT OCCURS 6 TIMES.
03 X PIC 9(3) VALUE ZERO.
03 Y PIC 9(3) VALUE ZERO.
01 CHECK-POINT.
02 CP-X PIC 9(3) VALUE ZERO.
02 CP-Y PIC 9(3) VALUE ZERO.
01 CNT PIC 9(1) VALUE 1.
01 WN PIC 9(3) VALUE ZERO.
01 SIDE PIC S9(3) VALUE ZERO.
PROCEDURE DIVISION.
PERFORM READ-CHECK-POINT.
PERFORM INITIALIZE-POLYGON.
PERFORM COMPUTE-WINDING-NUMBER VARYING CNT FROM 1 BY 1 UNTIL CNT = 6.
IF WN = 0 THEN
DISPLAY 'THE POINT (' CP-X ',' CP-Y ') IS OUTSIDE THE POLYGON.',
ELSE
DISPLAY 'THE POINT (' CP-X ',' CP-Y ') IS INSIDE THE POLYGON.',
END-IF.
STOP RUN.
COMPUTE-WINDING-NUMBER.
PERFORM CHECK-SIDE.
IF Y(CNT) <= CP-Y THEN
IF Y(CNT + 1) > CP-Y AND SIDE > 0 THEN
ADD 1 TO WN
END-IF
ELSE
IF Y(CNT + 1) <= CP-Y AND SIDE < 0 THEN
SUBTRACT 1 FROM WN
END-IF
END-IF.
CHECK-SIDE.
SUBTRACT X(CNT) FROM X(CNT + 1) GIVING T1.
SUBTRACT Y(CNT) FROM CP-Y GIVING T2.
MULTIPLY T1 BY T2 GIVING T1.
SUBTRACT Y(CNT) FROM Y(CNT + 1) GIVING T3.
SUBTRACT X(CNT) FROM CP-X GIVING T4.
MULTIPLY T3 BY T4 GIVING T3.
SUBTRACT T3 FROM T1 GIVING SIDE.
READ-CHECK-POINT.
DISPLAY 'ENTER X COORDINATE:'.
ACCEPT CP-X.
DISPLAY 'ENTER Y COORDINATE:'.
ACCEPT CP-Y.
INITIALIZE-POLYGON.
MOVE 2 TO X(1).
MOVE 0 TO Y(1).
MOVE 4 TO X(2).
MOVE 1 TO Y(2).
MOVE 4 TO X(3).
MOVE 4 TO Y(3).
MOVE 2 TO X(4).
MOVE 5 TO Y(4).
MOVE 1 TO X(5).
MOVE 2 TO Y(5).
MOVE 2 TO X(6).
MOVE 0 TO Y(6).
有点数学......
它是绕组和交叉方法的结合......从交叉方法中我借用了射线的概念，而从绕线方法中提出了方向的想法...
1.使用假想的水平线，包含我们寻找的点作为光线
2.仅检查该线穿过的边缘
3.使用边缘作为向量，看看我们是CW还是CCW
4.检查向量点（边缘）的哪一侧 - 那边是相对于方向...
5.增量（左侧）或减少（右侧）迂回编号
6.零在外面
And a bit for the math...
It is a combination of the winding and the crossing method... From the crossing method I borrowed the idea of the ray, while from the winding method the idea of direction...
1. Uses an imaginary horizontal line that contains the point we looking for as ray
2. Checks only edges crossed by that line
3. Uses edges as vectors to see if we go CW or CCW
4. Checks on which side the point of the vector (edge) - and that side is relative to the direction...
5. Increments (left side) or decrements (right side) the winding number
6. Zero is outside
这篇关于编码挑战：是多边形中的一个点？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
