dyn4j: Still getting hull errors

Unfortunately I’m still getting various errors after 1134b731412055bfa1f6e7e7e49d4f6d6874baf4. From what I saw, most of them have to do with colinear points on the hull. At this point I dunno if we can remove some of the algorithms altogether if they prove to be much trouble to implement correctly, or re-implement them from scratch.

Graham scan

Counter example for GrahamScan
for point cloud: new Vector2[] {
5.916275853509346, -4.228267720344762
8.31483976082672, -0.3807196367883092
3.9941738969349405, -0.491971233546733
-5.952110964171484, -0.7480752942332325
};

Result is: new Vector2[] {
5.916275853509346, -4.228267720344762
8.31483976082672, -0.3807196367883092
3.9941738969349405, -0.491971233546733
};

At least one missing point:
(-5.952110964171484, -0.7480752942332325)

Gift wrap

Counter example for GiftWrap
for point cloud: new Vector2[] {
-0.9025337983824699, 4.56709308364953
-5.5168621708920345, 0.34366552069341916
-2.400927400987851, 3.19563523962121
-9.419896312210547, 3.19563523962121
};

Result is: new Vector2[] {
-9.419896312210547, 3.19563523962121
-5.5168621708920345, 0.34366552069341916
-2.400927400987851, 3.19563523962121
};

At least one missing point:
(-0.9025337983824699, 4.56709308364953)

Also this one causes infinite loop:

for point cloud: new Vector2[] {
-0.33826889474805055, 8.329321811558497
-3.5586156659982215, -3.467244912905423
-3.5586156659982215, -4.566140779700733
-3.5586156659982215, -3.05702346750299
1.1178446483487536, -3.05702346750299

Divide and Conquer

Error for DivideAndConquer
for point cloud: new Vector2[] {
-5.214810023866061, -5.581528163221621
-3.2956195481849493, 6.700146933201903
2.159226322162535, -2.2353877725618476
4.84788802330902, -6.921113359457114
4.84788802330902, -6.921113359457114
};

Unexpected exception occured: 
java.lang.NullPointerException
	at org.dyn4j.geometry.hull.LinkedVertexHull.getEdge(LinkedVertexHull.java:366)
	at org.dyn4j.geometry.hull.LinkedVertexHull.mergeHulls(LinkedVertexHull.java:236)
	at org.dyn4j.geometry.hull.LinkedVertexHull.merge(LinkedVertexHull.java:109)
	at org.dyn4j.geometry.hull.DivideAndConquer.divide(DivideAndConquer.java:95)
	at org.dyn4j.geometry.hull.DivideAndConquer.generate(DivideAndConquer.java:66)
	at mainPackage.AppMain.v(AppMain.java:94)
	at mainPackage.AppMain.<init>(AppMain.java:231)
	at mainPackage.AppMain.main(AppMain.java:610)

About this issue

Original URL
State: closed
Created 5 years ago
Comments: 21 (21 by maintainers)

Most upvoted comments

AdaptiveDecimal sounds quite nice to me!
let’s go with getErrorComponentFromSum then, nevermind the length 😁
Alright I’ll implement robust Polygon.contains and friends seperately in the unit tests

Since we’re done with the discussion here I’ll implement those final changes and then do the PRs (soon enough) 🎉

mtsamis on Dec 21, 2019

@wnbittle here are some updates on the topic. I have made a draft implementation of the said algorithm for side of line testing that is quite readable. I need some time to fix some bugs it has, write tests and documentation. I’m trying to make the algorithm very understandable by trading some speed (maybe up to 2x for the hardest cases, but because the whole thing is complex I go for readability etc).

While I’m writing these, the question occurred to me “but will this new exact algorithm solve the hull algorithms bugs?”. So I made a simple slow exact implementation with Java’s BigDecimal and made the HullAlgorithms use it. It turns there are still other bugs that will need to be fixed.

Good news: GiftWrap passes all the automated tests and seems to neither hang nor produce wrong output. Just by replacing the getLocation method.
Not super good news: Both GrahamScan and DivideAndConquer still produce bad output. But hopefully, since the exact implementation didn’t help, this probably means there are some ‘straightforward’ algorithmic bugs to fix and then the algorithms will function properly.

Do you want to check for those bugs while I’m writing the other implementation? I can provide counterexamples for the versions using the exact arithmetic for getLocation which is below.

public static double getLocation(Vector2 pa, Vector2 pb, Vector2 pc) {
    BigDecimal pax = new BigDecimal(pa.x);
    BigDecimal pay = new BigDecimal(pa.y);
    BigDecimal pbx = new BigDecimal(pb.x);
    BigDecimal pby = new BigDecimal(pb.y);
    BigDecimal pcx = new BigDecimal(pc.x);
    BigDecimal pcy = new BigDecimal(pc.y);
    
    BigDecimal result = pcx.subtract(pbx).multiply(pay.subtract(pby)).subtract(pax.subtract(pbx).multiply(pcy.subtract(pby)));
    double locExact = result.doubleValue();
    
    return locExact;
}

mtsamis on Nov 20, 2019