0

SVG图形转成图(数据结构)

用户手绘的SVG图形,其中一些是路径,需要求任意两点最短路。

计划就是将SVG分析转换成graph:polyline每个point转换成graph里的vertices。之后判交点,交点添加到图中。由于点量较大故用邻接表。

实际实现中发现的问题也没出乎预料,手绘的精度导致以数学方法判断相交很不现实,由于polyline的粗度导致一些线看起来相交了实际没有。观察到这件事仅限于用户想要一个点落在另一线段上的时候会发生。故作额外步骤:未相交两线段求端点—线段的距离;小于某个阈值就强行相交(O///_///O)。

此外交点添加到图中时要和最近的交点相连。

然后最短路算法拉过来一个合适的就好了。

没怎么想也想不出来什么更聪明的做法了。用几个现实datapoint测,基本没什么拖延。

★太空飞鸽★

不知名单身青年音游狗。 Purdue University '16, Computer Science. Googler @ Mountain View, California.

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注