Incorrect unify result #55

[nine-fox]

Currently, I am verifying the test cases of the Flatten.js. Found that the following test may be incorrect. Would you please confirm? Thanks.

"Can perform unify. Infinite loop for boolean union over (valid) polygons. Issue #55 case 0"

It contains poly1 and poly2, while poly2 contains the point: "pe":{"x":879050000,"y":269690000,"name":"point"}

Look, we have 879050000 in x axis as min value. However, after unifying, the result faces boudingbox is as follows, which is 880050000 bigger than 879050000:

			"key": {
				"xmin": 880050000,
				"ymin": 213980000,
				"xmax": 886111716.7381974,
				"ymax": 273020000
			},

As a reference, the following is the res.faces result:

{"index":{"root":{"left":{"left":null,"right":null,"parent":null,"color":1,"item":{}},"right":{"left":null,"right":null,"parent":null,"color":1,"item":{}},"parent":null,"color":1,"item":{"key":{"xmin":880050000,"ymin":213980000,"xmax":886111716.7381974,"ymax":273020000},"value":[{"ps":{"x":885125130.4347826,"y":217050000,"name":"point"},"pe":{"x":885457739.1304348,"y":220050000,"name":"point"},"name":"segment"},{"ps":{"x":885457739.1304348,"y":220050000,"name":"point"},"pe":{"x":885880000,"y":220050000,"name":"point"},"name":"segment"},{"ps":{"x":885880000,"y":220050000,"name":"point"},"pe":{"x":886111716.7381974,"y":221440300.42918456,"name":"point"},"name":"segment"},{"ps":{"x":886111716.7381974,"y":221440300.42918456,"name":"point"},"pe":{"x":885629798.7601395,"y":221601910.38557255,"name":"point"},"name":"segment"},{"ps":{"x":885629798.7601395,"y":221601910.38557255,"name":"point"},"pe":{"x":885950000,"y":224490000,"name":"point"},"name":"segment"},{"ps":{"x":885950000,"y":224490000,"name":"point"},"pe":{"x":885572474.0424377,"y":228923822.22616062,"name":"point"},"name":"segment"},{"ps":{"x":885572474.0424377,"y":228923822.22616062,"name":"point"},"pe":{"x":883252727.7414774,"y":256167889.82527742,"name":"point"},"name":"segment"},{"ps":{"x":883252727.7414774,"y":256167889.82527742,"name":"point"},"pe":{"x":882610351.261163,"y":263712226.99979052,"name":"point"},"name":"segment"},{"ps":{"x":882610351.261163,"y":263712226.99979052,"name":"point"},"pe":{"x":882952897.4299022,"y":268490915.6310136,"name":"point"},"name":"segment"},{"ps":{"x":882952897.4299022,"y":268490915.6310136,"name":"point"},"pe":{"x":882950001.1519145,"y":268609952.65631473,"name":"point"},"name":"segment"},{"ps":{"x":882950001.1519145,"y":268609952.65631473,"name":"point"},"pe":{"x":882038442.3014525,"y":270428964.23629075,"name":"point"},"name":"segment"},{"ps":{"x":882038442.3014525,"y":270428964.23629075,"name":"point"},"pe":{"x":882038439.5867643,"y":270428996.1187189,"name":"point"},"name":"segment"},{"ps":{"x":882038439.5867643,"y":270428996.11871856,"name":"point"},"pe":{"x":881920000,"y":271820000,"name":"point"},"name":"segment"},{"ps":{"x":881920000,"y":271820000,"name":"point"},"pe":{"x":881380000,"y":272020000,"name":"point"},"name":"segment"},{"ps":{"x":881380000,"y":272020000,"name":"point"},"pe":{"x":881287492.4471301,"y":271927492.44712996,"name":"point"},"name":"segment"},{"ps":{"x":881287492.44713,"y":271927492.44712996,"name":"point"},"pe":{"x":881287488.7218044,"y":271927488.7218046,"name":"point"},"name":"segment"},{"ps":{"x":881287488.7218044,"y":271927488.7218046,"name":"point"},"pe":{"x":880740000,"y":273020000,"name":"point"},"name":"segment"},{"ps":{"x":880740000,"y":273020000,"name":"point"},"pe":{"x":880050000,"y":272860000,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":272860000,"name":"point"},"pe":{"x":880050000,"y":270690000,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":270690000,"name":"point"},"pe":{"x":880050000,"y":242973796.52605474,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":242973796.52605474,"name":"point"},"pe":{"x":880050000,"y":242973796.5260537,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":242973796.5260537,"name":"point"},"pe":{"x":880050000,"y":224390000,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":224390000,"name":"point"},"pe":{"x":881870000,"y":220760000,"name":"point"},"name":"segment"},{"ps":{"x":881870000,"y":220760000,"name":"point"},"pe":{"x":880050000,"y":220153333.33333328,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":220153333.33333328,"name":"point"},"pe":{"x":880050000,"y":219200000,"name":"point"},"name":"segment"},{"ps":{"x":880050000,"y":219200000,"name":"point"},"pe":{"x":880610000,"y":218970000,"name":"point"},"name":"segment"},{"ps":{"x":880610000,"y":218970000,"name":"point"},"pe":{"x":881690000,"y":220050000,"name":"point"},"name":"segment"},{"ps":{"x":881690000,"y":220050000,"name":"point"},"pe":{"x":882461456.5387628,"y":220050000,"name":"point"},"name":"segment"},{"ps":{"x":882461456.5387628,"y":220050000,"name":"point"},"pe":{"x":882777039.9373531,"y":217050000,"name":"point"},"name":"segment"},{"ps":{"x":882777039.9373531,"y":217050000,"name":"point"},"pe":{"x":883080000,"y":214170000,"name":"point"},"name":"segment"},{"ps":{"x":883080000,"y":214170000,"name":"point"},"pe":{"x":883620000,"y":213980000,"name":"point"},"name":"segment"},{"ps":{"x":883620000,"y":213980000,"name":"point"},"pe":{"x":884930000,"y":215290000,"name":"point"},"name":"segment"},{"ps":{"x":884930000,"y":215290000,"name":"point"},"pe":{"x":885125130.4347826,"y":217050000,"name":"point"},"name":"segment"}]},"max":{"xmin":880050000,"ymin":213980000,"xmax":886111716.7381974,"ymax":273020000}},"nil_node":{"left":null,"right":null,"parent":null,"color":1,"item":{}}}}

