martinez: Crash: JavaScript heap out of memory

Using Node-8.11.1 (or 9.11.1, though the stack trace is from 8), martinez crashes the runtime with this pair of geometries: https://gist.github.com/mojodna/6e4ed77135ffdb629577574298307dd6

Standalone reproduction:

const martinez = require("martinez-polygon-clipping");

const a = [[[117.659922722,3.255275783000087],[117.64844811300017,3.246039130000042],[117.63795006600017,3.248724677000112],[117.63331139400017,3.268215236000103],[117.62484785200004,3.283270575000117],[117.57178795700011,3.313137111000017],[117.55640709700006,3.331854559000078],[117.54363040500002,3.354803778000147],[117.53467858200011,3.379380601000079],[117.53126061300006,3.403143622000158],[117.54151451900012,3.428452867000118],[117.56666100400011,3.438421942000105],[117.62525475400005,3.437689520000077],[117.64047285199999,3.436509507000054],[117.65699303500017,3.433539130000128],[117.67156009200019,3.426988023000064],[117.68165123800006,3.415513414000102],[117.68392988400015,3.399603583000086],[117.68197675900004,3.37750885600002],[117.67725670700011,3.356431382000082],[117.66537519600016,3.329291083000072],[117.66732832099999,3.271551825000117],[117.659922722,3.255275783000087]]];
const b = [[[117.6315403,3.2711246],[117.631605,3.2711063],[117.6315993,3.2710864],[117.6321104,3.2709415],[117.6320843,3.2708497],[117.6316732,3.2709663],[117.631666,3.2709411],[117.6315646,3.2709699],[117.6315529,3.2709289],[117.6314897,3.2709469],[117.6315403,3.2711246]]];

martinez.intersection(a, b);

Stack trace:

<--- Last few GCs --->

[98975:0x103001800]     6728 ms: Mark-sweep 578.0 (585.6) -> 578.0 (585.6) MB, 138.1 / 0.0 ms  allocation failure GC in old space requested
[98975:0x103001800]     6867 ms: Mark-sweep 578.0 (585.6) -> 577.9 (582.6) MB, 139.0 / 0.0 ms  last resort GC in old space requested
[98975:0x103001800]     7007 ms: Mark-sweep 577.9 (582.6) -> 577.9 (582.6) MB, 140.2 / 0.0 ms  last resort GC in old space requested


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x34e1f74a57c1 <JSObject>
    1: connectEdges(aka connectEdges) [/Users/seth/src/americanredcross/osm-stats-workers/node_modules/martinez-polygon-clipping/dist/martinez.js:~1091] [pc=0x3b6e887061d1](this=0x34e11aa022d1 <undefined>,sortedEvents=0x34e1c508a031 <JSArray[39]>,operation=0)
    2: boolean(aka boolean) [/Users/seth/src/americanredcross/osm-stats-workers/node_modules/martinez-polygon-clipping/dist/martinez.js:13...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
 1: node::Abort() [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 4: v8::internal::Factory::NewUninitializedFixedArray(int) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 5: v8::internal::(anonymous namespace)::ElementsAccessorBase<v8::internal::(anonymous namespace)::FastPackedObjectElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)2> >::GrowCapacity(v8::internal::Handle<v8::internal::JSObject>, unsigned int) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 6: v8::internal::Runtime_GrowArrayElements(int, v8::internal::Object**, v8::internal::Isolate*) [/Users/seth/.nvm/versions/node/v8.11.1/bin/node]
 7: 0x3b6e885842fd
 8: 0x3b6e887061d1
 9: 0x3b6e8863d196
10: 0x3b6e8863d196
11: 0x3b6e8863d196
12: 0x3b6e8863d196
13: 0x3b6e8863d196
14: 0x3b6e8863d196
15: 0x3b6e8863d196
Abort trap: 6

About this issue

  • Original URL
  • State: closed
  • Created 6 years ago
  • Comments: 17 (5 by maintainers)

Commits related to this issue

Most upvoted comments

For the record, the error was in a COMPLETELY different place ))))

+3
w8r on May 27, 2018

I will try working on it this week, so maybe next week.

+3
w8r on May 23, 2018

Thank you @w8r.

For now, I’ve hacked a workaround so that it doesn’t crash (crucial for my app). Basically inserting a counter and exiting the loop if it executes too long. I understand that it will probably give a wrong intersection result, but wrong is better than app crash for me 😃

In my particular case we’re using @turf/intersect so I’m patching the code using overwrite and injecting the overwritten dependency into turf with rewire.

Here’s a snippet, just in case anyone else has similar situation to mine.

+2
v1adko on May 23, 2018

Here’s a simplified repro:

const martinez = require("./index");

const a = [
  [
    [117.659922722, 3.255275783000087],
    [117.63331139400017, 3.268215236000103],
    [117.62484785200004, 3.283270575000117],
    [117.659922722, 3.255275783000087]
  ]
];

const b = [
  [
    [117.6315403, 3.2711246],
    [117.631605, 3.2711063],
    [117.6315993, 3.2710864],
    [117.6321104, 3.2709415],
    [117.6320843, 3.2708497],
    [117.6314897, 3.2709469],
    [117.6315403, 3.2711246]
  ]
];

martinez.intersection(a, b);

This while loop is never terminating: https://github.com/w8r/martinez/blob/master/src/connect_edges.js#L121-L137

+2
mojodna on Apr 20, 2018

It also crashes Chrome when these geometries are used in the CodePen.

The smaller feature is https://www.openstreetmap.org/way/576508727, the larger feature is an island in Indonesia from Natural Earth’s 110m admin 0 boundaries layer.

+2
mojodna on Apr 6, 2018

I’ve done a bit more digging (and read through the paper), so perhaps I can offer something a bit more helpful than “the while loop doesn’t terminate” (which isn’t actually useful, since the cause of that is that the data passed in is incomplete).

sortedEvents after subdivision looks like this:

image

It should look like:

image

The underlying problem is that the top edge (highlighted in red) isn’t getting subdivided:

image

The set of edges in sweepLine during the 17th (final) iteration in subdivide (it’s a right event) doesn’t contain what it should.

The eventQueue looks like this after being filled (and prior to being subdivided):

image

Each segment is doubled, with end vertices reversed (✔️).

Here is the tree at that point in red (with the queue in grey):

image

GeoJSON for the tree was generated using

{
  type: 'FeatureCollection',
  features: sweepLine.keys().map(x => ({
  type: "Feature",
  properties: {},
  geometry: {
    type: 'LineString',
    coordinates: [x.point, x.otherEvent.point]
  }
}

Here are the segments labeled with the order in which they’re processed:

image

Also, reading the algorithm in the paper, this

https://github.com/w8r/martinez/blob/8e8901894a3a229aa9ad0f1ab9cb9ec3d22634a2/src/subdivide_segments.js#L23

Should probably be done at the end of each loop iteration to provide only the edges that are part of the intersection to the edge connector, e.g.:

if (event.inResult) {
  sortedEvents.push(event);
}
+1
mojodna on May 5, 2018
Read more comments on GitHub
← martinez: A case where intersection is incorrect
firebase-action: New v13.0.1 docker image is unavailable →