Does anyone have a method to determine whether a point is to the left or right of a line drawing in SQL?

I have a line feature representing a section of coast and another layer of points. I wish to keep only those points which are onshore.

Any pointers much appreciated and apologies if it is simple (maths was never my strong suit)

Landsystems Ltd ... Know your land | www.landsystems.co.nz

I am guessing that this is straightforward for a segment, but not so much for multiple points on either side of a complex coastline?

Landsystems Ltd ... Know your land | www.landsystems.co.nz

What about extending artificialy coastline at its end, making closed polygon out of it (dummy equivalent of sea or land) and checkin spatially if points are within this artificial area?

Thanks gregory, I had thought of that but guessed that there would be a robust mathematical way of doing it. I am trying to automate a workflow so the less manual intervention the better.

It is helping me formulate a few feature suggestions as quite often I want to do variants of this sort of problem.

Landsystems Ltd ... Know your land | www.landsystems.co.nz

I'm rather with Gregory. IMO, the land form coastline should be part of a boundary for a polygon to easily check the spatial overlay to see which point reside inside the landform (not coastline / poly line).

Better to leave the lines for presentation in this case. Now for determining if points residing on the coastline, i.e. touching, that may or may not result in a desired expectation. Experimentation!

The region I work within is not entirely surrounded by coastline and equally I might not wish to process all of the coast. I am looking for a general case solution as this is useful both for lines and polygons.

Landsystems Ltd ... Know your land | www.landsystems.co.nz

I’m with the others too.

There is an easy 1D solution for any line segment and any point. There is an easy 2D solution for any simple area and any point (which is really just the 1D solution plus a winding rule).

I’m sure there are also easy 3D solutions for everywhere-convex surfaces (because in relation to any point, these surfaces are either locally triangles or locally spheres), but things are going to get tricky really quickly without that restriction (Riemann, Poincaré… proper maths that I don’t know).

I’m pretty sure that there can be no test for an unembedded line sequence. You need an embedding to make the question meaningful.

But maybe a hint would do, if you can find the right hint. For example, restrictions on the choice of start and end segments. They would need to stand in a defined relation to the area of which they were part. Both right-handed or both left-handed, for example. (Not one of each.)

So tgat you could subdivide a known coastline (closed area) into sections beginning and ending left-handed, and sections beginning and ending right-handed. These would in effect be proxy areas, although not closed.

(Because the whole area or line sequence was known to be closed, the minimum number of such subsections would be well-defined, and because of this property you could take any arbitrary greater number of subdivisions and be equally safe, provided their handedness was the same at both ends.

…I think.)

Thanks for your various thoughts. Unfortunately, I think my mention of coastline has been a bit of a distraction from what I was getting at. I should have just said polyline and posted some test data/images.

Anyway, that aside, I quite regularly have need to do this sort of test when working with rivers, stop banks (and coastlines) but think what would work in most cases would be the facility to buffer on one side of a line.

