Comments (4)
Interesting, it's been a while since I did anything on this code base. The problem with the example above (for the algorithm) is that in this case all of the points lie outside each other's polygon. So it fails to find an overlap.
A fix could be to check for line intersection for each segment as well. If any of the lines intersect, the polygons overlap. It should be possible to reuse the linesCross
method for this. This will make things a bit slower of course but not massively. There may be some more efficient algorithms out there for this.
Feel free to provide a PR. If not, I might look at this at some point but very low priority for me. In any case, thanks for reporting this.
from geogeometry.
Yes. These are existing test polygons:
Polygons p, p2 and p4 centers are very close and lie inside each other, so it is simple.
Consider this example:
(p3 overlaps with p5).
Or even this:
(p3 does not overlap with p6).
Here is my version of shouldOverlap test which fails (p5overlapP3 is yellow polygon on the image above, p6aroundP3 is magenta) :
`
public void shouldOverlap() {
double[][] polygon = new double[][] {
{50, 15},
{53, 15},
{53, 11},
{50, 11}
};
double[][] p2overlapping = new double[][] {
{51, 16},
{52, 16},
{52, 10},
{51, 10}
};
double[][] p3outside = new double[][] {
{60, 15},
{63, 15},
{63, 11},
{60, 11}
};
double[][] p4inside = new double[][] {
{51, 14},
{52, 14},
{52, 12},
{51, 12}
};
// polygon which overlaps with p3 but does not have center or any vertexes inside the p3
double[][] p5overlapP3 = new double[][] {
{60.3, 10},
{60.3, 22},
{61, 22},
{61, 10}
};
// polygon which lays around the p3 without overlapping
// polygon 6 is concave with its center lying outside of p6 but inside the p3
double[][] p6aroundP3 = new double[][] {
{ 63.39152174400882 , 16.3916015625 },
{ 63.38167869302983 , 17.2705078125 },
{ 64.30182213914463 , 17.02880859375 },
{ 64.24459476798195 , 8.349609375 },
{ 58.790978406215565, 8.349609375 },
{ 58.83649009392136 , 16.040039062499996 },
{ 59.40036514079251 , 16.171875 },
{ 59.377988012638895, 9.3603515625 },
{ 63.763065186029074, 9.3603515625 },
{ 63.918058296491104, 16.34765625 }
};
Assert.assertTrue(GeoGeometry.overlap(polygon,polygon));
Assert.assertTrue(GeoGeometry.overlap(polygon, p2overlapping));
Assert.assertTrue(GeoGeometry.overlap(p2overlapping,polygon));
Assert.assertFalse(GeoGeometry.overlap(p3outside,polygon));
Assert.assertTrue(GeoGeometry.overlap(polygon,p4inside));
Assert.assertTrue(GeoGeometry.overlap(p4inside,polygon));
// with overlap logic which check only center and vertexes this test fails
// edge intersections should be checked as well
Assert.assertTrue(GeoGeometry.overlap(p3outside,p5overlapP3));
Assert.assertTrue(GeoGeometry.overlap(p5overlapP3, p3outside));
// this test also fails because of the center logic.
// polygon 6 is concave with its center lying outside of p6 but inside the p3
// they do not overlap
Assert.assertFalse(GeoGeometry.overlap(p3outside,p6aroundP3));
Assert.assertFalse(GeoGeometry.overlap(p6aroundP3, p3outside));
}
`
from geogeometry.
Thanks for clarifying, I'll spend some time on improving this when I have a free moment.
from geogeometry.
I finally looked into this. The algorithm does not support concave polygons currently. p6 is concave. I added a clarification on this. Wikipedia hints at an algorithm that we might use but that would be a bit more work. https://en.wikipedia.org/wiki/Point_in_polygon
from geogeometry.
Related Issues (20)
- geoHashesForPolygon Poles Condition HOT 6
- This repo's master and maven repository are not at the same version HOT 2
- lineCross function is resulting in a false positive HOT 3
- Bbox lat/lng mixup HOT 2
- bounding boxes do not follow GeoJson spec HOT 1
- add tests for Douglas Peucker algorithm
- get rid of testng & kotest in favor of junit5 + kotest assertions
- Build out geojson model support
- improve validation
- add a max hashes to geoHashesForPolygon
- improve geoHashesForPolygon split and filter HOT 1
- expandPolygon produces weird results/broken
- GeoHashUtils.geoHashesForCircle is not generating correctly HOT 3
- poles check bug HOT 1
- Version 3.3.8 build with Java 21 HOT 2
- decode_bbox return array comment HOT 2
- Missing feature property: "id". Deserialisation fails when id is present HOT 2
- polygonContains doesn't seem to work correctly HOT 12
- geoHashesForPolygon HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from geogeometry.