You can search this output and there is no 879050000 value.

[alexbol99]

You are right, the result of unify(poly2, poly1) is incorrect.
Interesting, that the result of unify(poly1, poly2) is ok
I need to investigate this.

[nine-fox]

Thanks for your investigation. I believe this is the floating point issue, related to the issue #124

Because it is resolved after I replaced raw js numbers with decimal.js.

[alexbol99]

You may open a PR if you want

[dragonman225]

I'm working on refining an auto-layout algorithm for boxes, and I came across a similar hiccup: occasionally, the unify function would generate an incorrect polygon for specific combinations of boxes.

For example:

• Gray-filled rectangles are boxes.
• Orange edges represent the bounding boxes of those boxes + gaps around them.
• Blue edges represent the polygon calculated by unify. Gaps are included when calculating the polygon.

Here are the dimensions of those boxes and the code generating the image: https://codesandbox.io/s/flatten-js-polygon-issue-23q8dh

[alexbol99]

Hi, @dragonman225 ,

This is again floating point issues.
I can suggest a workaround to restrict precision of the vertices by 12 digits:

new Polygon(
    new Box(
        Number((obj.pos.x - gap).toPrecision(12)),
        Number((obj.pos.y - gap).toPrecision(12)),
        Number((obj.pos.x + obj.size.w + gap).toPrecision(12)),
        Number((obj.pos.y + obj.size.h + gap).toPrecision(12))
    )
)

Then the result is correct:

Please check if this works in other cases

[dragonman225]

Hi @alexbol99,

Thanks for your suggestion! It makes a lot of sense and is working flawlessly at the moment.