It appears that this can be done in ArcPro (https://pro.arcgis.com/en/pro-app/latest/tool-reference/analysis/buffer.htm), so having this available, I will do a bit of experimentation with this tool and perhaps come back to Manifold with a feature suggestion.

In truth for my task here I want to test if some split Voronoi lines are to the left or right of a line but started thinking about points because I could place a point on most objects and perhaps test this. Also over the years I have harvested many useful M8 examples largely from you Tim, around placing points perpendicular to line segments adding tie lines etc. etc which seemed to be the key to this.

The attached image is an example from my project. I have a set of Voronoi lines split at a 'base of cliff' feature (as evidenced by the selection in red) and wish to delete the seaward lines. A topological left/right buffer would allow me to do this. I buffer by a small distance, and see if the lines intersect the buffer.

Attachments:
Clipboard-1.jpg

Landsystems Ltd ... Know your land | www.landsystems.co.nz

A quick go in Pro and the facility to buffer a line on the topological left or righthand side of a line as in ArcPro would cover a number of cases.

I will put in a feature request. Thanks for all your help and my apologies for not being clearer at the start.

Attachments:
Clipboard-2.jpg

Landsystems Ltd ... Know your land | www.landsystems.co.nz

Dan,

If your line is directed, and you know what the direction means, then that is almost everything—but not quite everything! I think this is the temptation (forgive me).

Same with buffers.

Pockets are, in both cases, going to give directly erroneous results, at least in some cases. (Would those cases be hard to detect? Maybe not. I haven’t thought about that. Convex hull s woukd be a useful tool here.)

You mention that coastlines were possibly a distraction, but no they are perfect even if only as an analogy.

There is no meaning to inside or outside for a line sequence unless the line sequrence is explicitly related to a closed loop or a simple area.

Thanks Tim,

You mention ...

There is no meaning to inside or outside for a line sequence unless the line sequrence is explicitly related to a closed loop or a simple area.

There is a very good chance that I don't understand fully what you are getting at, but I am interested in whether an object lies to the topological left or topological right of a directed line (in this case the 'base of cliff' feature). This as far as I can tell is possible as long as you know the direction of this line.

I will definitely add in my request for the option to include flat end types (which I would like to see as an option to the buffering that we already have) as this is useful to eliminate some potential errors at the end of the line(s) and in other cases that I have encountered in the past.

Additionally to the ability to produce the only the outer part of of the buffer as a line would also be very useful to my work at least (see attached). This I can probably produce myself from a side buffer with SQL, but I would always rather these things were built in to make them more accessible and Manifold are much better at SQL than me

Attachments:
Clipboard-3.png

Landsystems Ltd ... Know your land | www.landsystems.co.nz

Repeating only part of the above, not the most important bits...

A single ordered line segment relates to any point unambiguously (in Euclidean space). When they together are made to form a line sequence, they are either left or right handed, or straight. That can always be easily determined, as you say.

Then, provided you know whether a left handed or right handed turn should count as "inside" or "outside", you know that quality of the point too. But only if you do know.

Otherwise, you just don't. You can't.

When you come to two line segments and a point, it's similar territory (with one or two extra checks, e.g. intersection).

But with three or more line segments--now you can't avoid considering closure or non-closure. That is, considering areas.

It is always simple if you only care about immediate handedness, but gets complicated if you care about "in" and "out". They are not totally different concepts, but different enough.

(Again, you could try what I suggested by way of semantic subdivision of closed line sequences, or some other kind of ordered hints.)

Here is an example of a problem with the question "is point P to the left or to the right of the line L?":

Is the point to the left of the line? The answer seems to be yes, because it is to the left of one of the starting segments. Is the point to the right of the line? The answer seems to be yes as well, because it is to the right of one of the ending segments. So the answer to "is the point to the left or to the right of the line" seems to be "it is both".

And that's just the beginning of it, there is no doubt in my mind that there are much worse configurations.

And no, functions that create left / right side of a buffer won't make it any clearer. For this particular example, if the distance from the point to the two neighboring segments is about the same, the answer to "is the point to the left or to the right of the line" is going to be either "neither" or "both", depending on the width chosen for the side buffers.

I would try to change the question to something better-defined.

Attachments:
point-lt-rt.png

Thanks Adam, this helps a lot. I believe that the topological buffer would still allow me to solve my current problem and all of the other cases that I am thinking of, but clearly not communicating that well.

Most if not all of the time I would actually be checking for which side directed lines are from another directed line as in the 'Clipboard '1 image below. I actually don't really care about left and right per se, rather I seek to differentiate one side as distinct from another relative to the direction of a line. A buffer or offset line would allow me to do this in the vast majority of cases and I'm I could flag cases where it is ambiguous as you illustrate.

The ability to buffer one side of a line or another is something that I would have found useful on many occasions during my use of GIS and I see that there is a 'single sided buffers (and offset lines) for lines' tool in GDAL that sounds like it offers exactly what I was proposing to request. I will have a look at this today and see if I can sharpen up my description.

We are encouraged to request the tools we want so I will get something submitted. Mean time, is there a way to run GDAL tools from within M9 SQL?

Landsystems Ltd ... Know your land | www.landsystems.co.nz

There is https://github.com/rkolka/OnionTopologySuite that has SingleSidedBufferCurve function.

Download add-in and unpack it under {Manifold}\shared

Example mxb attached.

Attachments:
m9_SingleSidedBuffer.mxb
SingleSidedBuffer.png

Nice! Thanks Riivo, I will check this out

Landsystems Ltd ... Know your land | www.landsystems.co.nz

Simplify the query. NTSSingleSidedBuffer creates area.

--SQL9

-- $manifold$ 

-- $include$ [OnionTopologySuiteGEOM.sql] 

VALUE @tab TABLE = (SELECT NTSSingleSidedBuffer([geom], -33) FROM [line]);

TABLE CALL TableCacheIndexGeoms(@tab, false)

; 

Acute angles may cause problems

Attachments:
SingleSidedBufferNeg.png

Hi Riivo, Unfortunately it ends up as a bit of a car crash using my coastline feature (see image). I have tried normalising the line metric but to no avail. Do you think it is just too complex or are there any gotchas that you are aware of?

Thanks for pointing me towards your toolset however, this looks really handy and there is much to explore there which I plan to spend a bit of time doing this morning. It is also very fast which is good.

I will continue with my feature request as it is demonstrable that Manifold engineering have the smarts to improve upon most implementations of tools. I also really like having transforms in the base package.

Thanks again.

Attachments:
Clipboard-4.png

Landsystems Ltd ... Know your land | www.landsystems.co.nz

Can you test the QGIS tool. Is the result same?

Try normalizing with the tolerance computed from the buffer size - eg, 0.1 of it. This should reduce the amount of jitter dramatically without altering the final shape of the (side) buffer too much.

Thanks Adam and Riivo, I will give this a try and try the buffer in QGIS. I will post back the result shortly.

Landsystems Ltd ... Know your land | www.landsystems.co.nz

Find attached an mxb with my data and the results from QGIS, Onion and normalising topology.

QGIS is much cleaner (though still has artifacts), but unfortunately the Onion output is still a bit of a dogs breakfast. I wasn't sure about input and output projections for Onion so I first reprojected my coastal line from New Zealand Transverse Mercator to Pseudo Mercator first as this is what you have in your original project Riivo.

Normalising topology, while it helps doesn't clean it up that well (I used a precision of 1).

Attachments:
m9_SingleSidedBuffer_DanB.mxb

Landsystems Ltd ... Know your land | www.landsystems.co.nz

Yeah, seems it would be best for us to add our own function to do a side buffer (plus a function to do an offset line).

The result from Onion could be cleaned up by removing holes in the resulting area. But that's an extra step and it feels wrong to have to post-process the result like that.

That would be great Adam and would nicely round out the buffer tools. Many thanks for considering this.

I would also vote for a choice of rounded or square ends. I will try and find time to get my suggestion in today.

Landsystems Ltd ... Know your land | www.landsystems.co.nz

What I would love, instead or as well (at any rate, more), is the addition of means to address active components via the API (and if possible directly from SQL).

By active components I mean the all components open in a window, the window with focus, the layer with focus in each open window, as well as the component(s) selected in the Project pane.

This is critical stuff, often requested, and its absence in 9 is a long-standing frustration.

The reason for raising it here (you might well ask why) is that it would be a satisfying small challenge to write a readily reusable plugin to, say, draw a single-sided buffer, with or without square or rounded ends, for whatever component the user chooses by the simple expedient of opening or selecting it. Just as one (good) example. This approach always worked well in 8.

By not providing these hooks to the community, Engineering is effectively reserving the role of supplementing the Manifold 9 toolset largely to itself. Not entirely, since yes, we can build and enumerate a drop-down list of components, adding our own filter. That's a bit clumsy--it's usually more convenient to let the user just show which component to operate on, implicitly by context. Besides, no one is really interested in reading the muck and goo necessary for a drop-down and filter, so projects like this tend to be packaged into a closed DLL, making a missed opportunity for collective learning.

Adding these missing pieces of infrastructure would allow significantly better utilisation of (abundant) community talent, greatly enhance the utility of the 9 at any point in time, and encourage broader product take-up.

Are we talking about being able to write something like:

--SQL9

VALUE @t TABLE = CALL GetActiveLayer();

UPDATE @t SET ...;

With the idea of putting an .SQL file with this code into, eg, ~\shared, and then invoking it from the main menu?

If so, this is doable. The culprit is that normally such add-ins also need some prompts / dialogs. And while the simplest prompts could be done in SQL, SQL isn't the right tool for it, scripts are (as the UI gets more complex, you need to write code that responds to events, event callbacks are pretty alien to SQL, but natural for scripts). And if we are writing a script instead of a query anyway, we don't need functions like GetActiveLayer(), we can simply generate the text of the query and put the name of the active layer that we want to use into it.

Now, we do not currently have API functions to access windows and their components. We will add them. (We promised this a long time ago, I know. I'll bump the request.)

There is an update:

OffsetCurve function has better algorithm http://lin-ear-th-inking.blogspot.com/2022/01/jts-offset-curves.html

Download new version of Onion and use function NTSOffsetCurve(@geom, @distance) instead of NTSSingleSidedBuffer(@geom, @distance)

https://github.com/rkolka/OnionTopologySuite

Attachments:
m9_OffsetCurve_DanB.mxb
offset_curve.png

m9_SingleSidedBuffer_DanB.mxb image

Is it important that the onion library files ( dll sql files ) location should be "C:\WORK\gis\edge\shared\OnionTopologySuite" or "C:\WORK\gis\edge\shared\" ?

*.dll can also be inside "C:\WORK\gis\edge\bin64" !!!

Attachments:
CleanShape.png
onion_Install.jpg

Book about Science , cosmological model , Interstellar travels

Boyle surface fr ,en

Excellent thanks for this Rivo. Very much appreciated. I will give it a go when I get oportunity, though I still hope that Manifold will consider adding something to the base package as I believe that they will make a more robust and performant job of it.

By coincidence, today I have come across another example of where I need to know the side of a line, this time trying to come up with a process to blend the coincident edges of LiDAR datasets or to blend LiDAR data with coarser grid data.

I have come up with a couple of functions which progressively transform a coarse DEM surface height (solid orange) to LiDAR data surface (solid blue) over a user defined seam distance (DEM to LiDAR transformed heights represented by orange dashed line).

I also have the reverse of this transforming from the LiDAR surface to the coarser DEM (dashed blue heights).

For some of the objects in my test data, this process works perfectly. For others however, I need to choose the alternative algorithm as the blend goes the wrong way. Knowing if something is on the left or the right of a line would make it much easier to know which blend algorithm to use.

Landsystems Ltd ... Know your land | www.landsystems.co.nz

My 2c worth. Faced with this problem I would create a buffer as wide as necessary on the line, split it by the line then tag each side left/right. Then run spatial overlay points on buffer picking up left/right.

Aussie Nature Shots

If the line is a section of coast, are there other lines which continue the coastline? If so, they'll all eventually close to form the boundary of the country. Use the Trace transform to create the area enclosed by all those lines. Select points that are within the area, invert the selection to get the points that are not in the area, and then delete those.

Hi Dan, would Copy Parallel or Move Drawing Objects (http://www.georeference.org/forum/t54145.8#54161) help? Then you can create polygons to select points?

Thanks Mark? That is actually one of the bits of Tim's code that I had previously harvested and was tinkering around with. As long as I could differentiate which side of the coast line it is on, It would definitely do the job. I have to park this for a while and go back to LiDAR but will be back to this again soon and will get my feature request in as soon as I get chance. Thanks for the pointer. Much appreciated.

Landsystems Ltd ... Know your land | www.landsystems.co.nz