3

My input are two polylines -- I had one polyline and I computed offset of it, similarly to polygons. Here is the useful post: https://stackoverflow.com/questions/1109536/an-algorithm-for-inflating-deflating-offsetting-buffering-polygons

So I have to correct polylines, however the number of vertices (and segments) can vary, consider such polyline:

A\    /D
  \__/
  B  C

After offsetting it up ("inside") I could get

A'\  /C'
   \/
   B'

The horizontal segment is gone.

My task is to add in source or target polyline empty segments (i.e. duplicate vertices) in such way that the number of vertices is the same, and that I could iterate over one polyline and can get its counterpart in the other polyline just by index (no computation during "get").

In the case above I should get two polylines -- A, B, C, D (no change here) and A', B', B', C' (B' is duplicated).

I hope my question is clear. Now -- how to add "missing" vertices?

Improve this question
8
  • 1
    Are you showing us an open polyline example intentionally? Without a closed polygon, it is not inherently clear where "inside" and "outside" is. Morevover, if you (so your own algorithm) did the offset computing, doesn't your algo know which edges belong together?
    – Doc Brown
    Commented Dec 16, 2015 at 13:54
  • @DocBrown, by "open" do you mean -- without crossings? Yes, this is the case. I fix the wording in a second, I didn't do the computing, I just have 2 polylines and I know how they were computed.
    – greenoldman
    Commented Dec 16, 2015 at 14:15
  • No, I mean "open" as opposed to "closed" (which means start and end point are the same). When you look at the stackoverflow link, you will only find closed polygons, because inflating or deflating will make only sense when you know where the inside of the polygon is.
    – Doc Brown
    Commented Dec 16, 2015 at 14:22
  • @DocBrown, closed would mean polygons, not polylines. I added a link, because it is similar case (as I pointed out). And I didn't say I deflate polygon, only offset it (however the operation is similar as well).
    – greenoldman
    Commented Dec 16, 2015 at 14:59
  • So if it is not the same operation as in the SO link, can you give a more precise description how the operation works, and which parameters you know/do not know? I mean, if you know the exact offset and direction, it should be trivial how to map the vertices A,B,C,D to A', B',C', which gives you a mapping of the edges, too.
    – Doc Brown
    Commented Dec 16, 2015 at 16:18

2 Answers 2

Reset to default
1

You need to construct a mapping of the vertices from polyline one to polyline two, where duplicates are allowed. Once you have this, the mapping of the segments follows trivially from that.

You said you know the offset (a positive real value x) and the point coordinates. So for each segment A -> B in the first polygon, search the second polygon for a parallel segment A' -> B' of distance x. If you find exactly one, you are done for A and B. If you find none, look if there is a "zero length" segment like A' -> A' (in other words a single point) in the second polygon with distance x from A->B. When there is exactly one, you are done for A and B as well, they both map to A'.

If you do not find any parallel segment in the given distance, the polylines cannot be mapped, so stop.

The tricky part is to deal with the situation where you find more two or more parallel segments from A->B. For this case, put "A->B" back into the "bag of unprocessed segments" and continue with the next segment, lets assume it is "B->C". Maybe you are lucky and this one has exactly one parallel counterpart "B' -> C'", so now you know where to map B. After you processed all segments, start from the beginning with all unprocessed segments again. When processing A->B, there are still two possible counterparts in the second polyline, but now you know where B must be mapped, which reduces the number of possibilities to the parallel segments of distance x where B maps to the found B'.

Continue that algorithm until you either cannot process any segment from the "unprocessed bag" any more, or the bag becomes empty.

Improve this answer
3
  • Thank you, but the problem is not here "search the second polygon" -- I don't have to search, it is the next segment or not. The problem is, those segments could be small, and testing for being parallel in computer world with finite precision could lead to false detections (for both outcomes). How to overcome this, I don't know (yet). The more I think, the more I am convinced that synchronization has to be part of offset algorithm, meaning DIY from the beginning :-).
    – greenoldman
    Commented Dec 17, 2015 at 10:06
  • 2
    @greenoldman: the algorithm above does not "search the second polygon", it expects you know the coordinates of the vertices of the second polygon already, and it describes how to find the associations between vertices and segments of the two polygons. That is exactly what you asked for in your comment above. Now you bring the precision problem on the table, not one word before of that :-((( You should really edit your question and write a more precise description. FWIW, the precision problem can typically be solved by using some tolerance values.
    – Doc Brown
    Commented Dec 17, 2015 at 10:22
  • ... and yes,as I wrote in my initlal comment above, the offset algo knows which segments it maps from polygon 1 to polygon 2, so if you have access to that code, implement it there, makes things a hell lot easier than post-mortem reconstruction.
    – Doc Brown
    Commented Dec 17, 2015 at 10:26
0

What about you just don't add them ?

Let me clarify: you could store that information elsewhere. Why you need a segment that isn't there ? Just store the original polygon, or store the offsetted segments and their relationship with the original one in memory or a database ... serialize it in json maybe.

i hope i got what you meant...

I would just save the original polygon and the operation you made, so you can undo and redo with different values...

Telling what you need that for could get you an answer more easily!

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.