Polygon contains point

[huz]

I have thousands of large polygons, and hundreds of thousands points. I should find points outside of polygons. Most of them are in. I have used NetTopologySuite.Index.Strtree.STRtree for polygons to quicky find real candidates for test. But as polygons are large and have many points deafult Geometry.Contains(IGeometry) implementation is too slow for me. Is there any other method or helper in NTS to do this faster?

[Diego Guidi]

On Monday, November 3, 2014 9:06:54 AM UTC+1, huz wrote:

implementation is too slow for me. Is there any other method or helper in NTS to do this faster?

Tried with Geometries in Prepared namespace?

[huz]

Exactly what i needed. Thank you!

[huz]

I need some more help with memory leak with PreparedGemetry usage..

When i don't call Contains in my progam everything is fine, but when i remove "true ||" process starts to eat memory until OutOfMemoryException. Is there some lazy cashing troubling me or something else?

       private bool PoiInsideAnyObject(IGeomtry g, IList<IPreparedGeometry> poligons)

        {

            foreach (var pol in poligons)

                if (true || pol.Contains(g))

                    return true;

            return false;

        }

[Diego Guidi]

On Monday, November 3, 2014 11:52:47 AM UTC+1, huz wrote:

I need some more help with memory leak with PreparedGemetry usage..

can you share some code and data, so I can check? 

[huz]

Cant share data easy, it needs few layers of conversions and libraries to be used, and it also has NDA along.

I have tried to find real source in code, it came to section below. If i use Envelope it will check 35k cityCenters18

in few seconds and no much memory change after initial loading, but when i remove .Envelope from candidates[i].Envelope.Contains(cc) process starts to eat memory and eats 300MB before it is done, but it will finish all.

If i then also change candidates to 

var candidates = buildups.Select(x => PreparedGeometryFactory.Prepare((Polygon)x.Pts)).ToArray();
 

it will eat 800MB and die due to .NET 32 bit process limitations. If you have any advice what to try next please help. I will try to reconstruct this with some OSM data. This is very similar to checking if POIs are inside city poligons for some large country.

  

            var candidates = buildups.Select(x => (Polygon)x.Pts).ToArray();
            int nfnd = 0;
            int fnd = 0;
            foreach (var cc in cityCenters18)
            {
                bool found = false;
                for (int i = 0; i < candidates.Length; ++i)
                    if (candidates[i].Envelope.Contains(cc))
                    {
                        found = true;
                        fnd++;
                        break;
                    }
                if (!found)
                    ++nfnd;
                Console.Write(nfnd.ToString() + "\t" + fnd.ToString() + "\r");
            }

[Diego Guidi]

On Monday, November 3, 2014 3:29:15 PM UTC+1, huz wrote:

Cant share data easy, it needs few layers of conversions and libraries to be used, and it also has NDA along.

Ok I try to start from random data. 

[huz]

using

http://nettopologysuite.googlecode.com/svn/trunk 

revision 1258

[huz]

Also, thanks for the effort!

On Monday, November 3, 2014 3:45:58 PM UTC+1, Diego Guidi wrote:

[Diego Guidi]

you should use candidates[i]Contains(cc) instead of candidates[i].Envelope.Contains(cc)

[Diego Guidi]

please check attached code, I see a lot of ram used but can you confirm?

[Diego Guidi]

Using deferred geometries creation, I have no memory problems at all.

So, to me, problem is actually when you read data, not when you test data itself.

See attached code.

[huz]

I did, just tried to explain different memory usage with different Contains approaches. But it was not clear to understand, sorry. I will give you one more example in few minutes.

[FObermaier]

This approach is wrong, prepared polygon is a one against many approach, so you need to check one polygon for many points.
Also a prepared polygon is an expensive object, both in creation and storage, so I'd say you create it, use it for your tests and then drop it.
For a PoI inside any polygon test, build a union (CascadedPolygonUnion) of your input polygons, make a prepared geometry of it and then test your points.

On Monday, November 3, 2014 11:52:47 AM UTC+1, huz wrote:

[huz]

Please check memory measurements in update of your test. I get following result:

Test Name: test_with_1M_items

Test Outcome: Passed

Result StandardOutput: memory: '538747676', matched '78639' of '1000000': elapsed time: '00:00:10.2525051'

Just looping and checking if geometry contains object used 539MB. It is strange that .Contains() method uses memory and does not release it? If you have same result than we know what caused my problem,

I did't use deferred creation, nor did I before in my code, used .ToArray() to avoid this.

[huz]

OK, sorry, I am not experienced with NTS to know many alternate ways of thinking.

I will try with CascadedPolygonUnion approach and see how good it is.

Original approach seamed excellent because I used STRtree to quickly find candidates and then prepared polygons to test points. This thing with .Contains is strange because i would expect to all memory to be used when polygon is prepared, and if something is allocated in .Contains that is released when function finishes.

[FObermaier]

As I said, PreparedGeometry is for one against many, that is why utility objects (e.g. indices) are not dropped after usage. Only when the whole object goes out of scope.

You still should use PreparedGeometry for your "unioned" polygon.