MultiSegmentIntersect - Maple Help

ComputationalGeometry

 MultiSegmentIntersect
 determine if a line segment intersects a string of segments

 Calling Sequence MultiSegmentIntersect( M, opts ) MultiSegmentIntersect( M, S, opts )

Parameters

 M - listlist or rtable of point coordinates to be used as endpoints of line segments. M can also be a list of multiple collections of points. S - (optional) a collection of indices specifying the line segments given as type list(listlist(posint). When M is multiple collections of points, each entry in S indicates indices as the corresponding entry in M. If M is a single collection of points, all entries of S indicate indices into that one collection. When M is a single collection of points, S may also be of type listlist(posint) for convenience. If not given, the it is automatically generated from M using one of several ways determined by the mode option. opts - one or more options, see the Options section.

Options

 • self : true or false, return the intersection of line segments which have endpoints in the same collection. Default is false if multiple collections of points are given, and true if only one.
 • mode : one of "pairs", "linestring", "polygon", or a list these. The default is "pairs".
 • lazy : if lazy or lazy=true is given then the command stops after finding one intersection.
 • output : one of "truefalse", "index", "coordinate". The default is "coordinate".

Description

 • If M is a single collection of points, this command returns a list of all the points at which intersections occur. It does so using a version of the Bentley–Ottmann sweep line algorithm and repeated calls to SegmentsIntersect.
 • If M is more than one collection of points, only the intersections of line segments in different collections are returned.  This is useful for giving a list of polygons and finding all the places the polygons intersect each other without including their corners.
 • If a second argument S is not given then the segments are implied by M and the mode option.
 – mode="pairs" : for each collection in M, adjacent pairs of points are taken as line segments.
 – mode="linestring" : for each collection in M, points are taken as lying in sequence along a piecewise-linear curve, or line string.
 – mode="polygon" : for each collection in M, the points are taken as the boundary of a (possibly self-intersecting) polygon. This is identical to mode="linestring" except that a segment will be added to join the last point to first point in each collection.
 – mode can be a list in order to use a different mode on each point collection.
 • The self option, if given, calculates the self-intersections of the segment collections. It is false by default unless only one collection of segments is given. In that case, self=false indicates that only intersections that occur at segment end-points should not be ignored.
 • The output option controls the form of the output.  If "truefalse" true is returned if there are any intersections at all and false otherwise. If "index", the return value gives the indices of the end points of the line segments that intersect.  If M is a list of multiple collections of points, then an index into M is also returned: $\left[\mathrm{mi},\left[b,e\right]\right]$. This is useful if you wish to know exactly which segments intersect rather than just their intersection. In the case that an intersection can be determined to occur exactly at a vertex (this can only happen when self=true) the index is returned as $\left["exact",\mathrm{mi},i\right]$ or $\left["exact",i\right]$ in the case of one collection of points.

Examples

 > $\mathrm{with}\left(\mathrm{ComputationalGeometry}\right):$
 > $\mathrm{plots}:-\mathrm{setoptions}\left(\mathrm{scaling}=\mathrm{constrained},\mathrm{axes}=\mathrm{none}\right):$
 > $M≔\left[\left[0,0\right],\left[0,1\right],\left[1,1\right],\left[1,0\right]\right]:$
 > $L≔\left[\left[\left[-0.5,-1\right],\left[-0.5,2\right]\right],\left[\left[0.5,-1\right],\left[0.5,2\right]\right],\left[\left[1.5,-1\right],\left[1.5,2\right]\right],\left[\left[0.75,1.5\right],\left[1.25,0.5\right]\right],\left[\left[-0.25,0\right],\left[1.25,0\right]\right],\left[\left[0.2,1\right],\left[0.4,1\right]\right],\left[\left[-0.25,0.5\right],\left[0.25,0.25\right]\right],\left[\left[0,0.5\right],\left[0,1.5\right]\right]\right]:$
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{seq}\left(\mathrm{plottools}:-\mathrm{line}\left({{L}_{i}}_{[]},\mathrm{legend}="L"||i,\mathrm{color}="Red"\right),i=1..\mathrm{nops}\left(L\right)\right),\mathrm{plottools}:-\mathrm{polygon}\left(M,\mathrm{style}=\mathrm{line},\mathrm{legend}="M"\right),\mathrm{axes}=\mathrm{boxed}\right)$
 > $\mathrm{MultiSegmentIntersect}\left(\left[{L}_{1},M\right],\mathrm{mode}="polygon",\mathrm{output}="truefalse"\right)$
 ${\mathrm{false}}$ (1)
 > $\mathrm{MultiSegmentIntersect}\left(\left[{L}_{2},M\right],\mathrm{mode}="polygon",\mathrm{output}="truefalse"\right)$
 ${\mathrm{true}}$ (2)
 > $\mathrm{MultiSegmentIntersect}\left(\left[{L}_{2},M\right],\mathrm{mode}="polygon",\mathrm{lazy}\right)$
 $\left[\left[{0.500000000000000}{,}{-0.}\right]{,}\left[{0.500000000000000}{,}{1.}\right]\right]$ (3)

