用户手绘的SVG图形,其中一些是路径,需要求任意两点最短路。
计划就是将SVG分析转换成graph:polyline每个point转换成graph里的vertices。之后判交点,交点添加到图中。由于点量较大故用邻接表。
实际实现中发现的问题也没出乎预料,手绘的精度导致以数学方法判断相交很不现实,由于polyline的粗度导致一些线看起来相交了实际没有。观察到这件事仅限于用户想要一个点落在另一线段上的时候会发生。故作额外步骤:未相交两线段求端点—线段的距离;小于某个阈值就强行相交(O///_///O)。
此外交点添加到图中时要和最近的交点相连。
然后最短路算法拉过来一个合适的就好了。
没怎么想也想不出来什么更聪明的做法了。用几个现实datapoint测,基本没什么拖延。