Comments (4)
I began implementing this but as I thought more about it... were should this be implemented?
It might be possible to simplify the whole graph, for example (self.graph
), but perhaps we should simplify every polygon in self.polygon
(or choose which one to).
Wouldn't it be useful to add a separate class Polygon
to manage each one independent of the graph?
from pyvisgraph.
Thanks for the interest!
The reason I did not implement a separate Polygon class is that the visible vertices algorithm doesn't care about polygons, only Point
's and Edge
's. So from a performance standpoint (I use fairly large polygon obstacles), its faster to use a dictionary where the key is a Point
and value is a set of Edge
's. This is in a similar spirit to the canonical way of implementing graphs in Python, see Guido's essay. I do store the polygons in self.polygon
, as its needed for point_in_polygon
checks.
My thinking for implementing simplify_polygon
would be as follows: I would not do it as a Graph
method that runs on self.graph
, because think of the way the visible vertices algorithm uses the obstacle graph - it uses it once to build the visibility graph. Once the visibility graph is built, you would not update or change/simplify the obstacle graph, because that would break the visibility graph.
You will always run simplify_polygon
before building the visibility graph with VisGraph.build
. Therefore, I consider simplify_polygon
more of a helper function you access through VisGraph
. You could implement it as a function in graph.py, _simplify_polygon(polys, resolution)
, where polys
is a list of polygons (where each polygon is a list of Point
's). A user would call it through VisGraph.simplify_polygon
.
You can use it stand alone to test out and visualize your simplification:
import pyvisgraph as vg
w = vg.VisGraph()
polys = ... # Obstacle polygons from some shapefile or other input
simple = w.simplify_polygon(polys, 0.5)
# draw the simplified polygon with matplotlib or similar to verify your simplification
Or you could use it directly when building the visibility graph:
import pyvisgraph as vg
w = vg.VisGraph()
polys = ... # Obstacle polygons from some shapefile or other input
w.build(w.simplify_polygon(polys, 0.5))
Thats how I am thinking, but you might have better ideas!
from pyvisgraph.
Sure, I thought about the performance cost but I guessed the cost wouldn''t be much and the benefit of abstraction could facilitate the implementation of the simplify
algorithm.
However, it is true that changing the polygon would break the visibility graph, and so I implemented the function (simplify_polygon
) on VisGraph
. And, given that a polygon
is simply a list of Point
, instead of a list of Edge
, it is much simpler to manipulate them (removing the need for a Polygon
class abstraction).
My pull request will be coming soon.
One silly question. I assume we define "resolution" to mean len(new_poly)/len(old_poly)
, right?
from pyvisgraph.
I haven't looked into Visvalingam's algorithm yet, so I am not sure if you specify a resolution like you defined or if you specify a triangle threshold. I just wrote resolution in my above post to illustrate that some value is given to specify how large of a simplification you want.
Btw, the shapefile I use for testing is available here. I use GSHHS_c_L1.shp, which is the lowest resolution. I use pyshp
to read the shapefile and get the obstacle graph in the following way:
import shapefile
import pyvisgraph as vg
sf = shapefile.Reader("GSHHS_c_L1.dbf")
shapes = sf.shapes()
polys = []
polys.append([vg.Point(p[0], p[1]) for p in shapes[0].points])
This is for getting just one of the shapes, if you want all you just loop on shape in shapes
. Note that in that shapefile, shapes[0] is the Eurasian continent, with 1003 points. shapes[3] is North America, 667 points.
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.