ThinkGeo.com    |     Documentation    |     Premium Support

IsWithin very slow

#1

Hi,

I’m testing a very large number of points if they are within a circle. This process is taking 18029 s using the point.IsWithin(BaseShape shape) extension.

I decided to make my own Pythagoras method as follows which runs through the same number of points in 4 s. Any idea why the slowness? NB: I also tried to reverse the test using IsDisjointed with similar results.

    private static bool PointInCircle2(PointShape point, EllipseShape circle, double radius)
    {
        double dx = point.X - circle.Center.X;
        double dy = point.Y - circle.Center.Y;

        double side = dx * dx + dy * dy;

        if (side < radius * radius)
            return true;
        else
            return false;
    }

Thanks,
Damian

#2

Thanks Damian,
I think your method PointInCircle2 looks good. The only thing I think it may take some time is

“circle.Center”

This may look through all point of the EllipseShape and calculate the center point. You could pass the radius to your method directly. If not at least we could use
var center = circle.Center;
double dx = point.X - center.X;
double dy = point.Y - center.Y;

This could only calculate the center point once.

Thanks

Frank

#3

Hi Frank,

I think you misunderstand. The PointInCircle2 method is working very fast, but the IsWithin method is grossly taking a lot of time. I don’t know at what point this happened as it didn’t used to be that way.

I’ve attached a test project. Please let me know as I use IsWithin and IsDisjointed quite a lot.

PointInCircle.zip (20.1 KB)

Regards,
Damian

#4

Thanks Damian,
I got it. tp.IsWithin(el) will calculate base on the Geometry. If you use var x = el.GetWellKnownText(); you will find the circle actual stored as polygon. That is why it much slower than compare the distance between two points. We use the NetTopologySuite.Geometries to do the spatial calculation. You can find more detail here.
https://nettopologysuite.github.io/NetTopologySuite/api/NetTopologySuite.Geometries.Geometry.html#NetTopologySuite_Geometries_Geometry_Within_NetTopologySuite_Geometries_Geometry_

So the WithIn method is a generic to calculate within. But for circle you could have your own method to do this. You could either extent the class or create a new class to overwrite the method.

    public class MyPointShape : PointShape
    {
        public MyPointShape(double x, double y) : base(x, y)
        {
            
        }

        protected override bool IsWithinCore(BaseShape targetShape)
        {
            if (targetShape.GetType() == typeof(EllipseShape))
            {
                return PointInCircle2((EllipseShape)targetShape);
            }
            else
            {
                return base.IsWithinCore(targetShape);
            }
        }


        private bool PointInCircle2(EllipseShape circle)
        {
            double dx = this.X - circle.Center.X;
            double dy = this.Y - circle.Center.Y;
            double radius = circle.Width / 2;

            double side = dx * dx + dy * dy;

            if (side < radius * radius)
                return true;
            else
                return false;
        }
    }

Thanks

Frank

#5

Hi Frank,

Thanks for the override suggestion, but it’s probably way more hassle to change all my PointShape objects into MyPointShape objects just in case I try and use the IsWithin method on an Ellipse that is only of type Circle. I’ll have to see.

Are you aware of any other non-optimal tests the NetTopologySuite is doing?

Thanks,
Damian

#6

Thanks Damian,
I don’t see any other non-optimal tests on NetTopologySuite. There may another way to enhance this one. we could use
tp.GetDistanceTo(targetPoint)

Because we need check the point is in the circle. We could just calculate the distance between the target point and the center point. Basically it is the same theory as your PointInCircle2.

Thanks

Frank

#7

Hi Frank,

That’s an interesting idea. Will need to verify it though as GetDistanceTo has a square root term to it that may set it back. Worth a test though!

Regards,
Damian

#8

Thanks Damian,
Go ahead let us know if you have any question.

Thanks

Frank