Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [computational-geometry]

study of algorithms which can be stated in terms of geometry

1
vote
1answer
45 views

“Average” of two lines

I have a dataset of pairs of parallel linear features (railway tracks) and I need to simplify each pair into its central/median line. This could be achieved by computing a skeleton as suggested in ...
1
vote
1answer
90 views

Delaunay triangulation algorithm in shapely producing erratic result

I would like to triangulate the following polygon: The wkt for the geometry is given as follows: POLYGON ((3 0, 2 0, 2 0.75, 2.5 0.75, 2.5 0.6, 2.25 0.6, 2.25 0.2, 3 0.2, 3 0)) I ran this code to ...
1
vote
0answers
16 views

Points on the opposing side of a breakline

If you have a breakline or even a single line segment within a DEM, how can you tell if two points lie on the opposing side of that breakline or line segment? From a computational geometry standpoint ...
1
vote
0answers
266 views

Pattern recognition - machine recognition of plausible shape of a polygon

I have a schoolproject where the task is to locate all possible shapes (of a certain complex polygonic structure) in a layer of several heterogenous polygons. And now the task is to find all the ...
1
vote
0answers
44 views

Closest Point Pairs to determine grid resolution

I'm reading Hengl's (2006) Finding the Right Pixel Size. In it, among many different suggested approaches, he suggests using a grid resolution where > 95% of the closest point pairs do no fall into ...
2
votes
0answers
36 views

Is there an established method to declare “Forward” on a linear feature

Is there an accepted way to establish a Forward direction for a linear feature regardless of the ordering of the points used to store the feature? An example would come from Roadway Design in the ...
1
vote
0answers
86 views

Is this Fastest, most Elegant and Extendable to nD implementation of AABB Intersection?

I recently did an AABB (Axes Aligned Bounding Box) Intersection implementation on 2D and 3D objects for which I came up with such a short (and very fast) solution as follows. The demonstration below ...
1
vote
2answers
1k views

What algorithm allows me to calculate the set of all points inside a polygon?

Imagine I have a polygon, which represents the countours of a building on an integer 3D map (everything is a 1 meter by 1 meter block in that map). In the image below, you see several buildings ...
5
votes
1answer
345 views

Travel planning - Finding farthest points of a polygon

I’d like to organize a tour around the lake with 2 objectives: maximise the length of shores to view minimise travel distance In order to do so I can: Pick 2 most remote points on the lake in ...
11
votes
2answers
3k views

How to compute Straight Skeletons using Python?

Is there a Python package which provides an implementation of a Straight Skeleton algorithm? I'm aware that the open source (C++) project CGALcontains an implementation but it seems like cgal-...