P, Q, and R are the vertices of three irregular polygons

 > $P≔\left[\left[0.8485281372,0.3514718626\right],\left[0.3514718626,0.8485281372\right],\left[-0.3514718628,0.8485281370\right],\left[-0.8485281373,0.3514718624\right],\left[-0.8485281368,-0.3514718630\right],\left[-0.3514718614,-0.8485281376\right],\left[0.3514718633,-0.8485281368\right],\left[0.8485281374,-0.3514718621\right]\right]:$
 > $Q≔\left[\left[0.07795711098,-0.4379868877\right],\left[0.9081886538,-0.4686672090\right],\left[0.3310509455,0.1314238396\right],\left[0.07568485961,0.9992639501\right],\left[-0.3367585765,0.1931579319\right],\left[-0.8165279848,-0.4289815143\right]\right]:$
 > $R≔\left[\left[0.5872000891,0.6460853196\right],\left[-0.06333536874,1.751487097\right],\left[-0.6288418341,0.6328017610\right],\left[-1.719345382,0.02678891621\right],\left[-0.5837772511,-0.6164276625\right],\left[-0.05065049498,-1.745456068\right],\left[0.5734652878,-0.4860444847\right],\left[1.670119538,0.1041376233\right]\right]:$
 > $\mathrm{theplot}≔\mathrm{plots}:-\mathrm{display}\left(\mathrm{plottools}:-\mathrm{polygon}\left(P,\mathrm{style}=\mathrm{line},\mathrm{color}="Niagara 6"\right),\mathrm{plottools}:-\mathrm{polygon}\left(Q,\mathrm{style}=\mathrm{line},\mathrm{color}="Niagara 5"\right),\mathrm{plottools}:-\mathrm{polygon}\left(R,\mathrm{style}=\mathrm{line},\mathrm{color}="Niagara 9"\right)\right)$
 > $\mathrm{segints}≔\mathrm{MultiSegmentIntersect}\left(\left[P,Q,R\right],\mathrm{mode}="polygon"\right)$
 ${\mathrm{segints}}{≔}\left[\left[{0.848528137396171}{,}{-0.338014991924543}\right]{,}\left[{0.120039590504333}{,}{0.848528137134153}\right]{,}\left[{-0.00143898670186136}{,}{0.848528137099591}\right]{,}\left[{-0.770555651471915}{,}{-0.429444348202590}\right]{,}\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.821484869996484}{,}{-0.378515129536161}\right]{,}\left[{0.435447425512102}{,}{-0.764552574486531}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]{,}\left[{0.805041648484513}{,}{-0.361417944761064}\right]\right]$ (4)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{theplot},\mathrm{plottools}:-\mathrm{point}\left(\mathrm{segints},\mathrm{symbol}="circle",'\mathrm{symbolsize}'=15,'\mathrm{color}'="Black"\right)\right)$

Zooming confirms there is no intersection at x = -.5837772511

 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{theplot},\mathrm{plottools}:-\mathrm{point}\left(\mathrm{segints},\mathrm{symbol}="circle",'\mathrm{symbolsize}'=15,'\mathrm{color}'="Black"\right),\mathrm{view}=\left[-0.585..-0.580,-0.615..-0.620\right],\mathrm{axes}=\mathrm{box}\right)$

a different mode option can consider the collections as points of non-closed curves

 > $\mathrm{theplot}≔\mathrm{plots}:-\mathrm{display}\left(\mathrm{plottools}:-\mathrm{curve}\left(P,\mathrm{style}=\mathrm{line},\mathrm{color}="Niagara 6"\right),\mathrm{plottools}:-\mathrm{curve}\left(Q,\mathrm{style}=\mathrm{line},\mathrm{color}="Niagara 5"\right),\mathrm{plottools}:-\mathrm{curve}\left(R,\mathrm{style}=\mathrm{line},\mathrm{color}="Niagara 9"\right)\right)$
 > $\mathrm{segints}≔\mathrm{MultiSegmentIntersect}\left(\left[P,Q,R\right],\mathrm{mode}="linestring"\right)$
 ${\mathrm{segints}}{≔}\left[\left[{0.120039590504333}{,}{0.848528137134153}\right]{,}\left[{-0.00143898670186136}{,}{0.848528137099591}\right]{,}\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.821484869996484}{,}{-0.378515129536161}\right]{,}\left[{0.435447425512102}{,}{-0.764552574486531}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]{,}\left[{0.805041648484513}{,}{-0.361417944761064}\right]\right]$ (5)
 > $\mathrm{plots}:-\mathrm{display}\left(\mathrm{theplot},\mathrm{plottools}:-\mathrm{point}\left(\mathrm{segints},\mathrm{symbol}="circle",'\mathrm{symbolsize}'=15,'\mathrm{color}'="Black"\right)\right)$

