search

ABAPlan / abaplan-core

Core ABAPlan project
MIT License
4 stars 2 forks source link

Improve segments intersection algorithm #48

Closed jcavat closed 7 years ago

jcavat commented 7 years ago

All segments of all polygons are compared. Segments in collision are deleted. Now, the algorithm is O(n^2) regarding to he number N of segments.

jcavat commented 7 years ago

Now, algorithm is improved. We have O(M) linear operations for M polygons. If polygons intersection we have O(filtered(n^2)) where filtered(segments) is only segments inside a common window on x and y. Window is very small.