Comments (4)
I chose too small a tolerance value.
I hunted down a bug which boiled down to mis-ordering of edges in the open_edges list because in the definition of the less than operator for the EdgeKey, the edge_intersect was returning false in the case pictured below.
The red line is the connector between the point for which the visible vertices are being counted, and the cyan endpoint is the current point being evaluated for visibility. This red line is eventually incorrectly evaluated as visible.
The magenta line is the scan line. The cyan edge is mistakenly considered not intersecting with the magenta line because of rounding error. The edges 2 and 3 are not ordered correctly (both are considered less than the other), which later causes a failure to delete edge 2 from the open_edges because the index for it is incorrect. That means that later, this edge persists in the list of open_edges as the open_edges[0] edge, which is not the right choice of edge to evaluate when we get to evaluating the cyan point.
In the end just changing the abs_tol to 10e-15 (from 10e-16) was sufficient to solve this problem. I need to read up on representation error and justify a better choice for the abs_tol.
from pyvisgraph.
From Kitzinger's thesis: "Another issue about collinearity is that sometimes it is difficult to exactly specify the coordinates of points that are supposed to be collinear to each other. To help with this, all of the implementations described in this paper allow the user to specify a tolerance (given by some small epsilon) in which the angles or slopes may deviate to still be considered collinear. This also allows slope and angle calculations within the implementations to lose some precision (which is inevitable with IEEE floating point representation)."
I never implemented this, nice that you found a solution.
Note that in angle2, I round to 5 decimals. angle2 is used in the ordering of edges, so maybe that is having an effect.
from pyvisgraph.
In the end just changing the abs_tol to 10e-15 (from 10e-16) was sufficient to solve this problem. I need to read up on representation error and justify a better choice for the abs_tol.
so setting a tolerance in ccw()
was enough or did you have to make changes to the EdgeKey
class, i.e. set a tolerance somewhere else as well?
from pyvisgraph.
@eshira this and this is a quick overview of the representation error. You can use the Decimal
class to see what the actual representation of a float is. For example:
from decimal import Decimal
Decimal(1.1)
>> Decimal('1.100000000000000088817841970012523233890533447265625')
The representation error seems to consistently happen at the 18th significant digit. The Wikipedia article states that the floating point representation that Python uses will have 15-17 decimal digit precision. So when you start adding or multiplying numbers together, the errors starting from the 18th significant digit start adding up:
Decimal(1.1*1.1)
>>Decimal('1.2100000000000001865174681370262987911701202392578125')
Now the error is occurring from the 17th significant digit.
So the correct tolerance would depend on your coordinate system. For my usecase, I have numbers with up to three digits before the decimal point, which gives me less precision after the decimal point. a tolerance of 15 has been working fine and makes sense.
Maybe there is a better way using Numpy or something, I will have to look into that.
from pyvisgraph.
Related Issues (20)
- Performance testing HOT 1
- Progressbar output not functional for workers>1 HOT 2
- Suggestion: examples folder HOT 3
- Add Pyvisgraph documentation HOT 1
- Start or end point on polygon boundary HOT 1
- Requesting support for smaller distances HOT 1
- shortest path crossing the obstacle HOT 2
- is haversine distance in use? HOT 1
- Bug HOT 3
- VG generate wrongly due to polygon_crossing function not accurate HOT 1
- Performance hit & js port HOT 3
- Outdated link to GSHHS shapefile for 1_build_graph_from_shapefiles.py: add this update and clarification
- Visibility graphs have a huge number of polygon crossings HOT 8
- IndexError HOT 1
- Visibility graph bug HOT 1
- Crash when vertices overlay HOT 2
- Is it possible to have a boundary polygon? HOT 2
- Detecting points on the edges of a polygon
- Extending to 3D possible?
- License file is not packaged in the PyPi tarball
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 pyvisgraph.