Enabling userinfo for CompGeomPlot will show graphical steps of the algorithm

 > ${\mathrm{infolevel}}_{\mathrm{CompGeomPlot}}≔1:$
 > $\mathrm{MultiSegmentIntersect}\left(\left[P,Q,R\right]\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]\right]$ (6)
 > $\mathrm{MultiSegmentIntersect}\left(\left[{P}_{[]},{Q}_{[]},{R}_{[]}\right]\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]\right]$ (7)
 > $\mathrm{MultiSegmentIntersect}\left(\left[{P}_{[]},{Q}_{[]},{R}_{[]}\right],\mathrm{mode}="linestring"\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\left[{0.568350743082245}{,}{0.631649256717755}\right]{,}\left[{0.120039590504333}{,}{0.848528137134153}\right]{,}\left[{-0.00143898670186136}{,}{0.848528137099591}\right]{,}\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{-0.790756202823990}{,}{-0.409243796883027}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.821484869996484}{,}{-0.378515129536161}\right]{,}\left[{0.435447425512102}{,}{-0.764552574486531}\right]{,}\left[{0.800646260525579}{,}{-0.356847747854247}\right]{,}\left[{0.816931241317897}{,}{-0.355019369311793}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]{,}\left[{0.805041648484513}{,}{-0.361417944761064}\right]{,}\left[{0.254570590141784}{,}{0.391335878482655}\right]{,}\left[{0.351471862600000}{,}{0.848528137200000}\right]{,}\left[{-0.351471862800000}{,}{0.848528137000000}\right]{,}\left[{-0.848528137300000}{,}{0.351471862400000}\right]{,}\left[{-0.848528136800000}{,}{-0.351471863000000}\right]{,}\left[{-0.351471861400000}{,}{-0.848528137600000}\right]{,}\left[{0.351471863300000}{,}{-0.848528136800000}\right]{,}\left[{0.848528137400000}{,}{-0.351471862100000}\right]{,}\left[{0.0779571109800000}{,}{-0.437986887700000}\right]{,}\left[{0.908188653800000}{,}{-0.468667209000000}\right]{,}\left[{0.331050945500000}{,}{0.131423839600000}\right]{,}\left[{0.0756848596100000}{,}{0.999263950100000}\right]{,}\left[{-0.336758576500000}{,}{0.193157931900000}\right]{,}\left[{-0.816527984800000}{,}{-0.428981514300000}\right]{,}\left[{0.587200089100000}{,}{0.646085319600000}\right]{,}\left[{-0.0633353687400000}{,}{1.75148709700000}\right]{,}\left[{-0.628841834100000}{,}{0.632801761000000}\right]{,}\left[{-1.71934538200000}{,}{0.0267889162100000}\right]{,}\left[{-0.583777251100000}{,}{-0.616427662500000}\right]{,}\left[{-0.0506504949800000}{,}{-1.74545606800000}\right]{,}\left[{0.573465287800000}{,}{-0.486044484700000}\right]\right]$ (8)

The self option will also calculate polynomial vertices and any self-intersections

 > $\mathrm{MultiSegmentIntersect}\left(\left[P,Q,R\right],\mathrm{mode}="polygon",'\mathrm{self}'\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\left[{0.848528137396171}{,}{-0.338014991924543}\right]{,}\left[{0.120039590504333}{,}{0.848528137134153}\right]{,}\left[{-0.00143898670186136}{,}{0.848528137099591}\right]{,}\left[{-0.770555651471915}{,}{-0.429444348202590}\right]{,}\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.821484869996484}{,}{-0.378515129536161}\right]{,}\left[{0.435447425512102}{,}{-0.764552574486531}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]{,}\left[{0.805041648484513}{,}{-0.361417944761064}\right]{,}\left[{0.848528137200000}{,}{0.351471862600000}\right]{,}\left[{0.351471862600000}{,}{0.848528137200000}\right]{,}\left[{-0.351471862800000}{,}{0.848528137000000}\right]{,}\left[{-0.848528137300000}{,}{0.351471862400000}\right]{,}\left[{-0.848528136800000}{,}{-0.351471863000000}\right]{,}\left[{-0.351471861400000}{,}{-0.848528137600000}\right]{,}\left[{0.351471863300000}{,}{-0.848528136800000}\right]{,}\left[{0.848528137400000}{,}{-0.351471862100000}\right]{,}\left[{0.0779571109800000}{,}{-0.437986887700000}\right]{,}\left[{0.908188653800000}{,}{-0.468667209000000}\right]{,}\left[{0.331050945500000}{,}{0.131423839600000}\right]{,}\left[{0.0756848596100000}{,}{0.999263950100000}\right]{,}\left[{-0.336758576500000}{,}{0.193157931900000}\right]{,}\left[{-0.816527984800000}{,}{-0.428981514300000}\right]{,}\left[{0.587200089100000}{,}{0.646085319600000}\right]{,}\left[{-0.0633353687400000}{,}{1.75148709700000}\right]{,}\left[{-0.628841834100000}{,}{0.632801761000000}\right]{,}\left[{-1.71934538200000}{,}{0.0267889162100000}\right]{,}\left[{-0.583777251100000}{,}{-0.616427662500000}\right]{,}\left[{-0.0506504949800000}{,}{-1.74545606800000}\right]{,}\left[{0.573465287800000}{,}{-0.486044484700000}\right]{,}\left[{1.67011953800000}{,}{0.104137623300000}\right]\right]$ (9)

