|
|
back to boardRe: Input precision to avoid decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. Re: Input precision sorry for so many dumplicate post with so fucking network Edited by author 21.10.2016 14:59 Re: Input precision to decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. Re: Input precision to decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. Re: Input precision to decreasing precision error we can find delaunay triangulation of m points and for each n points we can first find which delaunay triangle it is in, compare these three points and its adjcent triangle. at least one of the point with minmum distance in these three triangles, if we find three point of one triangle if equal to minimum distance, continue to find its adjcent triangles. Re: Input precision Posted by Orient 10 Nov 2016 18:07 I thought about Delanau triangulation. I have nD implementation of Quickhull algo, which can give me triangulation, when applied to projection onto paraboloid. Bit it is not too hard to imagine bad case for BFS on triangulation graph. E.g. well known concentric points. It is the same bad case as for quadtree. Edited by author 10.11.2016 18:12 Re: Input precision Posted by Orient 20 Dec 2017 21:49 Does your last solution use this algorithm? Re: Input precision NO, my AC sol directly find voronoi diagram but when Location the point, you mustn't find the intersection point of x==x0 instead you should find the nearest Thiessen polygons directly using Euclid distance to sort it.. in a word you should use original point as much as you can to inprove your accuracy btw seems there is some clever k-d tree sol also get AC... Edited by author 20.12.2017 21:58 Re: Input precision Posted by Orient 20 Dec 2017 22:59 What do you think, are top 3 solution implemented via Voronoi? I implemented Fortune's ( https://github.com/tomilov/sweepline), but I can't overcome precision errors in case of regular grids and concentric points, even if I use a little cheating: I modify input by rotation on some small angle. Some of points became a points-in-general-positions. Then I use something like this ( http://www.link.cs.cmu.edu/15859-f07/papers/point-location.pdf), but invented by myself - it is much simplier for Voronoi diagram. I interested to talk with you (I will not bother you much), can you give any contact? Edited by author 21.12.2017 19:51Re: Input precision you can contact me through 441766573@qq.com my qq is always online... Re: Input precision Posted by Orient 21 Dec 2017 21:10 you can contact me through 888888888@qq.com my qq is always online... You can remove the number and add me to your contacts =). |
|
|