Comments (2)
Hi @mourner! I'm glad you're interested in this library.
I don't know if your question is on the Subramaniam algorithm or my implementation. Just for clarity: I'm not affiliated with the author of the paper, but I came across the article when I wanted to solve the elliptical buffers made by Turf and made an implementation. I wrote my implementation based on the article text, in stead of porting the provided C/C++ code over to JS.
Indeed, the article is not specific on degenerate cases such as multiple intersections at the same point and paralel lines (as it literally mentions).
Regarding the known limitations of my implementation: I talk a bit about this in the README under 'Some notes on the algorithm': currently the algorithm rejects input polygons with non-unique vertices, because in many of those cases it fails. I gave one example there, too. Generally, it found that it fails on most input polygons that are non-simple for another reason than self-intersection (with the exception of spikes).
For my immediate case of geodesic buffers, this was only a minor problem since the input polygons are rings created by buffering objects, which are quite smooth and, given the geodesic nature, don't tend to give rise to coinciding points or parallel lines. Hence, I could afford to leave this issue open. But for a rigorous implementation it's absolutely key to be able to deal with degeneracies.
Whilst writing the current code, I started thinking about about degenerate cases. I came to the conclusion that turning the algorithm on its head would result in a more elegant algorithm that could also handle all of these cases (as far as my mind could imagine them): in stead of walking from intersection to intersection, you could design an algorithm to walk from pseudo-vector to pseudo-vector. An intersection could then be linked to an (ordered) list of pseudo-vectors, in stead of the current 2 pseudo-vectors per intersection. This would allow to deal with multiple edges crossing at the same point, etc.
Since this would be a large rewrite and probably not result in a speedup, I didn't do it at the time.
Note that we're getting pretty close to the concept of a topology: ideally you want to be granted a topology as input in stead of a geometry, and use that to walk over. It will guarantee you to treat degenerate polygons correctly. I though about using e.g. topojson to preprocess the input, but it doesn't accept inputs with self-intersections.
Greetings!
from simplepolygon.
@mclaeysb thank you for the detailed response! To give you some context on this question — I'm currently working on a library for repairing polygons that will be 100% robust on ALL cases, including any kinds of degeneracies, and also handling finite precision (e.g. given an integer coords input, rounding intersection points to integers in a way that doesn't introduce new intersections).
I'm halfway there — currently the library can properly find and snap all intersections, and then produce a graph where each intersection point (or a junction) has a sorted circular linked list of its incoming/outcoming edges. The biggest remaining part is figuring out how to traverse this graph correctly, but handling collinear edges is very tricky. Hopefully I'll figure out how to do that. You're welcome to poke at the repo — I'll be glad to hear any feedback!
from simplepolygon.
Related Issues (8)
- documentation outdated? HOT 3
- One Step Closer HOT 10
- allIsectsAsIsectRbushTreeItem is not declared HOT 3
- Self intersecting polygon -- some sub regions not getting detected HOT 6
- process.hrtime not available in browser HOT 1
- Complex polygon only return two parts HOT 3
- Polygon with holes (inners are replaced as outers) HOT 4
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 simplepolygon.