求一高效算法，高分送上

yhy0611 2008-09-12 02:55:21

先看个图

如上图所示己知有N个多边形（都是没有规律，不规则的）和每个多边形各个点的X和Y，现在给定一个P，判断P是否在某一多边型的区域内。

本人数学为0，跪求高人附上代码，多谢！

...全文

1091 34 打赏收藏转发到动态举报

写回复

用AI写文章

34 条回复

切换为时间正序

请发表友善的回复…

发表回复

liujiassd 2011-04-11

打赏
举报

支持下。

lingdu0001 2011-02-12

打赏
举报

貌似不错看看各位牛人的回答

qyci 2010-08-26

打赏
举报

回复17楼的，
你给出的：范围内数据两组 f1=124.9104 f2=46.61841,f1=124.9107 f2=46.62143
我用两种方法测试的结果都是范围外。。。。。

public bool IsPointInRegion()
{
using(GraphicsPath myGraphicsPath = new GraphicsPath())
{
using (Region myRegion = new Region())
{
using (Pen pen = new Pen(Color.Beige))
{
myGraphicsPath.Reset();

string str = "124.89874,46.6286V124.9001,46.62973V124.90287,46.62741V124.90409,46.62783V124.90334,46.63028V124.9055,46.63044V124.90629,46.62796V124.90775,46.62792V124.90868,46.63011V124.91089,46.62931V124.90943,46.62751V124.91182,46.62706V124.91257,46.62905V124.91506,46.62812V124.91281,46.6268V124.91459,46.62619V124.91557,46.6277V124.91708,46.62586V124.91468,46.6257V124.91497,46.62477V124.91703,46.62384V124.91497,46.62261V124.91356,46.62387V124.91309,46.62194V124.91506,46.62232V124.91511,46.62081V124.91286,46.62097V124.91271,46.62029V124.91482,46.61975V124.91398,46.61833V124.91187,46.61942V124.91117,46.61872V124.91075,46.61701V124.90746,46.61714V124.90976,46.61878V124.90639,46.61868V124.90559,46.61717V124.90142,46.61772V124.90498,46.61888V124.90212,46.61946V124.90085,46.61807V124.89921,46.61952V124.90151,46.62013V124.90109,46.62152V124.89813,46.62013V124.8979,46.62223V124.90067,46.622V124.90001,46.62351V124.89663,46.62281V124.89663,46.62441V124.89917,46.62445V124.89903,46.62545V124.89588,46.62567V124.89584,46.62702V124.89903,46.62638V124.89982,46.62725";
string[] s1 = str.Split('V');

PointF[] ptList = new PointF[s1.Length];
for (int i = 0; i < s1.Length; i++)
{
string[] s2 = s1[i].Split(',');
PointF pf = new PointF(float.Parse(s2[0]), float.Parse(s2[1]));
ptList[i] = pf;
}
// be in ?
PointF ptTest = new PointF(124.9104f,46.61841f);
//PointF ptTest = new PointF(124.9107f, 46.62143f);

// be out
//PointF ptTest = new PointF(124.918f, 46.62406f);
//PointF ptTest = new PointF(124.91518f, 46.62474f);

//Point[] ptList = new Point[4];
//ptList[0] = new Point(0, 0);
//ptList[1] = new Point(0, 100);
//ptList[2] = new Point(100, 100);
//ptList[3] = new Point(100, 0);

//Point ptTest = new Point(1, 90);

myGraphicsPath.AddPolygon(ptList);
bool bOnEage = myGraphicsPath.IsOutlineVisible(ptTest, pen);
if (bOnEage)
{
return false;
}

//myRegion.MakeEmpty();
//myRegion.Union(myGraphicsPath);
//bool bInRgn = myRegion.IsVisible(ptTest);

//bool bInRgn = myGraphicsPath.IsVisible(ptTest); // Check with .Framework

bool bInRgn = PointInPolygon.Contains(ptList, ptTest); // Check with Angle

return bInRgn;
}
}
}

qyci 2010-08-25

打赏
举报

忘了解释一下代码了。

如果点在封闭曲线的边线上的话，bOnEage为true，我这里因为需要认为它不在区域的内部，所以，返回false.

对于点是否在封闭曲线形成的区域的内部，我看大家都是使用Region的IsVisible来判断的，不明白为何不直接使用 GraphicsPath的IsVisible来判断呢？

大家可以用代码测试一下看看

qyci 2010-08-25

打赏
举报

using System.Drawing;
using System.Drawing.Drawing2D;
public bool IsPointInRegion()
{
using(GraphicsPath myGraphicsPath = new GraphicsPath())
{
using (Region myRegion = new Region())
{
using (Pen pen = new Pen(Color.Beige))
{
myGraphicsPath.Reset();

Point[] ptList = new Point[4];
ptList[0] = new Point(0, 0);
ptList[1] = new Point(0, 100);
ptList[2] = new Point(100, 100);
ptList[3] = new Point(100, 0);

Point ptTest = new Point(1, 90);

myGraphicsPath.AddPolygon(ptList);
bool bOnEage = myGraphicsPath.IsOutlineVisible(ptTest, pen);
if (bOnEage)
{
return false;
}

//myRegion.MakeEmpty();
//myRegion.Union(myGraphicsPath);
//bool bInRgn = myRegion.IsVisible(ptTest);
bool bInRgn = myGraphicsPath.IsVisible(ptTest);
return bInRgn;
}
}
}

lnixonliunian 2010-04-30

打赏
举报

引用13楼的了，很不错！看来我要多向你们请教了！

chenzt1015 2010-04-24

打赏
举报

怎么看不到算法啊

liang4571231 2008-09-13

打赏
举报

呵呵，我顶你，老兄
[Quote=引用 2 楼 wdgphc 的回复:]
c# 中早就给出了方法.
大致伪代码如下

private bool PointInBox()
{
for (int i = 0; i < 多边形个数; i++)
{
Point[] p = 多边形的各个点
Point p1 = 要计算的那个点

System.Drawing.Drawing2D.GraphicsPath gp = new System.Drawing.Drawing2D.GraphicsPath();
Region r = new Region(); …
[/Quote]

zoroz 2008-09-13

打赏
举报

帮顶

yhy0611 2008-09-13

打赏
举报

感谢大家，磕头了！

蓝色木 2008-09-13

打赏
举报

13楼正解

消失的尘芥 2008-09-13

打赏
举报

这个问题很难哦，帮顶

yhy0611 2008-09-13

打赏
举报

[Quote=引用 20 楼 wdgphc 的回复:]
这是由于画图中一条斜线理论计算画出来的和实际按整数象素点描绘出来的不一样.
[/Quote]

有什么办法可以解决吗？

hustcyb 2008-09-12

打赏
举报

我的算法是求平面点集凸包的算法，对凸多边形没问题，对凹多边形可能会有点问题，你可能要将凹多边形分解成多个凸多边形来求解。

wdgphc 2008-09-12

打赏
举报

这是由于画图中一条斜线理论计算画出来的和实际按整数象素点描绘出来的不一样.

yhy0611 2008-09-12

打赏
举报

老蚂蚱阿杰很是感谢你
可是C++我不会呀

mawering 2008-09-12

打赏
举报

学习一下!帮顶!

yhy0611 2008-09-12

打赏
举报

我试了一下，复杂一点的多边形使用Region.IsVisible (Point) 方法结果就不准了，而使用hustcyb 的算法没有问题

下面是测试数据，大家如果有兴趣可以试一下









string str = "124.89874,46.6286V124.9001,46.62973V124.90287,46.62741V124.90409,46.62783V124.90334,46.63028V124.9055,46.63044V124.90629,46.62796V124.90775,46.62792V124.90868,46.63011V124.91089,46.62931V124.90943,46.62751V124.91182,46.62706V124.91257,46.62905V124.91506,46.62812V124.91281,46.6268V124.91459,46.62619V124.91557,46.6277V124.91708,46.62586V124.91468,46.6257V124.91497,46.62477V124.91703,46.62384V124.91497,46.62261V124.91356,46.62387V124.91309,46.62194V124.91506,46.62232V124.91511,46.62081V124.91286,46.62097V124.91271,46.62029V124.91482,46.61975V124.91398,46.61833V124.91187,46.61942V124.91117,46.61872V124.91075,46.61701V124.90746,46.61714V124.90976,46.61878V124.90639,46.61868V124.90559,46.61717V124.90142,46.61772V124.90498,46.61888V124.90212,46.61946V124.90085,46.61807V124.89921,46.61952V124.90151,46.62013V124.90109,46.62152V124.89813,46.62013V124.8979,46.62223V124.90067,46.622V124.90001,46.62351V124.89663,46.62281V124.89663,46.62441V124.89917,46.62445V124.89903,46.62545V124.89588,46.62567V124.89584,46.62702V124.89903,46.62638V124.89982,46.62725";

            string[] s1 = str.Split('V');



            PointF[] ps = new PointF[s1.Length];

            for (int i = 0; i < s1.Length; i++)

            {

                string[] s2 = s1[i].Split(',');

                PointF pf = new PointF(float.Parse(s2[0]), float.Parse(s2[1]));

                ps[i] = pf;

            }







            System.Drawing.Drawing2D.GraphicsPath gp = new System.Drawing.Drawing2D.GraphicsPath();

            

            Region r = new Region();



            gp.Reset();

            gp.AddPolygon(ps);

            r.MakeEmpty();

            r.Union(gp);



            float f1=0;   

            float f2=0;

            

            if (r.IsVisible(new PointF(f1,f2)))

            {

                MessageBox.Show("在范围内");

            }

            else

            {

                MessageBox.Show("不在范围内");

            }



string str = "124.89874,46.6286V124.9001,46.62973V124.90287,46.62741V124.90409,46.62783V124.90334,46.63028V124.9055,46.63044V124.90629,46.62796V124.90775,46.62792V124.90868,46.63011V124.91089,46.62931V124.90943,46.62751V124.91182,46.62706V124.91257,46.62905V124.91506,46.62812V124.91281,46.6268V124.91459,46.62619V124.91557,46.6277V124.91708,46.62586V124.91468,46.6257V124.91497,46.62477V124.91703,46.62384V124.91497,46.62261V124.91356,46.62387V124.91309,46.62194V124.91506,46.62232V124.91511,46.62081V124.91286,46.62097V124.91271,46.62029V124.91482,46.61975V124.91398,46.61833V124.91187,46.61942V124.91117,46.61872V124.91075,46.61701V124.90746,46.61714V124.90976,46.61878V124.90639,46.61868V124.90559,46.61717V124.90142,46.61772V124.90498,46.61888V124.90212,46.61946V124.90085,46.61807V124.89921,46.61952V124.90151,46.62013V124.90109,46.62152V124.89813,46.62013V124.8979,46.62223V124.90067,46.622V124.90001,46.62351V124.89663,46.62281V124.89663,46.62441V124.89917,46.62445V124.89903,46.62545V124.89588,46.62567V124.89584,46.62702V124.89903,46.62638V124.89982,46.62725";

            string[] s1 = str.Split('V');



            PointF[] ps = new PointF[s1.Length];

            for (int i = 0; i < s1.Length; i++)

            {

                string[] s2 = s1[i].Split(',');

                PointF pf = new PointF(float.Parse(s2[0]), float.Parse(s2[1]));

                ps[i] = pf;

            }



            float f1=0;   

            float f2=0;



            if (this.Contains(ps, new PointF(f1,f2)))

            {

                MessageBox.Show("在范围内");

            }

            else

            {

                MessageBox.Show("不在范围内");

            }