The default modes and the mode option are meant to allow for convenience. The command can also take a single rtable of point coordinates together with a list of lists of index pairs specifying line segment end points in the point rtable. For best efficiency, the point rtable should be purely numerical and stored in C_order.

 > $M≔\mathrm{Matrix}\left(\left[{P}_{[]},{Q}_{[]},{R}_{[]}\right],':-\mathrm{datatype}'='{\mathrm{float}}_{8}',':-\mathrm{order}'=':-\mathrm{C_order}'\right)$
 > $S≔\left[\left[\mathrm{seq}\left(\left[i,i+1\right],i=1..8-1\right),\left[8,1\right]\right],\left[\mathrm{seq}\left(\left[8+i,8+i+1\right],i=1..6-1\right),\left[8+6,8+1\right]\right],\left[\mathrm{seq}\left(\left[14+i,14+i+1\right],i=1..8-1\right),\left[14+8,14+1\right]\right]\right]$
 ${S}{≔}\left[\left[\left[{1}{,}{2}\right]{,}\left[{2}{,}{3}\right]{,}\left[{3}{,}{4}\right]{,}\left[{4}{,}{5}\right]{,}\left[{5}{,}{6}\right]{,}\left[{6}{,}{7}\right]{,}\left[{7}{,}{8}\right]{,}\left[{8}{,}{1}\right]\right]{,}\left[\left[{9}{,}{10}\right]{,}\left[{10}{,}{11}\right]{,}\left[{11}{,}{12}\right]{,}\left[{12}{,}{13}\right]{,}\left[{13}{,}{14}\right]{,}\left[{14}{,}{9}\right]\right]{,}\left[\left[{15}{,}{16}\right]{,}\left[{16}{,}{17}\right]{,}\left[{17}{,}{18}\right]{,}\left[{18}{,}{19}\right]{,}\left[{19}{,}{20}\right]{,}\left[{20}{,}{21}\right]{,}\left[{21}{,}{22}\right]{,}\left[{22}{,}{15}\right]\right]\right]$ (10)
 > $\mathrm{MultiSegmentIntersect}\left(M,S\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\left[{0.848528137396171}{,}{-0.338014991924543}\right]{,}\left[{0.120039590504333}{,}{0.848528137134153}\right]{,}\left[{-0.00143898670186136}{,}{0.848528137099591}\right]{,}\left[{-0.770555651471915}{,}{-0.429444348202590}\right]{,}\left[{-0.796713219266504}{,}{-0.403286780450101}\right]{,}\left[{0.737635404097402}{,}{-0.462364595536458}\right]{,}\left[{0.821484869996484}{,}{-0.378515129536161}\right]{,}\left[{0.435447425512102}{,}{-0.764552574486531}\right]{,}\left[{0.625187746682136}{,}{-0.458209212271670}\right]{,}\left[{0.805041648484513}{,}{-0.361417944761064}\right]\right]$ (11)
 > $\mathrm{MultiSegmentIntersect}\left(M,{S}_{1},\mathrm{output}="index"\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\left[{"exact"}{,}{1}\right]{,}\left[{"exact"}{,}{2}\right]{,}\left[{"exact"}{,}{3}\right]{,}\left[{"exact"}{,}{4}\right]{,}\left[{"exact"}{,}{5}\right]{,}\left[{"exact"}{,}{6}\right]{,}\left[{"exact"}{,}{7}\right]{,}\left[{"exact"}{,}{8}\right]\right]$ (12)
 > $\mathrm{MultiSegmentIntersect}\left(M,{S}_{1},\mathrm{output}="index",\mathrm{self}=\mathrm{false}\right)$
 MultiSegmentIntersect:
 MultiSegmentIntersect:
 $\left[\right]$ (13)

Compatibility

 • The ComputationalGeometry[MultiSegmentIntersect] command was introduced in Maple 2019.