w8r / martinez

Martinez-Rueda polygon clipping algorithm, does boolean operation on polygons (multipolygons, polygons with holes etc): intersection, union, difference, xor
https://w8r.github.io/martinez/demo/#geo
MIT License
701 stars 77 forks source link

Self intersecting edges in union #103

Open lelongg opened 5 years ago

lelongg commented 5 years ago

The union of two polygons can produce a polygon with self intersecting edges.

Below are an example of the issue and the code to reproduce this example.

Example

gj1 gj2 union

Code to reproduce example

const martinez = require('martinez-polygon-clipping');
const geojson2svg = require('geojson-to-svg');
const svgToMiniDataURI = require('mini-svg-data-uri');

const gj1 = {
  type: 'Feature',
  properties: {},
  geometry: { coordinates: [[[314.40495804718677, 245.22995740474045], [355.3084164255646, 274.62805627384455], [388.1787335887434, 320.33832954550485], [388.9124587537205, 320.65353992291637], [400.0, 335.9912795978437], [400.0, 246.12148820908317], [374.63976989251296, 232.18897652259886], [333.1714557280062, 200.59530404401397], [339.9682813108619, 202.86632587352096], [352.20189036987824, 165.65101936712378], [352.1226856869796, 165.67910842756115], [351.11664245242355, 143.32479268320685], [358.21104193260544, 135.3909067611561], [400.0, 102.7539460309187], [400.0, 0.0], [371.2197402336615, 2.842170943040401e-14], [348.64013551352855, 53.435028392624496], [344.5955075658226, 53.806406865151274], [335.14340456541504, 77.83582779964986], [310.6585569221463, 80.7440852782285], [301.68587048275344, 132.45449117396356], [300.5747979723983, 118.76815396163059], [297.3467313288405, 145.14834613196768], [272.34144089775623, 145.3051023345713], [197.10335384609192, 129.83210391441233], [157.0231603224197, 105.78147219020022], [120.44771878596228, 109.55893998720018], [168.9029877884493, 131.3790233720232], [144.78499570302176, 137.09599949165835], [89.90107595046035, 118.5515206604366], [97.05625149415084, 132.96319782327134], [18.90341962399799, 111.35909458586124], [18.943831873143722, 116.08488152321168], [120.9957537807505, 142.53498680412483], [222.9869248986131, 178.3491004724274], [244.39124334340312, 180.9975096828225], [254.38144111881923, 272.10286475523776], [314.40495804718677, 245.22995740474045]]], type: 'Polygon' },
};
const gj2 = {
  type: 'Feature',
  properties: {},
  geometry: { coordinates: [[[244.55571899625278, 185.9229643180382], [248.5849016468879, 306.58250278991926], [257.9987920828058, 305.09120506683007], [254.38144111881923, 272.10286475523776], [314.40495804718677, 245.22995740474045], [355.3084164255646, 274.62805627384455], [292.2355740236037, 186.91740693932564], [343.1405834727814, 193.21600954273006], [352.1960877194012, 165.668671346602], [352.1226856869796, 165.67910842756115], [351.11664245242355, 143.32479268320685], [358.21104193260544, 135.3909067611561], [400.0, 118.64643487917338], [400.0, 75.65538218016279], [297.3467313288405, 145.14834613196768], [272.34144089775623, 145.3051023345713], [197.10335384609192, 129.83210391441233], [173.31982573883488, 104.09837210383137], [133.6345063121441, 108.1970243647632], [168.9029877884493, 131.3790233720232], [144.78499570302176, 137.09599949165835], [86.312921823555, 111.32439973633113], [97.05625149415084, 132.96319782327134], [18.870187035423584, 107.47289333997468], [18.89787710655719, 110.71095554199546], [120.9957537807505, 142.53498680412483], [244.55571899625278, 185.9229643180382]]], type: 'Polygon' },
};

const union = {
  type: 'Feature',
  properties: {},
  geometry: {
    type: 'Polygon',
    coordinates: martinez.union(gj1.geometry.coordinates, gj2.geometry.coordinates),
  },
};

console.log(geojson2svg()
  .data(gj1)
  .render());

console.log(geojson2svg()
  .data(gj2)
  .render());

console.log(geojson2svg()
  .data(union)
  .render());
bluenote10 commented 4 years ago

Another check against polybooljs:

Input: bug_103_input

Output: bug_103_output

Also seems like it avoids the issue.

bluenote10 commented 4 years ago

This issue seems fine already on master:

image

Was maybe fixed by #111 already? I can turn it into a test case anyway.

w8r commented 4 years ago

I can turn it into a test case anyway.

Pleas do, thank you so much for the help

bluenote10 commented 4 years ago

Added as a test case in #117

rowanwins commented 2 years ago

This still seems to have some issues with difference operations