Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

VG generate wrongly due to polygon_crossing function not accurate #45

Open
hansoong opened this issue Dec 6, 2018 · 1 comment
Open

Comments

@hansoong
Copy link

hansoong commented Dec 6, 2018

  below is a convex polygon, each point should only have 2 visible points, but point_3 got 3.
  polygon_crossing function need review, as it return false when checking mid point (208.5, 227)

    self.point_1 = Point(298, 163.0)
    self.point_2 = Point(263, 168.0)
    self.point_3 = Point(199, 194.0)
    self.point_4 = Point(192, 227.0)
    self.point_5 = Point(218, 260.0)
    
    g = vg.VisGraph()
    g.build([[self.point_1, self.point_2, self.point_3, self.point_4, self.point_5]])
@hansoong
Copy link
Author

hansoong commented Dec 7, 2018

https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon

i dont know how good is this, but seems working..
public bool IsPointInPolygon( Point p, Point[] polygon )
{
double minX = polygon[ 0 ].X;
double maxX = polygon[ 0 ].X;
double minY = polygon[ 0 ].Y;
double maxY = polygon[ 0 ].Y;
for ( int i = 1 ; i < polygon.Length ; i++ )
{
Point q = polygon[ i ];
minX = Math.Min( q.X, minX );
maxX = Math.Max( q.X, maxX );
minY = Math.Min( q.Y, minY );
maxY = Math.Max( q.Y, maxY );
}

if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY )
{
    return false;
}

// http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
bool inside = false;
for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ )
{
    if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) &&
         p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X )
    {
        inside = !inside;
    }
}

return inside;

}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant